Question: > 
> How to calculate $5^{2003}$ mod $13$
> 
> 
> 

using fermats little theorem

5^13-1 1 mod 13

(5^12)^166+11 mod 13

a+b modn=(a modn + b modn) modn

(1+11mod13)mod13

12 mod 13 = 12

why answer is 8 ? 

how do we calculate this

thanks

Answer: 
All modulo 13,

$$5^{2003} \equiv (5^{2})^{1001} (5)$$

$$\equiv (-1)^{1001}(5)$$

$$\equiv -5$$

$$\equiv 8$$
$5^{13-1}= 5^{12} \equiv 1 \mod 13$

$5^{2003} = 5^{12\*166 +11} = (5^{12})^{166}\*5^{11} \equiv 5^{11} \mod 13$

$5^{11}\*5 = 5^{12}\equiv 1 \mod 13$

So if $5^{11} \equiv x \mod 13$ then $5^{11}$ is a solution to $5x \equiv 1 \mod 13$. 

....

$5x \equiv 1,14,27,40 \mod 13$ so $5^{11} \equiv x\equiv 8 \equiv -5 \mod 13$.

.....

Or we could do $5^2 = 25 \equiv -1 \mod 13$ so $5^4 \equiv 1 \mod 13$ so $5^{11} \equiv 5^3 \equiv -5 \equiv 8 \mod 13$.

......

Those were trial and error. If we *had* to, we could use Euclid's algorithm to solve

$5x = 13k + 1$. 

$5x = 10k + 3k + 1$

$5(x - 2k) = 3k + 1$. Let $v = x - 2k$

$5v = 3k + 1$

$3v + 2v = 3k + 1$

$3(v - k) + 2v = 1$ Let $w = v -k$

$3w + 2v = 1$

$w + 2(w+v) = 1$. Let $z = w+v$

$w + 2z = 1$. Let $z = 0; w = 1$

$z = w+v \implies 0 = 1 + v\implies v = -1$

$w = v-k\implies 1= - 1 -k\implies k = -2$

$v = x - 2k \implies -1 = x + 4 \implies x = -5$.

So $5^{11} \equiv x \equiv- 5 \equiv 8 \mod 13$.