Let $a^{2c}\bmod n=(a^c)^2\bmod n$ and $a^{2c+1}\bmod n=a\cdot(a^c)^2\bmod n$. For $a=7,\ b=17$ and $n=561$, what is the value of $a^b\bmod n$?

We have to find:

$7^{17}\bmod 561$

Now,

$7^2=49$

$7^4=49^2=2401$

$2401\bmod 561=157$

So,

$7^4\bmod 561=157$

Now,

$7^8\bmod 561=157^2\bmod 561$

$157^2=24649$

$24649\bmod 561=526$

So,

$7^8\bmod 561=526$

Now,

$7^{16}\bmod 561=526^2\bmod 561$

$526^2=276676$

$276676\bmod 561=103$

So,

$7^{16}\bmod 561=103$

Now,

$7^{17}\bmod 561=7^{16}\times 7\bmod 561$

$=103\times 7\bmod 561$

$=721\bmod 561$

$=160$