Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas Teorema Lame yang menjelaskan tentang banyaknya langkah yang digunakan oleh algoritma Euclidean untuk mencari greatest common divisor dari dua bilangan, di mana langkah tersebut tidak akan lebih dari 5 kali jumlah digit desimal dari bilangan yang lebih kecil. Teorema ini terkait dengan penggunaan algoritma Euclidean dalam mencari GCD dari bilangan A dan B, dengan asumsi A lebih besar atau sama dengan B. Dengan menggunakan konsep Fibonacci, teorema ini membantu untuk mengestimasi jumlah langkah yang diperlukan berdasarkan jumlah digit desimal dari bilangan B. Dengan demikian, langkah-langkah yang diperlukan untuk mencari GCD dari dua bilangan akan lebih sedikit dari 5 kali jumlah digit desimal dari bilangan tersebut, di mana digit desimalnya direpresentasikan oleh k.

Teorema berikutnya yang akan kita bahas adalah teorema Lame.

misalkan A dan B bilangan bulat positif dengan nilai A lebih besar sama dengan B

maka banyak pembagian yang digunakan oleh algoritma Euclidean

untuk menemukan greatest common divisor dari AB

itu kurang dari atau sama dengan 5 kali banyak digit desimal dalam B.

Jadi teorema ini mengatakan berapa kali sih langkah yang kita gunakan

di mana kita asumsikannya A lebih besar sama dengan B.

Dalam mencari greatest common divisor dari AB

dengan yang R0 sama dengan R1 Ki1 ditambah R2

kemudian R1 kita tuliskan dalam R2 Ki2 ditambah R3

dan seterusnya sampai nanti Rn-1 sama dengan Rn kali Ki n

Rn itu yang akan menjadi greatest common divisor dari AB.

Banyaknya langkah itu nanti akan bisa dilihat

tidak akan lebih dari 5 kali jumlah digit desimalnya si B.

Jadi kalau kita lihat dari bentuk yang sebelumnya

maka Ki1, Ki2 sampai Ki n-1 itu setidaknya nilainya 1

sehingga kita bisa tuliskan Rn itu lebih besar sama dengan 1

sedangkan Rn tadi lebih besar sama dengan F2

dan seterusnya nanti kita akan mendapatkan bahwa

B yang sama dengan R1 itu akan lebih besar sama dengan R2 ditambah R3

Dari contoh sebelumnya kita tahu bahwa Fn-1 itu lebih besar dari Alfa n-1

jadi kita tahu bahwa logaritma dari Alfa itu sekitar 0,208

sehingga kalau dicari log B-nya dengan basis 10

itu lebih besar dari n-1 log 10 dari Alfa

nilainya akan lebih besar dari n-1 dibagi 5

jadi si n-1 ini akan lebih kecil dari 5 log B untuk basis 10

sekarang andaikan kita atau anggap B-nya itu memiliki k angka desimal

kemudian maaf B-nya ini diambil dari situ

sehingga log B-nya itu nanti akan jadi lebih kecil k

nah dari sini kita akan bisa lihat bahwa n-1 tadi

si log B dengan basis 10 tadi kan lebih besar dari n-1 dibagi 5

nah karena log B dengan basis 10 itu lebih kecil k

karena k adalah bilangan bulat maka n-nya itu lebih kecil sama dengan 5k

jadi langkah yang kita lakukan itu pasti lebih sedikit dari 5k

dimana k adalah angka desimal dari si B-nya

jadi berapa banyak angka desimal dari B-nya

itu salah satu teorema yang bisa membantu kita

untuk menghitung berapa langkah yang kita perlukan