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