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.

This question already has an answer here:

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

marked as duplicate by user26486, Joel Reyes Noche, graydad, user91500, Micah Jun 28 at 4:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

$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

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

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

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

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