Peritungan XN Mod M Dengan Nilai N Yang Sangat Besar

Bagaimanakah kita menghitung hasil dari x^n mod m dengan nilai n yang sangat besar? Setidaknya ada dua cara untuk melakukannya. Cara yang pertama merupakan cara yang paling sederhana namun untuk kasus tertentu tidak memberikan hasil yang tepat jika dibandingkan dengan cara yang kedua yaitu menggunakan konsep divide and conquer. Untuk menghemat waktu, mari kita lihat salah satu contoh soal yang diujikan di Olimpiade Sains kota.
br/> Berapakah 7⁴⁵⁰ mod 100? (Catatan n mod m adalah sisa pembagian n oleh m, misalnya 41 mod 7 = 6, karena 41 - ( 7 x 5 ) = 6)?
br/> Penyelesaian:
br/> Temukan terlebih dahulu pola untuk menyelesaikan soal diatas. Pola tersebut dihasilkan dari pangkat terkecil, yaitu:

• 7¹ mod 100 = 7 mod 100 = 7
• 7² mod 100 = 49 mod 100 = 49
• 7³ mod 100 = 343 mod 100 = 43
• 7⁴ mod 100 = 2401 mod 100 = 1
• 7⁵ mod 100 = 16807 mod 100 = 7
• 7⁶ mod 100 = 117649 mod 100 = 49
• 7⁷ mod 100 = ____49 mod 100 = 43
  

Perhatikan pola yang dihasilkan dimulai dari 6,49,43,1 dan berulang lagi ke angka yang sama yaitu 7,49,43,1. Sehingga sisa yang mungkin hanya 7,49,43 dan 1.
Analisa:

1. Semua nilai n dari 7ⁿ jika dibagi 4 menghasilkan sisa 0, maka 7ⁿ mod 100 = 1.
   Ambil contoh n=4 atau n=8
2. Semua nilai n dari 7ⁿ jika dibagi 4 menghasilkan sisa 1, maka 7ⁿ mod 100 = 7.
   Ambil contoh n=1 atau n=5
3. Semua nilai n dari 7ⁿ jika dibagi 4 menghasilkan sisa 2, maka 7ⁿ mod 100 = 49.
   Ambil contoh n=2 atau n=6
4. Semua nilai n dari 7ⁿ jika dibagi 4 menghasilkan sisa 3, maka 7ⁿ mod 100 = 43.
   Ambil contoh n=3 atau n=7

Kesimpulan Pola:

?

1 2 3 4 5

if (n mod 4=0), maka 7n mod 100=1 elseif (n mod 4=1), maka 7n mod 100=7 elseif (n mod 4=2), maka 7n mod 100=49 elseif (n mod 4=0), maka 7n mod 100=43 end if

Sehingga nilai dari 7⁴⁵⁰ mod 100 adalah 49. Bagaimana kalau kita menggunakan konsep divide and conquer? Pembahasannya akan saya posting untuk contoh soal dan waktu yang berbeda.

Sumber : http://andidamanik.com/media.php?module=detailtutorial&id=8