Teorema Euler [PDF]

Citation preview

Teorema Euler Jika (a,m) = 1 , maka a ( m)  1(mod m)



Bukti: Misalkan x1 , x 2 ,..., x ( m )  adalah suatu sistem residu tereduksi modulo m, maka dapat ditentukan bahwa: ax1 , ax 2 ,...,ax ( m )  adalah juga merupakan suatu system residu tereduksi modulo m. Karena x1 , x2 ,...,x ( m )  dan ax1 , ax 2 ,...,ax ( m )  keduanya merupakan merupakan sistem residu tereduksi modulo m, maka tentu ada indeks i dan j sehingga: xi  y (mod m) , 0  y  m



axi  y(modm), 0  y  m



Sesuai dengan sifat transitip kongruensi, jika xi  y (mod m) , 0  y  m



axi  y(modm), 0  y  m



maka dapat ditentukan bahwa: axi  ax j (mod m) Ini berarti bahwa setiap residu di dalam x1 , x 2 ,..., x ( m )  kongruen dengan suatu residu di dalam ax1 , ax 2 ,...,ax ( m )  sehingga jika seluruh kongruensi dikalikan, maka akan diperoleh: x1 .x 2 ...x ( m )  ax1 .ax 2 ...ax ( m ) (mod m)



x1.x2 ...x ( m)  a ( m) x1.x2 ...x ( m) (mod m) Karena x1 , x 2 ,..., x ( m )  adalah suatu sistem residu tereduksi modulo m, maka menurut definisi  xi , m  1 sehingga dapat ditentukan bahwa:



 x1, m   x2 , m  ...   x ( m) , m  1 dan sebagai akibatnya:



 x1x2 , m  1,  x1x2 x3 , m  1,  x1 x2 x3...x ( m) , m   1 Selanjutnya, karena:  x1 x2 x3 ...x ( m) , m   1 dan:



x1.x2 ...x ( m)  a ( m) x1.x2 ...x ( m) (mod m) maka dapat ditentukan bahwa: 1  a  ( m ) (mod m) atau



a  ( m )  1(mod m)



Contoh: 1. Untuk m  4, (4)  2 , sehingga diperoleh: 3 ( 4)  32  1(mod 4) , sebab (3,4) = 1 9 ( 4)  92  1(mod 4) , sebab (9,4) = 1 25 ( 4)  (25) 2  1(mod 4) , sebab (25,4) = 1



2. Untuk m  25, (25)  20 , sehingga diperoleh: 2 ( 25)  220  1(mod 25) , sebab (2,25) = 1 7 ( 25)  7 20  1(mod 25) , sebab (7,25) = 1 11 ( 25)  1120  1(mod 25) , sebab (11,25) = 1



3. Tentukan nilai x yang memenuhi 9101  x(mod 5) dan 0  x  5 Jawab: Untuk m  5, (m)  4 , sehingga 9 (5)  94  1(mod 5) 9101  9100.9  (94 ) 25 .9(mod 5)  1.9(mod 5)  9(mod 5)  4(mod 5)



Jadi x = 4