6
$\begingroup$

Find remainder when dividing $9^{{10}^{{11}^{12}}}-5^{9^{10^{11}}} \hspace{1cm} \text{by} \hspace{1.2cm} 13.$

I tried transforming these who numbers separately to form $13k+n$ but failed.

  • 7
    $9^3 \cong 1 \mod{13}$, so $10^{11^{12}} \cong 1 \mod 3$, so $9^{10^{11^{12}}} \cong 9 \mod 13$ ...2012-02-16

3 Answers 3

9

$\large 9^3\equiv1\implies 9^{\color{Blue}{10}^{11^{12}}\color{Blue}{\bmod\; 3}}\equiv9^{\color{Blue}1^{11^{12}}}\equiv 9 \mod 13 $

$\large 5^4\equiv1\implies 5^{\color{Red}9^{10^{11}}\color{Red}{\bmod\; 4}}\equiv 5^{\color{Red}1^{10^{11}}}\equiv 5 \mod 13$

$\large \therefore\quad 9^{10^{11^{12}}}-5^{9^{10^{11}}}\equiv9-5\equiv4\mod13 $

  • 0
    @Lazar $a^b\equiv 1\pmod c \implies a^x\equiv a^{x-b\lfloor x/b\rfloor}\equiv a^{x\;\bmod\; b} \pmod c$2012-02-17
5

Write this number as $9^N-5^M$.

Since $3^3=1\pmod{13}$, $9^3=1\pmod{13}$. Since $10=1\pmod{3}$ and $N$ is a power of $10$, $N=1\pmod{3}$. Hence $9^N=9\pmod{13}$.

Since $5^2=-1\pmod{13}$, $5^4=1\pmod{13}$. Since $9=1\pmod{4}$ and $M$ is a power of $9$, $M=1\pmod{4}$. Hence $5^M=5\pmod{13}$.

Finally, $9^N-5^M=9-5=4\pmod{13}$.

  • 0
    Thanks a lot, I feel like a stupid :P2012-02-16
1

Hint: put $\rm A,B = 3,5\:$ in $\rm\ A^3 \equiv 1,\ B^2\equiv -1\ \Rightarrow\ A^{2\:(1+3m)^{J}}\! - B^{\:(1+4n)^K} \equiv A^{2\cdot 1^J}\!-B^{\:1^K}\equiv\: A^2 - B$

Note $\:$ Proficiency stems from mastery of such exponent congruence arithmetic, viz.

$\rm A^N\equiv 1\ \Rightarrow\ A^K\equiv A^{(K\ mod\ N)} $

Proof $\:$ By the Division Algorithm $\rm\ K = R + N\:Q,\ $ for $\rm\ R = (K\ mod\ N),\:$ therefore

$\rm A^K \equiv\ A^{R+NQ}\equiv A^R (A^N)^Q\equiv A^R 1^Q \equiv A^R\equiv A^{(K\ mod\ N)}$