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.

I need to solve this question using the modular exponentiation method.

share|improve this question
2  
Have you figured out the factorization of $645$? With a view of taking advantage of either the Euler totient function (if judged helpful) or the Chinese Remainder Theorem (which is always helpful, but still leaves a bit of work to do)? –  Jyrki Lahtonen May 12 '13 at 17:39
2  
If you only want to spend a minute on it with a calculator, you can also try square-and-multiply. Has that algorithm been explained to you in class? Anyway, here it is relatively useful given that $$277=256+16+4+1,$$ so you only need to compute $13^4\equiv a\pmod{645}$, $13^{16}\equiv a^4\equiv b\pmod{645}$, $13^{64}\equiv b^4\equiv c\pmod{645}$, $13^{256}\equiv c^4\equiv d\pmod{645}$, and then calculate the residue class of $13\cdot a\cdot b\cdot d$. –  Jyrki Lahtonen May 12 '13 at 17:43

2 Answers 2

Since $\phi(645)=645(1-1/3)(1-1/5)(1-1/43)=336>277$, Euler's Totient formula isn't going to be of any use in this situation.

However, we see that \begin{align} 13^1 &\equiv 13\pmod{645}\\ 13^2 &\equiv 169\pmod{645}\\ 13^4 &\equiv 181\pmod{645}\\ 13^8 &\equiv 511\pmod{645}\\ 13^{16} &\equiv 541\pmod{645}\\ 13^{32} &\equiv 496\pmod{645}\\ 13^{64} &\equiv 271\pmod{645}\\ 13^{128} &\equiv 556\pmod{645}\\ 13^{256} &\equiv 181\pmod{645}\\ \end{align}

And since $277=256+16+4+1$, then the expression becomes

\begin{align} 13^{277} &\equiv 13^{256+16+4+1}\pmod{645}\\ &\equiv 13^{256}13^{16}13^4 13^1\pmod{645}\\ &\equiv 181 \cdot 541 \cdot 181 \cdot 13\pmod{645}\\ &\equiv 568\pmod{645}\\ \end{align}

share|improve this answer
1  
+1 But you can actually skip some of the squarings in this case. Undubtedly you noticed that $13^{256}\equiv 13^4$. The difference of the exponents is $256-4=252=42\cdot6$ happens to be divisible by all of $43-1$, $5-1$ and $3-1$, so Little Fermat tells us this right away. It may not usually be worth our while to look for short cuts such as this, for there may not be any. Explaining it afterwards is, of course, still fun! –  Jyrki Lahtonen May 12 '13 at 19:37
    
Nice! I totally missed that, but completely should have picked up on it, since (as you said) I did notice that $13^{256}\equiv 13^4$, and I was even wondering about a way to exploit it. Maybe next time :-) –  Lee May 12 '13 at 20:34

Using Carmichael Function, $\lambda(645)=$lcm $(\lambda(3),\lambda(5),\lambda(43))=$lcm$(2,4,42)=84$

Now, $277\equiv25\pmod {84}\implies 13^{277}\equiv13^{25}\pmod{645}$

Now, $25=2^4+2^3+1$ $\implies 13^{25}\equiv 13^1\cdot13^8\cdot 13^{16}\pmod{645}\equiv13\cdot511\cdot541\equiv13(-134)(-104)\equiv568$

share|improve this answer

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.