Olimpiade Sains Provinsi (OSP) 2014 - Komputer, Nomor 35–36

Perhatikan potongan kode berikut :

for i:=0 to lili do
begin
x:=(x*n) mod lala;
end;

Perhatikan bahwa di dalam for loop x dikali dengan n lalu di mod lala sebanyak lili + 1 kali (mulai dari 0 sampai lili). Jadi :
x_akhir = (x_awal * n^(lili + 1)) mod lala

35. x_akhir = (7 * 7^(12345 + 1)) mod 10
      x_akhir = (7^12347) mod 10 = 3

36. x_akhir = (9 * 9^(12345 + 1)) mod 100
      x_akhir = (9^12347) mod 100 = 69

Untuk mencari 7^12347 mod 10 dan 9^12347 bisa menggunakan pola atau Euler's Theorem.

Menggunakan pola :

35.
7^0 mod 10 = 1
7^1 mod 10 = 7
7^2 mod 10 = 9
7^3 mod 10 = 3
7^4 mod 10 = 1
7^5 mod 10 = 7
7^6 mod 10 = 9
7^7 mod 10 = 3
...
Bisa dilihat bahwa nilai dari 7^k mod 10 memiliki pola yang berulang. Pola yang bisa didapat yakni, apabila :
k mod 4 = 0 -> 7^k mod 10 = 1
k mod 4 = 1 -> 7^k mod 10 = 7
k mod 4 = 2 -> 7^k mod 10 = 9
k mod 4 = 3 -> 7^k mod 10 = 3

Yang ditanyakan pada soal : 7^12347 mod 10. 12347 mod 4 = 3 -> 7^12347 mod 10 = 3

36. Untuk latihan

Menggunakan Euler's Theorem :

Euler's Theorem : Untuk bilangan bulat a, n dan fpb(a, n) = 1, berlaku : a^phi(n) = 1 (mod n)

(Untuk lebih jelasnya mengenai euler's theorem + penjelasan untuk fungsi phi, bisa liat http://en.wikipedia.org/wiki/Euler%27s_theorem)

35.
a = 7
n = 10
gcd(a, n) = gcd(7, 10) = 1 -> memenuhi syarat euler's theorem
phi(n) = phi(10) = 10 * (1 - 1/2) * (1 - 1/5) = 4
Berarti, 7^4 mod 10 = 1
7^12347 mod 10 = (7^3 * (7^4)^3086) mod 10
7^12347 mod 10 = ((7^3 mod 10) * ((7^4)^3086 mod 10)) mod 10
7^12347 mod 10 = (3 * (1^3086 mod 10)) mod 10
7^12347 mod 10 = 3 mod 10 = 3

36.
a = 9
n = 100
gcd(a, n) = gcd(9, 100) = 1 -> memenuhi syarat euler's theorem
phi(n) = phi(100) = 100 * (1 - 1/2) * (1 - 1/5) = 40
Jadi, 9^40 mod 100 = 1
9^12347 mod 100 = (9^27 * (9^40)^308) mod 100
9^12347 mod 100 = (9^27 * 1^308) mod 100
9^12347 mod 100 = (9^27) mod 100

Untuk mencari 9^27 mod 100 bisa memakai exponentiation by squaring (http://en.wikipedia.org/wiki/Exponentiation_by_squaring).
9^27 mod 100 = (9 * 9^26) mod 100
9^26 mod 100 = (9^13)^2 mod 100
9^13 mod 100 = (9 * 9^12) mod 100
9^12 mod 100 = (9^6)^2 mod 100
9^6 mod 100 = (9^3)^2 mod 100
9^3 mod 100 = (9 * 9^2) mod 100
9^2 mod 100 = (9^1)^2 mod 100
9^1 mod 100 = (9 * 9^0) mod 100
9^0 mod 100 = 1 mod 100 (base case, sekarang isi nilai fungsi yang belum diketahui)
9^1 mod 100 = (9 * 1) mod 100 = 9
9^2 mod 100 = (9^1)^2 mod 100 = 81
9^3 mod 100 = (9 * 9^2) mod 100 = 9 * 81 mod 100 = 29
9^6 mod 100 = (9^3)^2 mod 100 = 29 * 29 mod 100 = 41
9^12 mod 100 = (9^6)^2 mod 100 = 41 * 41 mod 100 = 81
9^13 mod 100 = (9 * 9^12) mod 100 = 9 * 81 mod 100 = 29
9^26 mod 100 = (9^13)^2 mod 100 = 29 * 29 mod 100 = 41
9^27 mod 100 = (9 * 9^26) mod 100 = 9 * 41 mod 100 = 69