Beräkna rest

$3^{33} (mod 5)={\left(3^3\right)}^{11} (mod 5)={27}^{11} (mod 5)\equiv {32}^{11 }(mod 5)={\left(2^5\right)}^{11} (mod 5)$=${\left(2^5\right)}^6\times {\left(2^5\right)}^5 (mod 5) = {\left(2^5\right)}^6 (mod 5) * {\left(2^5\right)}^5 (mod 5)=(2^5 {(mod 5))}^6*(2^5 {(mod 5))}^5$=$(32 {(mod 5))}^6*(32 {(mod 5))}^5$OBS! $32 mod 5 =2$ $\Rightarrow 2^6*2^5 (mod 5)=2^{11} (mod 5)=2^6 (mod 5) *2^5 (mod 5)=64 (mod 5) * 32 (mod 5)=$$(4*2) (mod 5)=8 (mod 5)=3$

Det man verkligen vill ha är exponenter som är kongruenta med $\pm 1$ för då försvinner ju allt. Här har vi faktiskt en sådan exponent, $3^2 = 9 \equiv -1 \pmod 5$, så vi vill tidigt få fram $3^2$ för att förenkla snabbt. 

Vi kan skriva $3^{33} = 3\cdot 3^{32}=3\cdot 9^{16} \equiv 3\cdot (-1)^{16} = 3 \pmod 5.$ 

Om en sådan exponent inte finns kan man hitta de senare, t.ex när du skrivit om till exponenter av $2$ så kan man t.ex. använda att $2^4 = 16 \equiv 1$.

Som #4 eller notera att 3^481=80+1 som ger rest 1

3^33 = 3*3^32 = 3(3^4)^8 == 3*1^8 = 3*1 = 3 (mod 5)

("==" = kongruent med)