Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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

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|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.