# Prove: $\gcd(a,b) = \gcd(a, b + at)$.

I know that $\gcd(a,b)$ divides $a$ and $b$, and must also then divide $(a)(t)$ ($t$ being some integer). This makes sense to me, but how do I prove it? It seems that the addition of $(a)(t)$ is a continuation of the linear combination of $\gcd(a,b) = av + bu$ for some $v$, $u$ being elements of $\mathbb{Z}$.

Any help?

-

Let $d = \gcd(a,b)$ and $d' = \gcd(a, b+at)$. Then $d$ divides $a$ and $d$ divides $b$. So $d$ divides $at$. So $d$ divides $b+at$. Likewise, $d'$ divides $a$ and $d'$ divides $b+at$. So $d'$ divides $b$.

-
In your last sentence, you mean b+at ofcourse. – Myself Feb 23 '11 at 3:37

You're asking for a proof of the below.

let c = GCD(a,b); then c | a.t for integer t.


Let's refactor:

if c | a then c | a.t for integer t.


This is fundamental (it's very close to the definition of 'divisibility'), but to prove it:

if c | a then cx = a, for some integer x (this is the definition of divisibility)
if cx = a then cxt = at, for all integer t
c | cxt (again, the definition of divisibility)
if c | cxt, then c | at

-
Thanks for all the help with this – user7395 Feb 23 '11 at 4:06
@Kirk: That only proves (part of) the simpler direction, i.e. $\rm\ (a,b)\ |\ (a,b+at)$ – Bill Dubuque Feb 23 '11 at 4:20
'Hey all, I know that gcd(a,b) divides a and b, and must also then divide (a)(t) (t being some integer).' Aren't you asking for the proof that I've stated? I don't see that you're asking for the inverse as well. – Kirk Broadhurst Feb 23 '11 at 5:36
@Kirk: to prove naturals $\rm\ c = d\$ it suffices to prove both $\rm\ c\ |\ d\$ and $\rm\ d\ |\ c\:.\:$ Proving one of them does not suffice. – Bill Dubuque Feb 23 '11 at 5:50
@Bill But 'if/then' isn't the same as '='; if/then isn't necessariy a 1-1 function, it's an 'onto' function. I'm having TeX difficulties and can't read your answer, unfortunately. – Kirk Broadhurst Feb 23 '11 at 6:20

HINT $\rm\ \$ If $\rm\ c\ |\ a\$ then $\rm\ c\ |\ b + a\ t\ \iff\ c\ |\ b\:.\$ This implies that $\rm\ \{a\:,\:b+a\ t\}\$ and $\rm\ \{a\:,\: b\}\$ have the same set of common divisors $\rm\:c\:,\:$ hence they have the same greatest common divisor.

Modly: $\:$ if $\rm\ a\equiv 0\$ then $\rm\ b+a\ t\equiv 0\: \iff\: b\equiv 0\ \ \ (mod\ c)$

-
Would this proof be sufficient? let c be the gcd(a,b). So we know that cn=a, n being an integer, and cm=b, m being an integer. We know that c divides at, because ctn=at, so c divides (b + at) because it has been shown c divides b, a, and at. Am I on the correct track here or am I still a bit off? – user7395 Feb 23 '11 at 4:55
@Jeff: That shows $\rm(\Leftarrow)$. But it is more clear as follows: $\:$ suppose $\rm\ c\ |\ a\:.\:$ Then $\rm\ c\ |\ at\:.\:$ $\rm(\Leftarrow)\ \ c\ |\ b,\ c\ |\ at\ \Rightarrow\ c\ |\ b + at\:.\:$ $\rm(\Rightarrow)\ \ c\ |\ at,\ c\ |\ b+a\ t\ \Rightarrow\ c\ |\ (b+a\ t) - a\ t = b\:,\:$ precisely as I hinted. Note how my use of divisibility properties such as $\rm\ d\ |\ x,y\ \Rightarrow\ d\ |\ i\ x + j\ y\$ eliminates the need to introduce explicit names for quotients, such as your $\rm\:m,n\:$ above. They're inessential to the proof; eliminating such obfuscations clarifies the proof. – Bill Dubuque Feb 23 '11 at 5:40

$$\displaystyle ax+by = a(x-ty)+(b+at)y$$

-

Suppose gcd(a, b) = k - (1) gcd(a, b+at)=k' - (2)

If k' != k -

There are two cases,

1/ k' < k : Contradiction because k|(b+at).

2/ k' > k : Since k'|a again contradiction due to (1).

Therefore k = k'.

-

Since $a \equiv b \pmod{m}$ implies $\gcd(m, a) = \gcd (m,b)$, and $b +at \equiv b \pmod{a}$, $\gcd(a, b+at) = \gcd (a,b)$.

-

Suppose that $gcd(a,b)=d$ and $gcd(a+b,b)=g$.
Then $d$ divides $a$ and $d$ divides $b$
Then $d$ divides $(a+b)$.
Again $d$ divides $b$.
Therefore $d$ divides $gcd(a+b,b)$,or in other words $d$ divides $g.$ ..................1

Next, $g$ divides $(a+b)$ and $g$ divides $b$.
Therefore $g$ divides $(a+b)-b$ or,$g$ divides $a$.
Again $g$ divides $b$.
Therefore $g$ divides $gcd(a,b)$ or in other words $g$ divides $d.$ ....................2

From 1 and 2 we can claim that $d$ divides $g$ as well as $g$ divides $d.$
This implies that $g=d.$

Therefore we have already proved the fact for t=1.
Now assume that the fact is true for t=n where n is a natural number.

Then by induction hypothesis $gcd(a,b)$= $gcd(an+b,b)$.
Again $gcd(an+b,b)$=$gcd(b+(n+1)a,b)$
Then $gcd(a,b)$= $gcd(an+b,b)$=$gcd(b+(n+1)a,b)$ Hence $gcd(a,b)$=$gcd(b+(n+1)a,b)$,and our proof is complete.

-