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.

The Problem: ( 270 + 370 ) is divisible by which number? [ 5, 13, 11 , 7 ]


Using Fermat's little theorem it took more than the double of the indicated time limit. But I would like to solve it quickly as I am preparing for an exam, that would require us to solve each MCQs to be solved in 4 minutes on an average.

Thanks in advance.

share|improve this question
    
possible duplicate of Show that 13 divides $2^{70}+3^{70}$. –  Aryabhata May 7 '11 at 16:38
add comment

5 Answers 5

up vote 11 down vote accepted

$$2^{70} + 3^{70} = (2^2)^{35} + (3^2)^{35} = (2^2 + 3^2) M$$ and hence $$\left( 2^2 + 3^2 \right) | \left( 2^{70} + 3^{70} \right)$$ Note that $\left( a+b \right)$ divides $\left( a^n + b^n \right)$ when $n$ is odd. (By remainder theorem.)

share|improve this answer
add comment

$a+b$ divides $a^{2n+1}+b^{2n+1}$ so the answer is $2^2+3^2=13$, since $2^{70}+3^{70}=4^{35}+9^{35}$.

share|improve this answer
add comment

If you are sure that exactly one divisor in your list will work, then you can use the tricks give by the other respondents. If you want to be able to calculate divisibility in general you can use constant-specific tricks to speed things up, but it will depend on your speed with arithmetic, your memorization of various powers, etc, to make it go fast.

Example: $2^{70} \bmod 5$. We know that $2^{2} = -1 \bmod 5$, so $2^{70} = -1$. That takes just a few seconds without paper. Now $3^2 = -1 \bmod 5$ so $3^{70} = -1 \bmod 3$ also. Therefore $2^{70} + 3^{70} = -2 \bmod 5$.

It gets harder for the other divisors, but still doable within 4 mins.

share|improve this answer
add comment

Besides noticing $\ 2^2+3^2\ |\ 2^{70}+3^{70}\ $ here is another quick way. $\:$ Mod $\rm\:m = 5,7,13\:$ we have $\rm\: x\not\equiv 0\ \Rightarrow\ x^{12} \equiv 1\ \Rightarrow\ x^{70}\equiv x^{-2}\:.\ $ So $\rm\ 2^{70} + 3^{70}\equiv 1/4 + 1/9 \equiv 13/36\equiv 0\iff m = 13\:.$

share|improve this answer
add comment

If you forget FLT, you can just look for the cycle: $\pmod 5, 2^1=2, 2^2=4, 2^3=3, 2^4=1, \text{ so } 2^{70}=2^{68}2^2=4$ and so on. Not elegant, but effective, and probably within the time.

share|improve this answer
    
Or one can unify the cycle search by noting that $\rm\:lcm(\phi(5),\phi(7),\phi(13))\ =\ lcm(4,6,12)\ = 12\:,\: $ so the moduli $\:5,7,13\:$ all have cycle $12\:.\:$ This immediately yields the solution - see my answer. –  Bill Dubuque May 7 '11 at 18:19
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.