Pembuktian akan dibagi ke empat kasus, yaitu:

1. Kasus \( n = 4p \)
2. Kasus \( n = 4p+1 \)
3. Kasus \( n = 4p+2 \)
4. Kasus \( n = 4p+3 \)

dimana \( p \ge 0\) dan \( p \in \mathbb{Z} \)

Kasus 1:

Jika \( n = 4p \) maka
\( 2^n = 2^{4p} \)
\( 2^n = {(2^4)}^p \)
\( 2^n = 16^p \)
\( 2^n = {(15 + 1)}^p \)
\( 2^n \equiv 1^p \pmod{15} \)
\( 2^n \equiv 1 \pmod{15} \)

Kasus 2:

Jika \( n = 4p + 1 \) maka
\( 2^n = 2^{4p+1} \)
\( 2^n = 2 \cdot 2^{4p} \)

Karena \( 2^{4p} \equiv 1 \pmod{15} \) maka:
\( 2^n \equiv 2 \cdot 1 \pmod{15} \)
\( 2^n \equiv 2 \pmod{15} \)

Kasus 3:

Dengan menggunakan teknik yang sama seperti kasus 2:
Jika \( n = 4p + 2 \) maka \( 2^n \equiv 4 \pmod{15} \)

Kasus 4:

Dengan menggunakan teknik yang sama seperti kasus 2:
Jika \( n = 4p + 3 \) maka \( 2^n \equiv 8 \pmod{15} \)

Kesimpulan

Memang betul, sisa pembagian \( 2^n \) oleh 15 selalu 1, 2, 4, 8