7
$\begingroup$

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?

7 Answers 7

8

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)$

  • 1
    @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.2011-02-23
2

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$.

  • 0
    In your last sentence, you mean b+at ofcourse.2011-02-23
1

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

0

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'.

0

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)$.

0

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.

-1

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 
  • 0
    @Kirk: Yes, I just realized that. Hopefully the OP has enough hints by now.2011-02-23