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

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.

Note: This is exam prep, not homework.

-
note that gcd(a,b)=gcd(a-b,b) as you know, but also gcd(a,b)=gcd(a mod b, b). This helps a lot when the numbers are (or become) very different in size. – Ross Millikan Dec 9 '10 at 16:45

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.

-
Cool, thanks. I seem to have been approaching it the wrong way. – Cam Dec 9 '10 at 5:57
Ah, you edit caught up with my answer. – Arturo Magidin Dec 9 '10 at 5:57
@Arturo Magidin: but yours was prettier. I'll fix mine. – Ross Millikan Dec 9 '10 at 6:01

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.

-
This is an interesting approach. Thanks for adding it. – Cam Dec 9 '10 at 7:05

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.

-