# Use the modular exponentiation algorithm to find $13^{277} \pmod {645}$

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

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

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}

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

-