Question

Calculate $5^{2039}(mod.41).$

Answer 1

Since 41 is a prime, and 5 is prime to 41, therefore by Fermat's theorem

$5^{40}=1\left(mod41\right)$

By division algorithm,

$2039=50.40+39$

Therefore,

$5^{2039}=5^{50.40+39}=(5^{40}{)}^{50}{.5}^{39}$

$\equiv 1^{50}{.5}^{39}\left(mod41\right)$

$\equiv 5^{39}\left(mod41\right)$

To calculate $5^{39}\left(mod41\right)$, we first calculate $5^{39}\left(mod41\right)$ where $n=2,4,8,16,32$

$5^2\equiv 25\equiv -16\left(mod41\right)$

$5^4\equiv 256\equiv 10\left(mod41\right)$

$5^8\equiv 100\equiv 18\left(mod41\right)$

$5^{16}\equiv 324\equiv -4\left(mod41\right)$

$5^{32}\equiv 16\left(mod41\right)$

Now, $5^{39}\equiv 5^{32}{.5}^4{.5}^2.5=\mathrm{16.10.}(-16).5$

$\equiv 33\left(mod41\right)$

Thus $5^{2039}\left(mod41\right)=33$