Theorema Euler

Dalam teori bilangan, teorema Euler (juga dikenal sebagai teorema Fermat-Euler) menyatakan bahwa jika n adalah bilangan bulat positif, dan a adalah prima relatif dengan n, maka
aφ(n) = 1 (mod n)
di mana φ(n) melambangkan fungsi phi Euler.

Langsung ke contoh soal :

Contoh 1:
1, 2, 4, 5, 7, 8 adalah sistem residu tereduksi modulo 9.
 Jumlah bilangannya harus 6. .yaitu 1,2,4,5,7,,8
Perhatikan juga bahwa bilangan-bilangan itu harus koprima dengan 9, dan mempunyai kelas sisa yang berbeda satu sama lain.

Contoh 2:
-5, 7, 14, 19, 29, 35 adalah sistem residu tereduksi modulo 9.
Perhatikan bahwa semua bilangannya koprima dengan 9.
Tiap bilangan juga memiliki kelas sisa yang berbeda:
-5 = 4 (mod 9
7= 7 (mod 9)
14=  5 (mod 9)
19 = 1 (mod 9
29 = 2 (mod 9)
35=  8 (mod 9)

Bukti Theorema Euler

Teorema
Jika ada   adalah sistem residu yang tereduksi modulo n ,
dan a  adalah integer positif dimana  , maka:
 juga merupakan sistem residu yang tereduksi modulo n

BUKTI


Karena   juga merupakan sistem residu tereduksi modulo n , maka tentunya sisa residu positif dari  adalah  dalam urutan tertentu (acak).
Dengan mengalikan elemen-elemen tersebut, kita dapatkan:




Karena  , maka


               

TERBUKTI. ■.