Relatif Prima dan Rumus Modulo

Relatif Prima

Suatu pasangan bilangan $(m,~n)$ disebut relatif prima jika dan hanya jika GCD ($m$, $n$) = 1 dengan GCD adalah pembagi terbesar. Contoh, apakah $(6,~3)$ relatif prima?, jawabnya tidak karena pembagi terbesarnya adalah 3. Pengertian GCD dan FPB hampir sama, bedanya pada FPB, hasil FPB tidak boleh 1, sedangkan GCD boleh hasilnya 1.

Banyak bilangan asli dari 1 sampai $(n-1)$ yang relatif prima dengan $n$ dinotasikan dengan $\phi (n)$. Berikut ini diberikan rumus $\phi (n)$.

$$\phi (p)=p-1$$ dan $$\phi (p^n)=p^n-p^{n-1}$$ serta $$\phi(p^n.q^m)=\phi(p^n).\phi(q^m)$$ dengan $p$ dan $q$ adalah bilangan prima, serta $m$ dan $n$ adalah bilangan asli.

Contoh:
$\phi(24)=...$
Jawab:
$24=2^3.(3)$ maka $$\phi(24)=\phi(2^3).\phi(3)$$ $$=(2^3-2^2).(3-1)$$ $$=4.(2)=8$$ Jadi, $\phi(24)=8$ yang berarti banyak bilangan asli yang lebih kecil dari 24 dan relatif prima terhadap 24 yaitu sebanyak 8 bilangan.

Rumus Modulo

Diberikan rumus modulo sebagai berikut:

$$a^{\phi(b)}(\text{mod }b)\equiv 1$$ jika dan hanya jika GCD ($a$, $b$) = 1.

Baca juga: Pengertian Modulo.

Contoh:
Berapa sisa pembagian $\displaystyle 3^{2023}$ dibagi 8?
Jawab:
Karena GCD(3, 8)=1 maka: $$\phi(8)=\phi(2^3)$$ $$\phi(8)=2^3-2^2=4$$ sehingga, $$3^4(\text{mod }8)\equiv 1$$ Karena 2023 dibagi 4 bersisa 3, maka: $$3^{2023}\equiv 3^3(\text{mod }8)$$ $$27(\text{mod }8)\equiv 3$$ Jadi, sisa pembagian $\displaystyle 3^{2023}$ dibagi 8 adalah 3.