ILUSTRASI BUKTI:
Anggap
dan
, maka
. Kita akan mencacah bilangan 1, 2, 3, ... , 36 dalam suatu bagan seperti di bawah:
Bilangan yang diberi warna biru adalah bilangan yang koprima dengan 36.
Dari bagan di atas, kita tahu bahwa
BUKTI:
dapat digambarkan dalam bentuk seperti di bawah:
(Lihat kolom pertama)
Dari barisan 1, 2, 3, ... ,
, ... ,
, misalkan
memiliki faktor dengan
.
Kita tulis kembali baris ke-
, yaitu:
Karena
memiliki faktor dengan
, maka semua elemen barisan di atas juga memiliki faktor dengan
. Otomatis, semua elemen tersebut juga memiliki faktor dengan
.
Karena kita ingin memperhitungkan bilangan yang koprima dengan
, maka kita tinjau
barisan yang koprima dengan
.
----
Anggap
dan
koprima.
Kita tulis kembali baris
sbb:
Karena
dan
koprima, maka semua elemen di baris
tersebut merupakan sistem komplit residu modulo
. (
Lihat teorema di kotak biru di bawah). Oleh karenanya, di baris
tersebut pasti terdapat
bilangan yang koprima dengan
.
Sistem komplit residu modulo
adalah kumpulan
integer
yang tiap elemennya akan menghasilkan kelas sisa yang berbeda-beda jika dibagi oleh
.
Contoh:
1, 2, 3, 4, 5 merupakan sistem komplit residu 5.
-1, 3, 7, 10, 16 merupakan sistem komplit residu 5.
Perhatikan bahwa:
-1
4 mod 5 ,
__ 3
3 mod 5 ,
__ 7
2 mod 5 ,
__ 10
0 mod 5 ,
__ 16
1 mod 5
Apakah (-10, 7, 18, 22, 30, 32, 46, 65) merupakan sistem komplit residu 9?
Jawab: bukan, karena jumlah elemennya hanya 8.
Apakah (-10, 7, 18, 22, 30, 32, 46, 65, 73) merupakan sistem komplit residu 9?
Jawab: bukan, karena
dan
. (kelas sisanya sama)
Teorema
Jika
adalah sistem komplit residu modulo
dan jika
adalah positif integer dimana
,
dan
adalah integer, maka:
juga merupakan sistem komplit residu modulo
BUKTI:
Asumsikan bahwa ada dua elemen yang kongruen, maka:
(
Lihat SINI) Karena
, maka:
Namun, karena kita tahu bahwa
adalah sistem komplit modulo, maka tidak mungkin ada kelas sisa yang sama antar
dan
.
Kontradiksi dengan asumsi awal, maka tidak ada dua elemen yang kongruen modulo
. Dengan demikian,
merupakan sistem komplit modulo
. ■
Karena terdapat
baris yang koprima terhadap
DAN di setiap baris tersebut terdapat
elemen yang koprima dengan
, maka dapat disimpulkan bahwa:
TERBUKTI ■
Selain bisa ditulis sebagai
, phi function juga bisa ditulis dalam bentuk
. Ini hanya merupakan masalah bentuk simbol phi saja. Ada yang curly, ada yang straight.
Phi
function memiliki banyak kegunaan, terutama di bidang kriptografi
(persandian). Namun, karena keterbatasan tempat dan waktu, kita tidak
membahasnya sekarang. Di post ini, kita hanya belajar mengenai
perhitungan phi function saja.
Lihat lanjutan post ini:
Teorema Euler