Teorema Euler


Fermat’s Little Theorem (FLT) akan sangat bermanfaat jika bilangannya adalah bilangan prima. Masalahnya, bagaimana kalau bilangannya komposit?

Leonhard Euler berhasil membuktikan FLT pada tahun 1736. Kemudian, 24 tahun kemudian, FLT digeneralisasi oleh Generalisasi inilah yang disebut sebagai Teorema Euler.

Teorema Euler

Untuk m adalah integer positif dan a adalah integer dimana \gcd(a,m)=1 , maka
a^{\phi(m)} \equiv 1 \mod m

Jika, m adalah bilangan prima, maka rumus di atas akan identik dengan FLT


CONTOH

Berapakah sisa pembagian jika 3^{100000} dibagi 35

Solusi:

Berdasarkan teorema euler

3^{24} \equiv 1 (\mod 35)

Maka pangkatnya kita kelompokan berdasarkan 24

3^{24 \cdot 4166+16} \equiv 3^{16} (\mod 35)

Dengan begitu dapat dengan mudah diselesaikan. Hingga akhirnya didapat

3^{100000} \equiv 11 (\mod 35)

jadi, sisanya adalah 11

sekian.


About ardiantoarsadi

don't look for miracles it will come

Posted on Desember 19, 2009, in MATERI MATEMATIKA. Bookmark the permalink. 2 Komentar.

  1. Yeah… akhirnya dapat

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: