# Show that 13 divides $2^{70}+3^{70}$

Show that $13$ divides $2^{70} + 3^{70}$.

My main problem here is trying to figure out how to separate the two elements in the sum, and then use Fermat's little theorem. So how can I separate the two?

Thanks!

-
Argh, typo! Should be 3^70. Same exponent, different base. Thanks! –  Christoph Mar 8 '11 at 3:34
Please don't rely on the subject for content; the body should be self-contained. –  Arturo Magidin Mar 8 '11 at 3:38
@Arturo Alright. :) Thanks for editing it for me! –  Christoph Mar 8 '11 at 3:48

Compute $2^{70}$ and $3^{70}$ modulo $13$ separately (e.g., using Fermat's Little Theorem). If $2^{70}\equiv a\pmod{13}$ and $3^{70}\equiv b\pmod{13}$, then what is $2^{70}+3^{70}$ congruent to modulo 13?

-
Aah. I knew I could add them up easily but was coming from the wrong direction, trying to do it backwards. Thanks for clearing that up! –  Christoph Mar 8 '11 at 3:49

Okay, I'm on a little different wavelength so I'll turn my comment into an answer.. if $n$ is odd the polynomial $x + y$ divides $x^n + y^n$. So letting $x = 2^2, y = 3^2,$ and $n = 35$ you get that $13 = 2^2 + 3^2$ divides $2^{70} + 3^{70}$.

-
now there's a creative solution! nice to see someone who doesn't just immediately do brute force mods. –  Eugene Bulkin Mar 12 '11 at 6:00
@Eug But its simplest proof is by mod, viz. mod $\rm\ A+B\::\ \ A\:\equiv\: -B\ \Rightarrow\ A^{2\:N\:+\:1}\equiv\: -B^{2\:N\:+\:1}\quad\quad\quad\quad\quad$ –  Bill Dubuque May 7 '11 at 18:38

$2^{12} \equiv 1 \pmod{13}$ and $3^{12} \equiv 1 \pmod{13}$ by Fermat's Little Theorem.

Hence, $2^{72} \equiv 1 \pmod{13}$ and $3^{72} \equiv 1 \pmod{13}$

$2^{72} \equiv 1 \pmod{13} \Rightarrow 2^{72} \equiv 40 \pmod{13} \Rightarrow 2^{70} \equiv 10 \pmod{13}$

$3^{72} \equiv 1 \pmod{13} \Rightarrow 3^{72} \equiv 27 \pmod{13} \Rightarrow 3^{70} \equiv 3 \pmod{13}$

Hence, you get the result.

-
Thanks! Walking through it like that was very helpful to figure out just what kinds of operations are allowed with congruences. Thanks! –  Christoph Mar 8 '11 at 4:01
@Christoph: You are allowed to cancel since gcd(2,13) = 1 = gcd(3,13) –  user17762 Mar 8 '11 at 4:04
@Sivaram: Do you use \bmod on purpose rather than \pmod? Not criticising, just wondering; I know a lot of LaTeX users of long standing that are suprised to find out that \pmod exists... –  Arturo Magidin Mar 8 '11 at 4:11
Oooh yeah! Division works because inversion works, which only works for mod p, p is prime. Correct? –  Christoph Mar 8 '11 at 4:11
@Arturo: Nice, I didn't know about \pmod. Thanks! –  Christoph Mar 8 '11 at 4:13

HINT $\rm\:$ Little Fermat shows $\rm\ mod\ 13:\ \ 2^{70} + 3^{70}\ \equiv\ 2^{-2} + 3^{-2}\ \equiv\ 1/4+1/9\ \equiv 13/36\ \equiv\ 0$

NOTE $\$ For a slight generalization see here.

-

The "quick" way to do this is as follows:

$2^{6}=64=-1$(mod 13), $3^{3}=1$ (mod 13)

Hence you have $2^{70}=(2^{6})^{11}*2^{4}=(-1)*(3)=-3$ (mod 13)

And $3^{70}=(3^{3})^{13}*3=3$ (mod 13)

Therefore the result is $-3+3=0$ (mod 13).

Fermat's little theorem implies $a^{p-1}\cong 1$ (mod p), but this may be more slick, I am not sure. Mind that Fermat's little theorem is not optimal in many cases.

The "ultra quick" way may be $2^{70}+3^{70}=3^{70}*(1+(2/3)^{70})$. Now notice $2/3=2*9=5$. And $5^2=-1$, hence $(1+(5^{2})^{25})=1+-1=0$. Therefore $2^{70}+3^{70}=0$.

-
Well, I'd say, "the ultraquick" way is the following: $\mod 13:2^{70}+3^{70} ==4^{35}+9^{35} == (4^1+9^1)x ==0$ –  Gottfried Helms Mar 12 '11 at 5:32
great!!!!!!!!!!! –  Kerry Mar 12 '11 at 22:14

So by FlT, you know that $2^{12}\equiv 1\pmod{13}$ and $3^{12}\equiv 1\pmod{13}$. So $$2^{70}+3^{70}\equiv (2^{12})^5\cdot 2^{10}+(3^{12})^5\cdot 3^{10}\equiv 2^{10}+3^{10}\pmod{13}.$$ However, again by FlT, $$2^{12}\equiv 2^{10}\cdot 2^{2}\equiv 1\pmod{13}\implies 2^{10}\equiv 2^{-2}\pmod{13}.$$ That is to say, $2^{10}$ is congruent to the multiplicative inverse of $4$ modulo $13$. You can do the same for $3^{10}$, except you will need to find the multiplicative inverse to $9$ modulo $13$. You'll see that the sum of these inverses is $0$ modulo $13$, to get your answer.

-