Find the remainder when ## 4444^{4444} ## is divided by ## 9 ##.

[Math100]

Homework Statement

Find the remainder when ## 4444^{4444} ## is divided by ## 9 ##.
[Hint: Observe that ## 2^{3}\equiv -1\pmod {9} ##.]

Relevant Equations

None.

Observe that ## 4444\equiv 7\pmod {9} ##.
This means ## 4444^{4444}\equiv 7^{4444}\pmod {9}\equiv 7^{4+40+400+4000}\pmod {9} ##.
Now we have
\begin{align*}
&7^{4}\equiv 7\pmod {9}\\
&7^{40}\equiv (7^{4})^{10}\pmod {9}\equiv 7^{10}\pmod {9}\equiv [(7^{4})^{2}\cdot 7^{2}]\pmod {9}\equiv 7^{4}\pmod {9}\equiv 7\pmod {9}\\
&7^{400}\equiv (7^{4})^{100}\pmod {9}\equiv 7^{100}\pmod {9}\equiv (7^{4})^{25}\pmod {9}\equiv 7^{25}\pmod {9}\equiv [(7^{4})^{6}\cdot 7]\pmod {9}\equiv (7^{6}\cdot 7)\pmod {9}\equiv 7\pmod {9}\\
&7^{4000}\equiv (7^{400})^{10}\pmod {9}\equiv 7^{10}\pmod {9}\equiv 7\pmod {9}.\\
\end{align*}
Thus ## 7^{4444}\equiv (7^{4000}\cdot 7^{400}\cdot 7^{40}\cdot 7^{4})\pmod {9}\equiv 7\pmod {9} ##.
Therefore, the remainder when ## 4444^{4444} ## is divided by ## 9 ## is ## 7 ##.

 

[fresh_42]

Looks good.

Maybe you could have explained a bit more. E.g. ##4444=493\cdot 9 +7## or ##7^4=49^2\equiv 4^2\equiv 7\pmod 9## and similar for ##7^{10}## and ##7^6.##

 

[Math100]

Thank you.

 

[Orodruin]

Alternatively, using the hint:

You have already concluded that ##4444 \equiv 7 \equiv -2 ( \mod 9)##. It follows that ##4444^3 \equiv -2^3 \equiv 1( \mod 9)## and therefore ##4444^{3n}\equiv 1 (\mod 9)##.
Since ##4444 \equiv 4\cdot 4 \equiv 1 (\mod 3)## we therefore have ##4444^{4444} \equiv 4444 \equiv 7 (\mod 9)##.