Pembuktian akan dibagi ke tiga kasus.

Kasus 1:

Kasus \( n = 3p \)
Jika \( n = 3p \) maka \( n^2 = 9p^2 \)

Sangat jelas \( 9p^2 \equiv 0 \pmod{3} \)

Kasus 2:

Kasus \( n = 3p+1 \)
Jika \( n = 3p+1 \) maka
\( n^2 = 9p^2 + 6p + 1 \)
\( n^2 = 3(3p^2 + 2p) + 1 \)

Sangat jelas \( 3(3p^2 + 2p) + 1 \equiv 1 \pmod{3} \)

Kasus 3:

Kasus \( n = 3p+2 \)
Jika \( n = 3p+2 \) maka
\( n^2 = 9p^2 + 12p + 4 \)
\( n^2 = 9p^2 + 12p + 3 + 1 \)
\( n^2 = 3(3p^2 + 4p + 1) + 1 \)

Sangat jelas \( 3(3p^2 + 4p + 1) + 1 \equiv 1 \pmod{3} \)

Kesimpulan

Jika \( n \) adalah bilangan kelipatan 3, maka sisa pembagian \( n^2 \) oleh 3 adalah 0
Jika \( n \) bukan bilangan kelipatan 3, maka sisa pembagian \( n^2 \) oleh 3 adalah 1

Secara formal:

\( n^2 \equiv \begin{cases} 0 \pmod{3} & \text{jika } n \text{ kelipatan } 3\\ 1 \pmod{3} & \text{jika } n \text{ bukan kelipatan } 3 \end{cases} \)