Show that $\gcd(7^{79}+5,7^{78}+3) = 4$

Question

How can I prove that $\gcd(7^{79}+5,7^{78}+3) = 4$ ? This was a question on a past exam, so the naive euclidean algorithm doesn't seem to suffice.

I'm not really sure where to start with this.

Note: This is exam prep, not homework.

Answer 1

For a first step, $7^{79}+5 - 7*(7^{78}+3) = -16$, which gets you a long way. Then you only need to study the factors of 2 in the numbers.

Answer 2

Modulo the gcd: $\rm\ 7^{78}\ \equiv -3\ \Rightarrow\ 0\ \equiv\ 7^{79}+5\ \equiv\ 7(-3)+5\ \equiv -16\:,\ $ i.e. the gcd dvides $16\:$.

Now $\rm\ mod\ 8:\ 7^{78}+3\ \equiv\ (-1)^{78}+3\ \equiv\ 4\ \equiv\ (-1)^{79}+5\ \equiv\ 7^{79}+5\:,\ $ i.e. $\ $ gcd $\rm\equiv 4\ (mod\ 8)$

Hence:$\ $ gcd $\rm = 4 + 8\ k\ $ divides $16\:$ implies $\rm\ k = 0\:,\ $ so $\ $ gcd $ = 4\:$.

Notice how the calculations become more intuitive by working in various rings $\rm\ \mathbb Z/m\:.$ Doing such allows us to reuse our well-honed intuition of arithmetic operations (ring laws), versus the much more cumbersome $\ $ and $\ $ much less intuitive divisibility relation, i.e. calculating in equational algebras is simpler than calculating in relational algebras, so whenever a problem can be converted from relational to equational it usually yields a simplification.

Answer 3

Since $\gcd(a,b)=\gcd(a-b,b)$, $$\begin{align} \gcd(7^{79}+5,7^{78}+3) &=\gcd(7\cdot 7^{78}+5-7^{78}-3,7^{78}+3) \\ &=\gcd(6\cdot 7^{78}+2,7^{78}+3) \\ &=\gcd(6\cdot 7^{78}+2-7^{78}-3,7^{78}+3) \\ &=\gcd(5\cdot 7^{78}-1,7^{78}+3) \\ &\vdots \\ &=\gcd(7^{78}-13,7^{78}+3) \\ &=\gcd(7^{78}-13,7^{78}+3-7^{78}+13) \\ &=\gcd(7^{78}-13,16) \\ \end{align}$$

From there, I'd determine the remainder when $7^{78}$ is divided by 16 and use that to see how $7^{78}-13$ compares to 16.