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