You have to have a calculator that keeps the fractional part of an integer, when dividing by a number: Frac[11^850 / 1,643] =0.49360925136944613511868533171029 x 1,643=811
+26387 I want to caculate 11power 850 mod 1643
\(\begin{array}{|rcll|} \hline && 11^{850} \pmod{1643} \\ & \equiv & 11^{4\cdot 212+2} \pmod{1643} \\ & \equiv & (11^4)^{212}\cdot 121 \pmod{1643} \quad & | \quad 11^4\pmod{1643} &\equiv& -146 \pmod{1643} \\ & \equiv & (-146)^{212}\cdot 121 \pmod{1643} \\ & \equiv & (-146)^{2\cdot 106}\cdot 121 \pmod{1643} \\ & \equiv & [(-146)^2]^{106}\cdot 121 \pmod{1643} \quad & | \quad (-146)^2\pmod{1643} &\equiv& -43 \pmod{1643} \\ & \equiv & (-43)^{106}\cdot 121 \pmod{1643} \\ & \equiv & (-43)^{4\cdot 26+2}\cdot 121 \pmod{1643} \\ & \equiv & [(-43)^4]^{26}\cdot (-43)^2 \cdot 121 \pmod{1643} \quad & | \quad (-43)^4 \pmod{1643} &\equiv& -282 \pmod{1643} \\ & \equiv & (-282)^{26}\cdot (-43)^2 \cdot 121 \pmod{1643} \quad & | \quad (-43)^2 \pmod{1643} &\equiv& 206 \pmod{1643} \\ & \equiv & (-282)^{26}\cdot 206 \cdot 121 \pmod{1643} \\ & \equiv & (-282)^{2\cdot 13}\cdot 206 \cdot 121 \pmod{1643} \\ & \equiv & [(-282)^2]^{13} \cdot 206 \cdot 121 \pmod{1643} \quad & | \quad (-282)^2 \pmod{1643} &\equiv& 660 \pmod{1643} \\ & \equiv & 660^{13} \cdot 206 \cdot 121 \pmod{1643} \\ & \equiv & 660^{2\cdot6 + 1} \cdot 206 \cdot 121 \pmod{1643} \\ & \equiv & (660^2)^6\cdot 660 \cdot 206 \cdot 121 \pmod{1643} \quad & | \quad 660^2\pmod{1643} &\equiv& 205 \pmod{1643} \\ & \equiv & 205^6\cdot 660 \cdot 206 \cdot 121 \pmod{1643} \quad & | \quad 660 \cdot 206 \cdot 121\pmod{1643} &\equiv& -199 \pmod{1643} \\ & \equiv & 205^6\cdot (-199) \pmod{1643} \\ & \equiv & 205^{2\cdot 3}\cdot (-199) \pmod{1643} \\ & \equiv & (205^2)^3\cdot (-199) \pmod{1643} \quad & | \quad 205^2\pmod{1643} &\equiv& -693 \pmod{1643} \\ & \equiv & (-693)^3\cdot (-199) \pmod{1643} \\ & \equiv & (-693)^{2+1}\cdot (-199) \pmod{1643} \\ & \equiv & (-693)^2\cdot(-693)\cdot (-199) \pmod{1643} \quad & | \quad (-693)\cdot (-199)\pmod{1643} &\equiv& -105 \pmod{1643} \\ & \equiv & (-693)^2\cdot(-105) \pmod{1643} \quad & | \quad (-693)^2\pmod{1643} &\equiv& 493 \pmod{1643} \\ & \equiv & 493\cdot(-105) \pmod{1643} \\ & \equiv & 493\cdot(-105) \pmod{1643} \quad & | \quad 493\cdot(-105) \pmod{1643} &\equiv& -832 \pmod{1643} &\equiv& 811 \pmod{1643} \\ & \equiv & 811 \pmod{1643} \\ \hline \end{array}\)
