Can this number theory MCQ be solved in 4 minutes?

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.

-
possible duplicate of Show that 13 divides $2^{70}+3^{70}$. –  Aryabhata May 7 '11 at 16:38

5 Answers

$$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.)

-

$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}$.

-

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.

-

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\:.$

-

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.

-
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