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