7
$\begingroup$

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!

  • 1
    @Arturo Alright. :) Th$a$nks for ed$i$ting it $f$or me!2011-03-08

6 Answers 6

1

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.

23

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

  • 2
    @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$2011-05-07
12

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?

  • 0
    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!2011-03-08
6

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

  • 0
    @Arturo: I didn't know that \pmod exists. Have edited accordingly.2011-03-08
5

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.

3

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

  • 1
    great!!!!!!!!!!!2011-03-12