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

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.

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

 
discard

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.