Teorema Euler

Kita tahu teorema kecil fermat menyatakan

Untuk sebarang bilangan bulat a dan bilangan prima p yang coprime ke a berlaku
a^{p-1}\equiv 1\pmod p

Nah..sekarang bagaimana jika modulusnya tidak prima, composite, apakah teorema kecil fermat masih berlaku?
Tidak, sebgai contohnya jika kita ambil a=2 dan n=15,
apakah 2^{14}\equiv 1\pmod {15}
Tidak karena 15 tidak membagi 16383=2^{14}-1.
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 n yang didefinisikan sebgai berikut

\phi\left(n\right) adalah banyaknya bilangan pada \left\{ 1,2,3\ldots,n-1\right\} yang coprime ke n

Contoh: \phi\left(8\right)=4 karena ada 4 bilangann asli yang kurang dari 8 yang coprime ke 8 ke-4 bilangan tersebut adalah 1,3,5,7. \phi\left(11\right)=10 kerna semua bilangan pada \left\{ 1,2,3\ldots,10\right\} coprime ke 11.

Teorema

  1. Jika p prima maka \phi\left(p\right)=p-1
  2. Jika p prima dan  n\geq1 maka \phi\left(p^n\right)=p^n-p^{n-1}

Bukti

1. Jika p prima maka semu bilangan pada \left\{ 1,2,3\ldots,p-1\right\} coprime ke p, itu artinya \phi\left(p\right)=p-1
2. Ada p^n elemen pada himpunan \left\{ 1,2,3\ldots,p^n\right\} . Elemen pada himpunan tersebut tidak coprime ke p jika hanya jika dapat dibagi oleh p. Elemen pada himpunan yang dapat dibagi oleh p adalah

1p,\:,2p\:3\cdot p,\ldots,p^{n-1}\cdot p

Ada sebanyak p^{n-1} elemen yang tidak coprime ke p maka banyaknya elemen yang coprime ke p sebanyak p^n-p^{n-1}

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

a_{1},a_{2},a_{3},\ldots,a_{\phi\left(n\right)}

Yang memenuhi

  1. Jika i\neq j maka a_{1}\not\equiv a_{j}\pmod n
  2. Untuk setiap a_i coprime ke n

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

Contoh: \left\{ 1,5,7,11\right\} dan \left\{ 11,17,-1,31\right\} keduanya merupakan sistem residu tereduksi mod 12

Lemma: Diberikan \phi\left(n\right)=k dan \left\{ a_{1},a_{2},\ldots,a_{k}\right\} adalah Sistem residu tereduksi mod n, berlaku:

  1. Untuk semua bilangan bulat m maka  \left\{ a_{1}+mn,a_{2}+mn,\ldots,a_{k}+mn\right\} merupakan sistem residu tereduksi mod n.
  2. Jika m coprime ke n maka \left\{ ma_{1},ma_{2},\ldots,ma_{k}\right\} merupakan sistem residu tereduksi mod n.

Akibat: Diberikan \phi\left(n\right)=k dan \left\{  a_{1},a_{2},\ldots,a_{k}\right\} adalah Sistem residu tereduksi mod n, jika s coprime ke n dan t sebarang bilangan bulat maka \left\{ sa_{1}+t,sa_{2}+t,\ldots,sa_{k}+t\right\} merupakan sistem residu tereduksi mod n.

Contoh: \left\{ 1,5\right\} merupakan sistem residu tereduksi mod 6. tmabahkan 12=2\times 6 pada setiap bilangan diperoleh \left\{ 13,17\right\}, sistem residu tereduksi mod 6 lainnya, Kita tahu 6 coprime ke 25, jika kita kalikan sistem yang awal dengan 25 diperoleh \left\{ 25,125\right\} istem residu tereduksi mod 6 lainnya, terakhir \left\{ 25+12,125+12\right\}=\left\{ 37,137\right\} juga merupakan sistem residu tereduksi mod 6

Selanjutnya kita bahas teorema euler

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

a^{\phi\left(n\right)}\equiv 1\pmod n

Perhatikan jika n prima maka a^{n-1}\equiv 1\pmod n, teorema euler berubah menjadi teorema kecil fermat. Dengan demikian kita bisa menganggap teorema euler sebagai generalisasi teorema kecil fermat.

Bukti: Ambil \phi\left(n\right)=k dan \left\{   a_{1},a_{2},\ldots,a_{k}\right\} adalah Sistem residu tereduksi mod n, diasumsikan a_i termuat di \left\{ 1,2,3\ldots,n-1\right\} .

Karena a dan n coprime maka  \left\{a   a_{1},aa_{2},\ldots,aa_{k}\right\} juga merupakans sistem residu tereduksi mod n, Kedua sistem tersebut haruslah mempunyai hasil perkalian modulus n yang sama

\left(aa_{1}\right)\ldots\left(aa_{k}\right)\equiv a_{1}\ldots a_{k}\pmod n

a_{k}\left(a_{1}\ldots a_{k}\right)\equiv a_{1}\ldots a_{k}\pmod n

Karean setiap a_i coprime ke n, jika dikalikan kedua sisi dengan a_{1}^{-1}\ldots a_{k}^{-1} diperoleh

a^{k}\equiv 1\pmod n atau dengan kata lain  a^{\phi\left(n\right)}\equiv 1\pmod n

———————————————————————————————————————————————-
**Ingin mendapatkan kaos unik bertema matematika silahkan kunjungi kaos.ariaturns.com**

One thought on “Teorema Euler

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s