# Find remainder when dividing $9^{{10}^{{11}^{12}}}-5^{9^{10^{11}}}$ by $13$.

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.

-
$9^3 \cong 1 \mod{13}$, so $10^{11^{12}} \cong 1 \mod 3$, so $9^{10^{11^{12}}} \cong 9 \mod 13$ ... – martini Feb 16 '12 at 11:29

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

-
I'm not sure I understand the way you're handling "mod" inside the equations. How can you just mix modulo 3 and 4 when you're going with modulo 13 on the whole line? Sorry, could you explain more? – Lazar Ljubenović Feb 17 '12 at 10:19
@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$$ – anon Feb 17 '12 at 10:25

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

-
Didier, sorry but I still don't understand how are you writing "Hence $9^N=9\pmod{13}$". – Quixotic Feb 16 '12 at 17:23
@Foool: For every integer $k$, $9^{3k+1}=(9^3)^k\cdot9=1^k\cdot9=9\pmod{13}$. And $N=3k+1$ for some $k$ hence $9^N=9\pmod{13}$. – Did Feb 16 '12 at 18:29
Thanks a lot, I feel like a stupid :P – Quixotic Feb 16 '12 at 19:31

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

-