Question

Determine n betwen 0 and 8 such that 1111^2222= n mod 9

Answer 1

Note that 1111 is not divisible by 3, so it follows that $(1111,9)=1$ (they are coprime). Given that $\varphi(9)=6$, where $\varphi$ is the Euler totient/phi function, and that

$2222=6(370)+2$

we can then write

$1111^{2222}\equiv1111^{2+6(370)}\equiv1111^2(1111^6)^{370}\mod9$

By Euler's theorem, we have

$1111^{\varphi(9)}\equiv1111^6\equiv1\mod9$

and so

$1111^{2222}\equiv1111^2\mod9$

Note that

$1111\equiv9(123)+4\equiv4\mod9$

which means

$1111^{2222}\equiv1111^2\equiv4^2\equiv16\equiv7\mod9$

so $n=7$.