Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
6  
$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
add comment

3 Answers

up vote 8 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|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
add comment

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.