Take the 2-minute tour ×

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.

share|improve this question
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
add comment

3 Answers

up vote 7 down vote accepted

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.

share|improve this answer
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
add comment

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.

share|improve this answer
This is an interesting approach. Thanks for adding it. –  Cam Dec 9 '10 at 7:05
add comment

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.

share|improve this answer
add comment

Your Answer


