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

Mod the gcd $\rm\,d\!:\,$ $\rm\ \color{#0a0}{7^{78} \equiv -3}\ $ so $\ 0\ \equiv\ 7(\color{#0a0}{7^{78}})+5\ \equiv\ 7(\color{#0a0}{-3})+5\ \equiv -16,\ $ so $\rm\ d\mid16$

Mod $8$ both args are $\equiv 4\,$ by $\,7\equiv -1$ so the gcd $\rm \,d = \smash{(4\!+\!8i,4\!+\!8j) = 4\,\underbrace{(1\!+\!2i,1\!+\!2j)}_{\rm\color{#c00}{\large =\ k\ odd}}}$

So for $\,\rm\color{#c00}{odd\ k}\,$ the gcd $\rm\, d = 4\,\color{#c00}k\mid 16,\ $ so $\rm\ k = 1\,$ so $\rm\,d = 4$.

Remark $\ $ Note how the calculations become more intuitive by employing modular aithmetic. 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.