Kita tahu teorema kecil fermat menyatakan

Untuk sebarang bilangan bulat dan bilangan prima yang coprime ke berlaku

Nah..sekarang bagaimana jika modulusnya tidak prima, composite, apakah teorema kecil fermat masih berlaku?
Tidak, sebgai contohnya jika kita ambil dan ,
apakah
Tidak karena 15 tidak membagi .
Akan tetapi ada cara memodifikasi teorema kecil fermat sehingga tetap berlaku meskupun modulusnya tidak prima. Teorema fermat yang udah dimodifikasi inilah yang disebut teorema euler.

Nah..sebelum membahas teorema euler akan saya bahas mengenai fungsi euler-phi

Definisi: Fungsi phi-euler, adalah fungsi pada bilangan asli yang didefinisikan sebgai berikut

adalah banyaknya bilangan pada yang coprime ke

Contoh: karena ada 4 bilangann asli yang kurang dari 8 yang coprime ke 8 ke-4 bilangan tersebut adalah 1,3,5,7. kerna semua bilangan pada coprime ke 11.

Teorema

1. Jika prima maka
2. Jika prima dan  maka

Bukti

1. Jika prima maka semu bilangan pada coprime ke , itu artinya
2. Ada elemen pada himpunan . Elemen pada himpunan tersebut tidak coprime ke jika hanya jika dapat dibagi oleh . Elemen pada himpunan yang dapat dibagi oleh adalah

Ada sebanyak elemen yang tidak coprime ke maka banyaknya elemen yang coprime ke sebanyak

Definisi: Sistem residu tereduksi mod (reduced residue system mod ) adalah himpunan bilangan-bilangan

Yang memenuhi

1. Jika maka
2. Untuk setiap coprime ke

Dengan demikian Sistem residu tereduksi mod merepresentasikan bilangan-bilangan yang coprime ke

Contoh: dan keduanya merupakan sistem residu tereduksi mod

Lemma: Diberikan dan adalah Sistem residu tereduksi mod , berlaku:

1. Untuk semua bilangan bulat maka  merupakan sistem residu tereduksi mod .
2. Jika coprime ke maka merupakan sistem residu tereduksi mod .

Akibat: Diberikan dan adalah Sistem residu tereduksi mod , jika coprime ke dan sebarang bilangan bulat maka merupakan sistem residu tereduksi mod .

Contoh: merupakan sistem residu tereduksi mod . tmabahkan pada setiap bilangan diperoleh , sistem residu tereduksi mod lainnya, Kita tahu 6 coprime ke 25, jika kita kalikan sistem yang awal dengan 25 diperoleh istem residu tereduksi mod lainnya, terakhir juga merupakan sistem residu tereduksi mod

Selanjutnya kita bahas teorema euler

Teorema Euler: Setiap bilangan bulat dan bilangan bulat positif  yang coprime ke maka

Perhatikan jika prima maka , teorema euler berubah menjadi teorema kecil fermat. Dengan demikian kita bisa menganggap teorema euler sebagai generalisasi teorema kecil fermat.

Bukti: Ambil dan adalah Sistem residu tereduksi mod , diasumsikan termuat di .

Karena dan coprime maka  juga merupakans sistem residu tereduksi mod , Kedua sistem tersebut haruslah mempunyai hasil perkalian modulus yang sama

Karean setiap coprime ke , jika dikalikan kedua sisi dengan diperoleh

atau dengan kata lain