Hendra Jaya Napitupulu | Sisa Pembagian 2 pangkat n Oleh 15

Sisa Pembagian $2^{n}$ Oleh 15

Buktikan bahwa sisa pembagian $2^{n}$ oleh 15 selalu 1, 2, 4, 8 dimana $n \geq 0$ dan $n$ adalah bilangan bulat

Secara formal:

Buktikan bahwa $2^{n} \equiv {1, 2, 4, 8} (\mod 15)$ dimana $n \geq 0$ dan $n \in ℤ$

bukti

Pembuktian akan dibagi ke empat kasus, yaitu:

Kasus $n = 4 p$
Kasus $n = 4 p + 1$
Kasus $n = 4 p + 2$
Kasus $n = 4 p + 3$

dimana $p \geq 0$ dan $p \in ℤ$

Kasus 1:

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

Jadi, jika $n = 4 p$ maka $2^{n} \equiv 1 (\mod 15)$

Kasus 2:

Jika $n = 4 p + 1$ maka

$2^{n} = 2^{4 p + 1}$
$2^{n} = 2 \cdot 2^{4 p}$

Karena dari kasus 1 sudah diketahui bahwa $2^{4 p} \equiv 1 (\mod 15)$ maka

$2^{n} = 2 \cdot 2^{4 p}$
$2^{n} \equiv 2 \cdot 1 (\mod 15)$
$2^{n} \equiv 2 (\mod 15)$

Jadi, jika $n = 4 p + 1$ maka $2^{n} \equiv 2 (\mod 15)$

Kasus 3:

Dengan menggunakan teknik yang sama seperti kasus 2, jika $n = 4 p + 2$ maka $2^{n} \equiv 4 (\mod 15)$

Kasus 4:

Dengan menggunakan teknik yang sama seperti kasus 2, jika $n = 4 p + 3$ maka $2^{n} \equiv 8 (\mod 15)$

Kesimpulan

Memang betul, sisa pembagian $2^{n}$ oleh 15 selalu 1, 2, 4, 8