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?
 A: 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)$
A: 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$.
A: $$\displaystyle ax+by = a(x-ty)+(b+at)y$$
A: 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)$. 
A: 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'.
A: 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.
A: 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

