Smart Mathematics: Oktober 2012

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

Jika $p$ prima maka $\phi\left(p\right)=p-1$
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

Jika $i\neq j$ maka $a_{1}\not\equiv a_{j}\pmod n$
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:

Untuk semua bilangan bulat $m$ maka $\left\{ a_{1}+mn,a_{2}+mn,\ldots,a_{k}+mn\right\}$ merupakan sistem residu tereduksi mod $n$ .
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$