Rubik Cube

Rubik Cube adalah Puzzle yang diciptakan tahun 1974 oleh Professor Arsitektur, Erno Rubik. Untuk lebih jelas mengenai sejarah Rubik Cube, silakan lihat wikipedia.

Berkat adanya acara The Master saat Deddy Corbuzier "mengalahkan" Abel Brata dalam "blindfolded" Rubik Cube, di Indonesia permainan ini menjadi popular berkali-kali lipat. Toko-toko mainan, aksesories, games, souvenir, etc semuanya menjual Rubik Cube..!!

Ada beberapa pertanyaan matematis yang berhubungan dengan Rubik Cube:
1. Ada berapa banyak permutasi yang mungkin dalam membentuk suatu rubik cube 3x3x3?
2. Suatu Rubik Cube yang diacak secara random dapat dipecahkan dalam x langkah atau kurang. Tentukan nilai x yang minimum.
3. Bagaimana algoritma terbaik untuk memecahkan Rubik Cube?

=======================================================================

Berapa Banyak Permutasi Yang Mungkin?

Rubik Cube original (3x3x3) mempunyai 8 corner dan 12 edge. Untuk setiap corner, terdapat 8! cara untuk menyusun semua corner di tempat yang berbeda-beda. Secara orientasi, tiap pojok ini mempunyai 3 wajah/orientasi. Namun, dari 8 corner ini, corner yang satu harus bergantung dari ke-7 corner yang lainnya. Artinya, kemungkinan orientasi corner ada sebanyak 3⁷ (2187) kemungkinan. Untuk edge, terdapat 12!/2 kemungkinan untuk menempatkan ke petak yang berbeda, mengingat permutasi ganjil pada corner juga mengimplikasikan permutasi ganjil pada edge. Tiap edge memiliki 2 wajah/ orientasi. Dari 12 edge yang ada, 11 adalah independent, sedangkan edge yang satu lagi pasti terikat dengan edge lainnya, maka terdapat 2¹¹ (2048) kemungkinan untuk menyusun orinetasi edge. Bagian tengah dari Rubik tidak pernah berubah, maka kemungkinannya adalah 1.

Mengalikan semuanya, maka hasilnya:

Jadi, total permutasi yang mungkin dalam membentuk Rubik Cube adalah

43.252.003.274.489.856.000

Sangat banyak sekali....

=======================================================================

Optimal Solusi untuk Rubik Cube??

Perhatikan bahwa untuk memecahkan suatu Rubik Cube secara optimal, dibutuhkan kemampuan analisis terhadap pola-pola Rubik Cube. Mengingat jumlah permutasi Rubik secara total berjumlah 43 Quantillion, maka mustahil bagi manusia untuk dapat memecahkan Rubik Cube dalam langkah seminimum mungkin. (mungkin bukan mustahil, tapi tentunya akan sangat sangat sangat sangat lama).

Agustus 2007, Daniel Kunkle menggunakan super komputer untuk memecahkan Rubik Cube untuk menunjukkan bahwa semua pola Rubik dapat dipecahkan tidak lebih dari 26 langkah. Tahun 2008, Tomas Rokichi mempunyai bukti komputasional bahwa semua Rubik dapat dipecahkan dalam 25 langkah atau kurang. Selanjutnya, jumlah ini akan berkurang menjadi 23. Agustus 2008, Rokichi membuktikan bahwa langkah maksimum untuk Rubik Cube adalah 22 langkah. God Algorithm (Algoritma yang bertujuan meyelesaikan Rubik dalam langkah seminimum mungkin) untuk menyelesaikan Rubik Cuba ada banyak, misalnya: Thistlethwaite's Algorithm, Kociemba's Algorithm, Korf's Algorithm, etc. Semua dapat dilihat di wikipedia. Ketiga algoritma tersebut digunakan pada komputer.

Untuk melakukan langkah seminimum mungkin memang mustahil jika dilakukan oleh manusia, namun tidak mustahil untuk dapat dipecahkan dengan cepat oleh manusia. Ada yang melakukannya kurang dari 1 menit, kurang dari 30 detik, etc.

Metode yang sederhana dalam memecahkan Rubik Cube dengan cepat, antara lain:
1. Fridrich Method (Layer by Layer Method) ditemukan oleh Jessica Fridrich
Metode ini dimulai dengan membentuk tanda cross pada layer pertama, dilanjutkan dengan memecahkan layer pertama, layer kedua, hingga layer ketiga. Metode ini adalah metode yang sering digunakan oleh orang, mudah dimengerti, namun membutuhkan banyak sekali langkah (boros).

Untuk mempelajari metode ini, bisa cari di wikibook, atau di youtube..
Layer by layer Mthod selanjutnya dikembangkan menjadi F2L alternatif, ZB Method, ZZ Method, dan VH Method. Lihat di wikibook.

2. Petrus System (Block Methods)
Metode ini dimulai dengan membentuk 2x2x3 block di cube, dilanjutkan dengan memecahkan 3x3x2 block, tapi juga mengubah edge di layer terakhir. Kemudian, layer terakhir dikerjakan dalam 2 tahap, pertama pojok, kedua adalah edge. Metode ini sering digunakan dalam contest langkah seminimum mungkin.

Metode Petrus memiliki kemiripan dengan metode Heiss, dan Gilles Roux Method. Lihat di wikibook.

3. Waterman Method (Corner First Method)
Untuk mempelajari metode ini, dibutuhkan 90 algoritma dasar (yang sudah cukup banyak dan menyulitkan untuk dipelajari..). Pecahkan face di L, pojok di R, dan selesaikan edge. Metode ini adalah metode menyelesaikan Rubik Cube yang sangat sangat cepat.

Metode yang mirip adalah Jelinek Method, yaitu metode untuk 4x4x4 cube. Lihat di wikibook.

Untuk mempelajari Waterman Method memang dibutuhkan kesabaran, karena lebih rumit daripada Fridrich Method, namun sudah terbukti keampuhannya dari pemenang Rubik Cube: Josef Jelinek!! Silakan lihat sendiri di situsnya:

WATERMAN METHOD

Untuk menyelesaikan Rubik Cube, kalian bisa menggunakan software yang bisa didownload gratis di internet. Semua rubik dapat dikerjakan dalam 20 langkah (rata-rata)..

Note: Lihat juga di situs resmi Rubik di http://rubiks.com.
Solusi Rubiks.com layer by layer: http://www.youcandothecube.com/secret-unlocked/solution-stage-one.aspx.
Saran saya, pelajarai semua metodenya. Layer by layer, block by block, waterman, dan berbagai versi berbeda lainnya. Menggabungkan beberapa metode tersebut membuat rubiks dapat dikerjakan dengan lebih cepat :).

Click Here to Read More..

MATIC (Mathematics Competition) 2009

Universitas Bina Nusantara (Binus) kembali mengadakan kompetisi matematika antar siswa-siswi SMA bertema "Click So Quick Have Fun With The Tricks".. Lomba akan diadakan 4 babak, mulai babak 1 (penyisihan) yang dilakukan online, babak 2, babak semifinal, dan babak Final (yang akan dilakukan secara live). Lomba babak 1 diadakan tanggal 29 November 2009, dan babak berikutnya dilaksanakan di kampus Anggrek Bina Nusantara tanggal 13 Desember 2009.

Untuk mengikuti lomba, syaratnya yang penting kalian adalah siswa-siswi SMA. Biaya hanya 60 ribu, sudah include makanan, souvenir, sertifikat, workshop, expo, etc.

Untuk registrasi dan info selengkapnya, silakan lihat di http://competition.binus.ac.id/matic2009. Selamat berlomba. :D

Click Here to Read More..

Chinese Remainder Theorem Eksplisit

Di post sebelumnya sudah dibahas mengenai Chinese Remainder Theorem, tapi hanya dijelaskan solusi yang dilakukan secara iteratif. (Lihat di SINI) . Di post ini, akan ditunjukkan Rumus/ Teorema Chinese Remainder Theorem yang eksplisit yang dapat secara langsung digunakan untuk mencari solusi.

Diberikan sistem kongruensi sebagai berikut.

haruslah saling relatif prima
Dengan demikian, kita dapat mencari nilai dengan rumus berikut.

dimana

untuk setiap .
dan adalah invers dari modulo untuk setiap .

Untuk lebih memahami, silakan lihat contoh di bawah. :)

CONTOH 1:
Suatu bilangan bulat positif akan bersisa 1 jika dibagi 3, bersisa 2 jika dibagi 5, dan bersisa 3 jika dibagi 7. Tentukan bilangan bulat terkecil yang memenuhi kondisi tersebut.

Jawab
Soal di atas dapat ditulis ulang menjadi:

Karena 3,5, dan 7 relatif prima, maka rumus CRT (Chinese Remainder Theorem) dapat langsung digunakan.
Kita dapatkan , , , dan . Untuk menentukan , kita selesaikan , menjadi , maka . Untuk menentukan , kita selesaikan , maka . Untuk menentukan , kita selesaikan , maka

Tinggal memasukkan semua elemen yang ada ke dalam rumus.

Jadi, bilangan bulat positif terkecil itu adalah 52. Bisa dicek bahwa 52 akan bersisa 1 jika dibagi3, bersisa 2 jika dibagi 5 dan bersisa 3 jika dibagi 7.

Untuk membuktikan formula ini sangat sederhana. Lihat kotak dibawah.

Tentukan

Solusi yang diberikan adalah

Mula-mula pandang bahwa

(merupakan solusi yang sudah didefinisikan sebelumnya)

Jika solusi tersebut memenuhi syarat awal bahwa akan bersisa jika dibagi untuk setiap , maka solusi tersebut terbukti kebenarannya.

Kita coba periksa sisanya jika dibagi dengan
Karena , maka tentunya .
Karena , maka juga.
Dan seterusnya dari hingga
Oleh karenanya:

Menurut definisi sebelumnya , maka

Ternyata, jika dibagi dengan akan bersisa . Artinya, ini sesuai dengan salah satu syarat yang diberikan.

Pembuktian masih dilanjutkan dengan mengecek sisanya jika dibagi .
Karena , maka
Karena , maka .
Dan hal sama juga berlaku pada hingga (silakan dicek sendiri, dan ketahuilah mengapa demikian)
Oleh karenanya:

Karena kita tahu bahwa , maka

Ternyata sesuai dengan syarat baris kedua.

Pembuktian dilanjutkan dengan mengecek sisanya jika dibagi hingga . Masing-masing akan menyisakan , hingga . Dengan demikian, definisi awal yang diberikan terbukti.

TERBUKTI sebagai solusi CRT

Namun, ada hal yang masih perlu dibuktikan. Karena mempunyai banyak jawab, akibatnya juga mempunyai banyak jawab.
Misalkan dan adalah solusi CRT yang nilainya berbeda, maka:
________Untuk setiap :

Menggabungkan keduanya:

Sesuai dengan teorema keterbagian bahwa: "jika dan , maka ", maka

Dari hasil di atas, diketahui bahwa antara solusi yang satu dengan solusi yang lain adalah kongruen modulo M. Jadi, solusi CRT menjadi:

TERBUKTI

Untuk lebih memahami penggunaan CRT. Perhatikan contoh di bawah. Kerjakan sebagai latihan.

CONTOH 2:
Temukan integer yang bersisa 1 jika dibagi 2 dan jika dibagi 3

Jawab:


, ,
, maka
, maka

CONTOH 3:
Temukan integer terkecil yang memenuhi

Jawab:
(Note: akan lebih mudah jika diselesaikan dengan komputer :D)







Kemudian, carilah .
, maka , maka
, maka
, maka , maka
, maka , maka
, maka , maka
(Note: untuk mencari invers modulo, biasakan untuk menggunakan teorema Euler).

Selanjutnya tinggal memasukkan ke rumus

Jadi, bilangan terkecil itu adalah 150999.

=======================================================================

Demikianlah posting kali ini.
Materi CRT memang jarang digunakan dalam olimpiade matematika, namun aplikasinya menarik :D.

Untuk memahaminya, pelajari materi dasar dahulu seperti keterbagian, modulo, dan invers modulo. Jika masih belum paham, tanyakan di comment atau YM atau email, bagian mana yang membuat kamu tidak paham. Key? :).

Click Here to Read More..

Ikut OSN PTI Pertamina Yukk :)

OSN-PTI (Olimpiade Sains Nasional - Perguruan Tinggi Indonesia) merupakan ajang kompetisi sains di bidang Matematika, Fisika, dan Kimia antar mahasiswa tingkat nasional yang digelar Pertamina sebagai bagian dari kegiatan tanggung jawab sosial perusahaan (Corporate Social Responsibility/CSR) bidang pendidikan. Ajang berhadiah total uang tunai Rp 2 miliar lebih ini akan menghasilkan kandidat yang akan maju ke olimpiade internasional.

OSN-PTI 2009 merupakan penyelenggaraan yang kedua kali. Pada penyelenggaraan pertama (2008), jumlah pesertanya mencapai 4.666 mahasiswa. Untuk tahun ini, berdasarkan tingginya antusiasme mahasiswa, total peserta se-Indonesia diharapkan bisa mencapai 10 ribu peserta. Apalagi, penyelenggaraan tahun ini sudah diperluas dibandingkan tahun sebelumnya.

Syarat Peserta?
Asal kamu adalah mahasiswa minimal semester 3, kamu bisa ikut. Gratis. :)

Bagaimana Cara untuk Ikut?
Cukup berikan surat pengantar dari universitas (bisa Kajur, Dekan, atau Rektor), terus isi formulir pendaftaran online di www.osnpti.com.. Mudah kan?

Pendaftaran dan Seleksi
Pendaftaran : 5 September – 26 Oktober 2009
Seleksi Peserta Tingkat Daerah : 3 Nopember 2009
Seleksi Peserta Tingkat Pusat & Final : 4 – 9 Desember 2009

Untuk lebih jelasnya, silakan lihat di www.osnpti.com.
Ikut ya, semua. Gak ada ruginya kan ikut lomba gratis dan berhadiah? :))

Click Here to Read More..

Menghitung Super Cepat

Di Toko-toko buku, seperti Gramedia, dijual buku sulap yang ditulis Deddy Corbuzier; Book of Magic. Harganya lumayan mahal, Rp148.000,00, namun lumayan bagus. Isi bukunya adalah berbagai sulap sederhana yang menarik.

Ada trik sulap "Menghitung Super Cepat".

Bagaimana memainkannya?
Sebelum memainkannya, persiapkan dahulu 4 buah kartu yang diisi dengan angka-angka sebagai berikut.

Di bagian belakang masing-masing kartu juga diisi angka:

Penjelasan: 3 8 6 4 7 adalah bagian belakang dari kartu 2 2 3 9 6, dan seterusnya.

=======================================================================

Cara memainkannya sangat *sangat* sederhana. Panggilkan salah satu temanmu untuk ikut serta. Dia bebas mengacak keempat kartu itu dalam urutan yang bagaimana pun. Setelah temanmu itu selesai mengacak keempat kartu, maka sediakan kertas coret untuk menghitung jumlah semua angka itu dari atas ke bawah.

Contoh ilustrasi:

Dapat kita lihat bahwa jumlahnya adalah 24590. Silakan cek di kalkulator. Setiap urutan yang berbeda akan menghasikan jawaban yang berbeda pula.

Sementara kamu terlihat mencoret-coret di kertas, suruhlah temanmu itu untuk ikut menghitung. Yang pasti, bagaimana pun caranya, kamu akan dapat menghitung dengan tepat dan cepat. Bahkan lebih cepat dari kalkulator.!!

Bagaimana cara (rahasianya)??????? Lihat lanjutannya di bawah..
=======================================================================

Cukup sederhana.

Tambahkan baris kedua dengan 22220

Dari contoh di atas, artinya kita cukup menghitung 22220 + 2370 = 24590

Coba kita lihat contoh dengan urutan yang berbeda:

Hasilnya adalah 22220 + 2130 = 24350.

Note:
Permainan ini harus dilakukan dalam situasi yang tepat. Anda harus serius. Jangan pernah mengatakan bahwa ini hanya permainan sulap. Jangan pernah menyebut kata "sulap". Jika demikian, efek permainan tidak ada gunanya.

Jangan lakukan permainan ini seperti permainan anak bayi. Artinya, jangan buat penonton merasa permainan ini terlalu mudah. Oleh karenanya, terlihatlah serius menghitung di kertas. Tulis semua coret-coretan yang sebetulnya tidak berguna bagi Anda (hanya sebagai aksesoris). Jangan terlalu cepat menghitung. Sekali-kali kegagalan juga diperlukan untuk membuat efek dramatis.

Mengapa harus ditambahkan 22220? Siapa penemu urutan ajaib ini? Mengapa bisa demikian? Semua pertanyaan ini tidak dijawab sekarang. Ini juga masih menjadi pertanyaan bagi saya. :)

Terdapat cara untuk menyusun urutan kartu-kartu tersebut. Jadi, akan mustahil untuk menghapal semua jawabannya :)

Sumber: Buku BOOK OF MAGIC oleh Deddy Corbuzier.

Click Here to Read More..

Kumpulan Soal dan Solusi Olimpiade Matematika Tk Provinsi 2002-2009

Berikut adalah kumpulan Soal dan Solusi Olimpiade Matematika Tingkat Provinsi tahun 2002-2009.

Judul File	Ziddu	Rapidshare
Soal dan Solusi Olimpiade Matematika Tk Provinsi 2002	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Provinsi 2003	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Provinsi 2004	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Provinsi 2005	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Provinsi 2006	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Provinsi 2007	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Provinsi 2008	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Provinsi 2009	Download	Download

Kumpulan Soal dan Solusi Olimpiade Matematika Tk Provinsi 2002-2009

Download

Download

Kumpulan soal di atas tentunya tidak terlepas dari jasa orang-orang baik pelatih olimpiade maupun peserta olimpiade. Mereka mau berbagi solusi dan men-sharenya ke publik.

Jangan lupa mengerjakan sesudah mendownload. Jangan hanya dilihat. :)
Lihat juga Kumpulan Soal dan Solusi Olimpiade Matematika pada tingkat Kota.
Click Here to Read More..

Kumpulan Soal dan Solusi Olimpiade Matematika Tk Kota 2002-2007

Olimpiade Matematika tingkat SMA dimulai dari seleksi tingkat kabupaten/ kota, kemudian provinsi, nasional, dan terakhir tingkat internasional. Kita dapat menyebut OSK untuk tingkat kota. OSP untuk provinsi. OSN untuk nasional dan IMO untuk Olimpiade internasional. Tentunya, olimpiade sains ada banyak bidang, termasuk matematika.

Tentunya, untuk bisa mencapai tingkat Nasional bahkan internasional, tidak ada jalan pintas selain belajar dengan latihan dan latihan.

Berikut adalah kumpulan Soal dan Solusi Olimpiade Matematika Tingkat Kota tahun 2002-2009.

Judul File	Ziddu	Rapidshare
Soal dan Solusi Olimpiade Matematika Tk Kota 2002	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Kota 2003	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Kota 2004	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Kota 2005	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Kota 2006	Download	Download
Soal dan Solusi Olimpiade Matematika Tk Kota 2007	Download	Download

Kumpulan Soal dan Solusi Olimpiade Matematika Tk Kota 2002-2007

Download

Download

Kumpulan soal di atas tentunya tidak terlepas dari jasa orang-orang baik pelatih olimpiade maupun peserta olimpiade. Mereka mau berbagi solusi dan men-sharenya ke publik. Jadi, jangan terima kasih ke saya. :)

Jangan lupa mengerjakan sesudah mendownload. Jangan hanya dilihat. :)
Lihat juga Kumpulan Soal dan Solusi Olimpiade Matematika Tingkat Provinsi 2002-2009.
Click Here to Read More..

Selamat Hari Raya Idul Fitri

Let's Undo and Make it Better.

Blog ini mengucapkan Selamat Hari Raya Idul Fitri.
Mohon Maaf Lahir dan Batin.

Click Here to Read More..

Teorema Euler

(Pelajari dahulu Fermat's Little Theorem dan Euler Phi Function.)

Fermat's Little Theorem (FLT) bekerja dengan baik jika bilangannya adalah prima. Namun, hal ini kurang memuaskan para matematikawan karena kurang praktis. Bagaimana dengan bilangan komposit?

Tahun 1736, Leonhard Euler berhasil membuktikan FLT. Kemudian, 24 tahun kemudian, FLT digeneralisasi oleh Euler. Selanjutnya generalisasi ini disebut dengan teorema Euler.

Teorema Euler

Untuk positif integer dan adalah integer dimana , maka:

Perhatikan bahwa apabila adalah bilangan prima (), maka FLT berlaku:

Di post ini, kita akan mempelajari bukti teorema ini, sekaligus mengenal kegunaan dari teorema Euler ini terutama dalam menyelesaikan soal kongruensi modulo dengan cepat. :)

=======================================================================

Konsep yang melandasi bukti teorema euler adalah sistem residu yang tereduksi. Perhatikan penjelasan pada kotak di bawah.

Sistem Residu yang tereduksi (reduced residue system) modulo adalah kumpulan bilangan integer yang totatif (koprima) dengan dan tidak ada 2 integer yang mempunyai kelas sisa yang sama.

Contoh 1:
1, 2, 4, 5, 7, 8 adalah sistem residu tereduksi modulo 9.
Perhatikan bahwa . Jadi, jumlah bilangannya harus 6. .
Perhatikan juga bahwa bilangan-bilangan itu harus koprima dengan 9, dan mempunyai kelas sisa yang berbeda satu sama lain.

Contoh 2:
-5, 7, 14, 19, 29, 35 adalah sistem residu tereduksi modulo 9.
Perhatikan bahwa semua bilangannya koprima dengan 9.
Tiap bilangan juga memiliki kelas sisa yang berbeda:
-5 4 (mod 9)____7 7 (mod 9)_____14 5 (mod 9)
19 1 (mod 9)____29 2 (mod 9)____35 8 (mod 9)

Contoh 3:
1, 5, 7, 11, 13 BUKAN sistem residu tereduksi modulo 12, karena jumlah bilangannya ada 5, padahal

Contoh 4:
-7, 11, 13, 17 BUKAN sistem residu tereduksi modulo 12, karena
-7 dan 17 memiliki kelas sisa yang sama.
-7 5 (mod 12). ____17 5 (mod 12)_

Contoh 5:
-7, 11, 13, 51 BUKAN sistem residu tereduksi modulo 12, karena 51 dan 12 bukan koprima.

Teorema

Jika adalah sistem residu yang tereduksi modulo ,
dan adalah integer positif dimana , maka:

juga merupakan sistem residu yang tereduksi modulo .

BUKTI:
(i) Bukti bahwa tiap elemen koprima dengan .
__Karena dan , maka .
(ii) Bukti bahwa tiap dua elemen memiliki kelas sisa yang berbeda.
__Asumsikan bahwa ada dua elemen, misalkan dan yang kongruen modulo .

__Karena , maka:

__Namun, kita tahu bahwa dan inkongruen (karena keduanya berasal dari sistem
__residu tereduksi). Oleh karenanya, kontradiksi dengan asumsi awal.
__Jadi, dan yang inkongruen modulo .

Dari poin (i) dan (ii) dapat disimpulkan bahwa juga merupakan sistem residu yang tereduksi modulo . ■

Contoh 6:
1, 3, 5, 7 merupakan sistem residu tereduksi modulo 8.
Karena gcd( 3, 8 ) = 1, maka:
3, 9, 15, 21 juga merupakan sistem residu tereduksi modulo 8.

BUKTI TEOREMA EULER:
Didasarkan pada teorema sebelumnya pada kotak di atas.

Karena juga merupakan sistem residu tereduksi modulo , maka tentunya sisa residu positif dari adalah dalam urutan tertentu (acak).
Dengan mengalikan elemen-elemen tersebut, kita dapatkan:

Karena , maka

TERBUKTI. ■

ILUSTRASI BUKTI:
Dari contoh 6, kita tahu bahwa
1, 3, 5, 7 merupakan sistem residu tereduksi modulo 8.
3.1, 3.3 , 3.5 , 3.7 juga merupakan sistem residu tereduksi modulo 8.
Dengan demikian:

(3.1) (3.3) (3.5) (3.7) 3. 1. 7. 5 (mod 8)

(3.1) (3.3) (3.5) (3.7) 1 . 3 . 5 . 7 (mod 8)
3⁴ (1. 3. 5. 7) 1 . 3 . 5 . 7 (mod 8)

=======================================================================

Contoh 1:
Tentukan digit terakhir dari .

Jawab:
Mencari digit terakhir sama seperti mencari sisanya juga dibagi 10.
Sesuai dengan teorema euler, maka:

Jadi, kita kelompokkan berdasarkan 4.

Digit terakhirnya adalah 1.

Contoh 2:
Berapakah sisa pembagian jika dibagi .

Jawab:
Sesuai teorema Euler,

Maka, kita kelompokkan berdasarkan 24.

Selanjutnya, gunakan cara biasa:

___________

Jadi, sisanya adalah 11.

Contoh 3:
Tentukan solusi kongruensi dari .

Jawab:

Teorema euler berguna untuk mencari invers modulo:

Berarti, adalah invers dari modulo .

Dengan demikian,

Contoh 4:
Jika koprima dengan 32760, buktikan bahwa:

Jawab:
Perhatikan bahwa
Teorema Euler menyatakan bahwa:
__, maka
__, maka
__, maka
__, maka


Karena 8, 9, 5, 7, dan 13 semuanya koprima, maka

Terbukti. ■

Contoh 5:
Jika dan koprima, buktikan bahwa:

Jawab:
Menurut teorema Euler:
(i) , maka
(ii) , maka
Sesuai dengan sifat keterbagian,

Terbukti. ■

=======================================================================

Di post ini, hanya diberikan perhitungan-perhitungan dasar yang melibatkan teorema euler. Dalam prakteknya pun, perhitungan yang melibatkan teorema euler juga merupakan perhitungan dasar seperti di atas. Teorema Euler berguna dalam banyak hal. Salah satunya untuk mempercepat proses enkripsi dan dekripsi dalam kriptografi, sehingga lebih efektif dan efisien . (belum dibahas sekarang).

Dengan teorema Euler, kita juga dapat membuktikan formula eksplisit dari Chinese Remainder Theorem, yang memungkinkan CRT diselesaikan dengan program komputer. Namun, hal itu masih belum dibahas sekarang.

Tunggu kelanjutan post-post berikutnya ya :)

Sumber:
http://en.wikipedia.org/wiki/Euler%27s_theorem
http://www.cut-the-knot.org/blue/Euler.shtml
Buku Elementary Number Theory oleh Kenneth H Rosen.

Click Here to Read More..

Mengenal Euler Phi-Function

Euler Phi-Function sering disebut juga sebagai Euler totient function.

Dalam bahasa Indonesia, kita dapat menyebutnya dengan fungsi phi atau fungsi totient. Meskipun fungsi ini memiliki nama phi, namun fungsi ini dalam perhitungannya sama sekali tidak menggunakan phi () yang bernilai 1,61803399.. Sebaliknya, fungsi ini hanya memperhitungkan bilangan integer.

Alasan mengapa dinamakan fungsi phi adalah karena fungsi ini menggunakan lambang phi ().

Definisi phi function

Phi function adalah fungsi yang mengitung banyaknya integer untuk

yang memenuhi syarat:

dan koprima.

Note, dan dikatakan koprima jika .

Bilangan integer positif yang lebih kecil atau sama DAN relatif prima dengan suatu bilangan lain yang diberikan disebut bilangan totatif. Oleh karenanya, fungsi ini disebut juga sebagai fungsi totient.

=======================================================================

Untuk lebih jelasnya mengenai fungsi phi ini, maka sebaiknya kita gunakan contoh.

Contoh 1:
Sesuai definisi, maka

karena gcd(1,1) = 1.

Contoh 2:

Dari enam bilangan: 1, 2, 3, 4, 5, dan 6,
terdapat 2 bilangan yang koprima dengan 6 yaitu 1 dan 5.

Contoh 3:

Dari sembilan bilangan: 1, 2, 3, 4, 5, 6, 7, 8, dan 9,
terdapat 3 bilangan yang memiliki faktor dengan 9, yaitu 3, 6, dan 9
Jadi, terdapat 6 bilangan yang koprima dengan 9.

Contoh 4:

Dari dua belas bilangan: 1, 2, 3, ... , 11, 12,
terdapat 8 bilangan yang memiliki faktor dengan 12, yaitu 2, 3, 4, 6, 8, 9, 10, dan 12.
Jadi, terdapat 4 bilangan yang koprima dengan 12.
Dapat dikatakan juga: Banyaknya bilangan totatif dari 12 adalah 4.

Untuk bilangan-bilangan awal, kita dapat membuat tabelnya sbb:

Sekarang, kita akan membahas property unik dari .

Teorema 1

Untuk bilangan prima

Contoh 5:

Dari bilangan 1, 2, 3, ... , 13
terdapat 1 bilangan yang memiliki faktor dengan 13, yaitu 13.
Jadi, terdapat 12 bilangan yang koprima dengan 13.

Contoh 6:

Ingat bahwa 97 adalah bilangan prima.

Teorema 2

Untuk bilangan prima dan positif integer


atau dapat ditulis:

Contoh 7:

Dari bilangan 1, 2, 3, 4, ... , 121,
terdapat 11 bilangan yang memiliki faktor dengan 121, yaitu 11, 22, 33, 44, ... , 121.
Jadi, terdapat (121 - 11) = 110 bilangan yang koprima dengan 121.

Contoh 8:

Dari bilangan 1, 2, 3, 4, ... , 125,
terdapat 25 bilangan yang memiliki faktor dengan 125, yaitu 5, 10, 15, 20, ... , 125.
Jadi, terdapat (125 - 25) = 100 bilangan yang koprima dengan 125.

Teorema 3

Phi function adalah fungsi multiplikatif.

Untuk dan saling relatif prima (koprima), maka

ILUSTRASI BUKTI:
Anggap dan , maka . Kita akan mencacah bilangan 1, 2, 3, ... , 36 dalam suatu bagan seperti di bawah:

Bilangan yang diberi warna biru adalah bilangan yang koprima dengan 36.
Dari bagan di atas, kita tahu bahwa

BUKTI:
dapat digambarkan dalam bentuk seperti di bawah:

(Lihat kolom pertama)
Dari barisan 1, 2, 3, ... , , ... , , misalkan memiliki faktor dengan .
Kita tulis kembali baris ke-, yaitu:

Karena memiliki faktor dengan , maka semua elemen barisan di atas juga memiliki faktor dengan . Otomatis, semua elemen tersebut juga memiliki faktor dengan .

Karena kita ingin memperhitungkan bilangan yang koprima dengan , maka kita tinjau barisan yang koprima dengan .

----

Anggap dan koprima.
Kita tulis kembali baris sbb:

Karena dan koprima, maka semua elemen di baris tersebut merupakan sistem komplit residu modulo . (Lihat teorema di kotak biru di bawah). Oleh karenanya, di baris tersebut pasti terdapat bilangan yang koprima dengan .

Sistem komplit residu modulo adalah kumpulan integer yang tiap elemennya akan menghasilkan kelas sisa yang berbeda-beda jika dibagi oleh .
Contoh:

1, 2, 3, 4, 5 merupakan sistem komplit residu 5.

-1, 3, 7, 10, 16 merupakan sistem komplit residu 5.
Perhatikan bahwa:

-1 4 mod 5 ,__ 3 3 mod 5 ,__ 72 mod 5 ,__ 100 mod 5 ,__ 161 mod 5

Apakah (-10, 7, 18, 22, 30, 32, 46, 65) merupakan sistem komplit residu 9?
Jawab: bukan, karena jumlah elemennya hanya 8.

Apakah (-10, 7, 18, 22, 30, 32, 46, 65, 73) merupakan sistem komplit residu 9?
Jawab: bukan, karena dan . (kelas sisanya sama)

Teorema

Jika adalah sistem komplit residu modulo
dan jika adalah positif integer dimana ,
dan adalah integer, maka:

juga merupakan sistem komplit residu modulo

BUKTI:
Asumsikan bahwa ada dua elemen yang kongruen, maka:

(Lihat SINI) Karena , maka:

Namun, karena kita tahu bahwa adalah sistem komplit modulo, maka tidak mungkin ada kelas sisa yang sama antar dan .

Kontradiksi dengan asumsi awal, maka tidak ada dua elemen yang kongruen modulo . Dengan demikian, merupakan sistem komplit modulo . ■

Karena terdapat baris yang koprima terhadap DAN di setiap baris tersebut terdapat elemen yang koprima dengan , maka dapat disimpulkan bahwa:

TERBUKTI ■

Contoh 9:


Contoh 10:

Rumus Cepat

merupakan faktorisasi prima untuk positif integer

maka

BUKTI:

TERBUKTI ■

Contoh 11:


Contoh 12:

Teorema 4

selalu bernilai genap untuk

BUKTI:
Anggap . (faktorisasi prima), maka

Dari teorema 2, kita tahu bahwa .
Perhatikan bahwa selalu genap untuk setiap , kecuali untuk DAN .
Terdapat satu saja yang bernilai genap mengakibatkan juga bernilai genap.

TERBUKTI ■

=======================================================================

Selain bisa ditulis sebagai , phi function juga bisa ditulis dalam bentuk . Ini hanya merupakan masalah bentuk simbol phi saja. Ada yang curly, ada yang straight.

Phi function memiliki banyak kegunaan, terutama di bidang kriptografi (persandian). Namun, karena keterbatasan tempat dan waktu, kita tidak membahasnya sekarang. Di post ini, kita hanya belajar mengenai perhitungan phi function saja.

Lihat lanjutan post ini: Teorema Euler

Sumber:
http://en.wikipedia.org/wiki/Euler%27s_totient_function
http://mathworld.wolfram.com/TotientFunction.html
Buku Elementary Number Theory oleh Kenneth H Rosen.

Click Here to Read More..