Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
$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
up vote 10 down vote accepted

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

share|cite|improve this answer
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}$.

share|cite|improve this answer
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)}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.