Take the 2-minute tour ×
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.

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

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

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

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.