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`.