Figuring out a high power modulo

Question

Could you walk me through the most efficient way to solve this modulo?

$276^{247} \mod 323$

Answer 1

First factor $323$ which is not divisible by $2,3,5$ or $11$ and probably not by $7, 13,$ or $17$. $323 = 28*10+ 43=31*10 + 13=34*10 - 17$ so $343 = 17*(20-1) = 19$.

$\phi(343) = \phi(17)\phi(19) = 16*18 = (20-2)(20-4) = 400 -120 + 8 = 288$.

$276 = 2*138=4*69=4*3*23$ so $\gcd(276,343) = 1$.

So $276^{288} \equiv 1 \mod 323$

Argh. Second go.. Chinese remainder theorem.

$276^{247} \mod 17 \equiv ...$ Dang, I hate not having calculators. $276 = 17*10 + 106 = 17*11 + 89 = 17*11 + 34+34 + 21\equiv 4 \mod 17$. and $247\mod 16 \equiv 160 + 87 \equiv 32+32+32 - 9 \equiv 7\mod 16$ so $276^{247}\equiv 4^7 \equiv 16^3*4\equiv -4\mod 17$.

$276\mod 19 = 190 + 86 = 190 + 76 + 10 \equiv 10\mod 19$ while $247\mod 18 = 180 + 67= 180 + 72-5\equiv 13 \mod 18$. So $276^{247}\equiv 10^13 \mod 19 \equiv 100^6*10 \equiv 5^6*10 \equiv 25^3*10 \equiv 6^3*10\equiv 36*6*10 \equiv -2*60\equiv -2*3 \equiv -6 \mod 19$.

So $276^{247} \equiv -4 + k17 =-6 + m19 \mod 323$ $k=1=m \implies -4+k17 = -6 + 19m = 13$.

So $276^{247} \equiv 13 \mod 323$.