# 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

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.

-

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.

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