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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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