0

$a=bq+r$

I suppose$~~d|a~~\wedge~~d|b~~\Leftrightarrow~~a=dx~~\wedge~~b=dy~~$for some integers x y.

So

$dx=dyq+r$

$r=d(x-yq)~~\Leftrightarrow~~d|r$

What I've concluded is $~~d|a~~\wedge~~d|b~~\Rightarrow~~d|r$

A similar argument shows that $~~s|b~~\wedge~~s|r~~\Rightarrow~~s|a$

But I've stopped here, I need to prove that If$~~gcd(a,b)=d~~$and$~~gcd(b,r)=s~~$then$~~d=s$

Can someone help me? I think I'm almost there

Vinícius
  • 185

1 Answers1

2

Yes, you are almost there. Note that you proved that whenever a number divides both $a$ and $b$, then it also divides $r$. And that if a number divdes both $b$ and $r$, then it also divides $a$. So, you proved the the common divisors of both $a$ and $b$ are exactly the common divisors of both $b$ and $r$. Therefore, the greatest common divisor of $a$ and $b$ is the greatest common divisor of $b$ and $r$.

José Carlos Santos
  • 427,504
  • Bom dia, José. Vi que falas Português. Eu poderia afirmar que o conjunto dos divisores de a e b está contido no conjunto dos divisores de b e r e que o conjunto dos divisores de b e r está contido no conjunto dos divisores de a e b? Sendo assim esses conjuntos são iguais? Concluindo gcd(a,b) = gcd (b, r)? – Vinícius Mar 21 '18 at 07:47
  • @Vinicius Sim, é issi. – José Carlos Santos Mar 21 '18 at 07:52
  • Obrigado, eu ainda não tinha ligado os pontos, mas quando você falou que os divisores eram exatamente os mesmos, isso clareou minha mente. – Vinícius Mar 21 '18 at 07:55