Proof $\gcd(a, 18) = \gcd(a + 18,\gcd(a, 18))$

Question

I know there's some kind of theorem I'm missing here. How can one prove the above?

Cheers!

Answer 1

Let $\gcd(a,18)=d$. Since $d|a$ and $d|18$, we have $d|a+18$. Thus the $\gcd(a+18,d)=d$ since $d$ divides both terms.

Answer 2

In short, they are equal because LHS divides RHS and RHS divides LHS. This is a very common argument when proving equalities on gcd.

Answer 3

$\gcd(a,18) | a$ and $\gcd(18) | 18$, so $\gcd(a,18) | (a+18)$. Trivially $\gcd(a,18) | \gcd(a,18)$, so $\gcd(a,18) | \gcd(a+18, \gcd(a,18))$ as we have shown the left hand divides both of the numbers, and the $\gcd$ on the right is the largest (in the divisibility sense) of the common divisors.

$\gcd(a+18,\gcd(a,18)) | \gcd(a,18) $ and $\gcd(a,18) | a$ and $\gcd(a,18) | 18$, so transitivity gives $\gcd(a+18,\gcd(a,18)) | a$ and $\gcd(a+18,\gcd(a,18)) | 18$. As it divides both we get by maximality of the $\gcd$ that $\gcd(a+18,\gcd(a,18)) | \gcd(a,18)$. So these numbers divide each other so they differ up to sign, and and $\gcd$'s are positive, they are equal.

Answer 4

Let $c$ be any common divisor of $a$ and $b$; then $c$ is a divisor of both $a+b$ and of $\gcd(a,b)$.

Conversely, if $c$ is a common divisor of $a+b$ and of $\gcd(a,b)$, then it is a divisor of $b$, say $b=cd$; then $a+b=ce$ says $a=ce-cd=c(e-d)$ and so $c$ is also a divisor of $a$.

So the set of divisors of $a$ and $b$ is the same as the set of common divisors of $a+b$ and $\gcd(a,b)$.

Now just set $b=18$.