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)$.