Algoritma Euclid
Pada setiap bilangan bulat \( a \) dan \( b \) dimana \( b \ne 0 \) yang memenuhi \( a = bq + r \) dan \( 0 \le r \lt \lvert b \rvert \), dimana bilangan bulat \( q \) adalah hasil bagi (quotient) dan bilangan bulat \( r \) adalah sisa bagi (remainder), berlaku \( \gcd(a, b) = \gcd(b, r) \)
GCD adalah singkatan dari Greatest Common Divisor. Dalam bahasa Indonesia, GCD dikenal sebagai FPB: Faktor Persekutuan Terbesar.
Teorema di atas bisa dipakai secara beruntun untuk mencari GCD secara cepat. Pemakaian secara beruntun ini dikenal sebagai Algoritma Euclid. Algoritma Euclid akan terus berlangsung selama \( r \) masih lebih besar dari nol. Algoritma baru akan berhenti ketika \( r \) bernilai nol.
Jika \( r \) sudah nol, maka nilai GCD dapat ditentukan dengan menggunakan rumus:
\( \gcd(a, 0) = \lvert a \rvert \)
Teorema ini sudah dibuktikan di sifat GCD ini.
Selanjutnya, sebelum mempelajari Algoritma Euclid, pembaca sangat disarankan untuk memahami Pembagian Euclid terlebih dahulu.
Agar lebih jelas, perhatikan contoh-contoh di bawah.
bukti
Misalkan \( D \) adalah himpunan semua faktor-faktor persekutuan dari \( a \) dan \( b \).
\( D = \{ d_1, d_2, d_3, \cdots , d_j \} \)
Tentu saja faktor persekutuan terbesar (GCD) dari \( a \) dan \( b \) ada di dalam \( D \).
Misalkan pula \( E \) adalah himpunan semua faktor-faktor persekutuan dari \( b \) dan \( r \).
\( E = \{ e_1, e_2, e_3, \cdots , e_k \} \)
Tentu saja faktor persekutuan terbesar (GCD) dari \( b \) dan \( r \) ada di dalam \( E \).
Kalau bisa dibuktikan bahwa semua anggota himpunan \( D \) ada di dalam \( E \) dan semua anggota himpunan \( E \) ada di dalam \( D \), berarti \( D = E \).
Kalau \( D = E \), berarti anggota himpunan terbesar \( D \) sama dengan anggota himpunan terbesar \( E \).
Kalau anggota himpunan terbesar \( D \) sama dengan anggota himpunan terbesar \( E \), berarti faktor persekutuan terbesar \( a \) dan \( b \) sama dengan faktor persekutuan terbesar \( b \) dan \( r \).
Berarti, untuk membuktikan \( \gcd(a, b) = \gcd(b, r) \) cukup dengan membuktikan bahwa semua anggota himpunan \( D \) ada di dalam \( E \) dan semua anggota himpunan \( E \) ada di dalam \( D \).
Bagian 1: semua anggota himpunan D ada di dalam E
Ambil salah satu anggota himpunan \( D \). Katakanlah \( d_1 \)
Karena \( d_1 \) adalah faktor persekutuan dari \( a \) dan \( b \), maka
\(
\begin{align*}
a &= d_1 \cdot m \\
b &= d_1 \cdot n
\end{align*}
\)
Kemudian
\(
\begin{align*}
a &= b \cdot q + r \\
d_1 \cdot m &= d_1 \cdot n \cdot q + r \\
r &= d_1 \cdot (m - n \cdot q)
\end{align*}
\)
Terlihat jelas bahwa \( d_1 \) adalah salah satu faktor dari \( r \). Karena \( d_1 \) adalah faktor dari \( b \) dan \( r \), maka \( d_1 \) adalah salah satu faktor persekutuan dari \( b \) dan \( r \). Artinya \( d_1 \) pasti ada di dalam himpunan \( E \).
Dengan cara yang sama, semua anggota himpunan \( D \) pasti juga anggota himpunan \( E \).
Bagian 2: semua anggota himpunan E ada di dalam D
Ambil salah satu anggota himpunan \( E \). Katakanlah \( e_1 \)
Karena \( e_1 \) adalah faktor persekutuan dari \( b \) dan \( r \), maka
\( b = e_1 \cdot m \)
\( r = e_1 \cdot n \)
Kemudian
\(
\begin{align*}
a &= b \cdot q + r \\
a &= e_1 \cdot m \cdot q + e_1 \cdot n \\
a &= e_1 \cdot ( m \cdot q + n ) \\
\end{align*}
\)
Terlihat jelas bahwa \( e_1 \) adalah salah satu faktor dari \( a \). Karena \( e_1 \) adalah faktor dari \( a \) dan \( b \), maka \( e_1 \) adalah salah satu faktor persekutuan dari \( a \) dan \( b \). Artinya \( e_1 \) pasti ada di dalam himpunan D.
Dengan cara yang sama, semua anggota himpunan \( E \) pasti juga anggota himpunan \( D \).
Kesimpulan
Karena sudah ditunjukkan bahwa semua himpunan \( D \) pasti juga anggota himpunan \( E \) dan sebaliknya, semua anggota himpunan \( E \) pasti juga anggota himpunan \( D \), maka dapat disimpulkan \( D = E \). Karena \( D = E \), maka anggota himpunan terbesar \( D \) pasti sama dengan anggota himpunan terbesar \( E \). Karena anggota himpunan terbesar \( D \) sama dengan anggota himpunan terbesar \( E \), maka faktor persekutuan terbesar dari \( a \) dan \( b \) sama dengan faktor persekutuan terbesar dari \( b \) dan \( r \).
tambahan
Apakah algoritma ini pasti berhenti?
Pasti. Perhatikan bahwa di dalam setiap operasi, nilai \( r \) semakin lama semakin mengecil. Nilai yang semakin mengecil ini terjadi karena batasan \( 0 \le r \lt \lvert b \rvert \)
Misalkan \( r_1 \) adalah nilai \( r \) pada operasi pertama.
Pada operasi kedua, \( r_1 \) akan bertindak sebagai pembagi. Akibatnya, \( 0 \le r_2 \lt r_1 \)
Pada operasi ketiga, \( r_2 \) akan bertindak sebagai pembagi. Akibatnya, \( 0 \le r_3 \lt r_2 \lt r_1 \)
Dan seterusnya.. sampai \( r_k = 0 \) dan algoritma berhenti.
Contoh
Contoh 1
Carilah GCD dari \( 4 \) dan \( 6 \) dengan menggunakan Algoritma Euclid.
\( 4 = 6 \cdot 0 + 4 \)
Sisa bagi (remainder) \( r = 4 \)
Karena \( 4 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(4, 6) = \gcd(6, 4) \)
\( 6 = 4 \cdot 1 + 2 \)
Sisa bagi (remainder) \( r = 2 \)
Karena \( 2 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(6, 4) = \gcd(4, 2) \)
\( 4 = 2 \cdot 2 + 0 \)
Sisa bagi (remainder) \( r = 0 \)
Karena \( r = 0 \) maka algoritma berhenti dan \( \gcd(4, 2) = \gcd(2, 0) \)
Dari rentetan algoritma ini diperoleh:
\(
\begin{align*}
\gcd(4, 6) &= \gcd(6, 4) \\
&= \gcd(4, 2) \\
&= \gcd(2, 0) \\
&= 2
\end{align*}
\)
Dengan demikian, GCD dari \( 4 \) dan \( 6 \) adalah \( 2 \).
Contoh 2
Carilah GCD dari \( 252 \) dan \( 105 \) dengan menggunakan Algoritma Euclid.
\( 252 = 105 \cdot 2 + 42 \)
Sisa bagi (remainder) \( r = 42 \)
Karena \( 42 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(252, 105) = \gcd(105, 42) \)
\( 105 = 42 \cdot 2 + 21 \)
Sisa bagi (remainder) \( r = 21 \)
Karena \( 21 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(105, 42) = \gcd(42, 21) \)
\( 42 = 21 \cdot 2 + 0 \)
Sisa bagi (remainder) \( r = 0 \)
Karena \( r = 0 \) maka algoritma berhenti dan \( \gcd(42, 21) = \gcd(21, 0) \)
Dari rentetan algoritma ini diperoleh:
\(
\begin{align*}
\gcd(252, 105) &= \gcd(105, 42) \\
&= \gcd(42, 21) \\
&= \gcd(21, 0) \\
&= 21
\end{align*}
\)
Dengan demikian, GCD dari \( 252 \) dan \( 105 \) adalah \( 21 \).
Contoh 3
Carilah GCD dari \( 110 \) dan \( 490 \) dengan menggunakan Algoritma Euclid.
\( 110 = 490 \cdot 0 + 110 \)
Sisa bagi (remainder) \( r = 110 \)
Karena \( 110 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(110, 490) = \gcd(490, 110) \)
\( 490 = 110 \cdot 4 + 50 \)
Sisa bagi (remainder) \( r = 50 \)
Karena \( 50 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(490, 110) = \gcd(110, 50) \)
\( 110 = 50 \cdot 2 + 10 \)
Sisa bagi (remainder) \( r = 10 \)
Karena \( 10 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(110, 50) = \gcd(50, 10) \)
\( 50 = 10 \cdot 5 + 0 \)
Sisa bagi (remainder) \( r = 0 \)
Karena \( r = 0 \) maka algoritma berhenti dan \( \gcd(50, 10) = \gcd(10, 0) \)
Dari rentetan algoritma ini diperoleh:
\(
\begin{align*}
\gcd(110, 490) &= \gcd(490, 110) \\
&= \gcd(110, 50) \\
&= \gcd(50, 10) \\
&= \gcd(10, 0) \\
&= 10
\end{align*}
\)
Dengan demikian, GCD dari \( 110 \) dan \( 490 \) adalah \( 10 \).
Contoh 4
Carilah GCD dari \( -35 \) dan \( 120 \) dengan menggunakan Algoritma Euclid.
\( -35 = 120 \cdot (-1) + 85 \)
Sisa bagi (remainder) \( r = 85 \)
Karena \( 85 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(-35, 120) = \gcd(120, 85) \)
\( 120 = 85 \cdot 1 + 35 \)
Sisa bagi (remainder) \( r = 35 \)
Karena \( 35 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(120, 85) = \gcd(85, 35) \)
\( 85 = 35 \cdot 2 + 15 \)
Sisa bagi (remainder) \( r = 15 \)
Karena \( 15 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(85, 35) = \gcd(35, 15) \)
\( 35 = 15 \cdot 2 + 5 \)
Sisa bagi (remainder) \( r = 5 \)
Karena \( 5 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(35, 15) = \gcd(15, 5) \)
\( 15 = 5 \cdot 3 + 0 \)
Sisa bagi (remainder) \( r = 0 \)
Karena \( r = 0 \) maka algoritma berhenti dan \( \gcd(15, 5) = \gcd(5, 0) \)
Dari rentetan algoritma ini diperoleh:
\(
\begin{align*}
\gcd(-35, 120) &= \gcd(120, 85) \\
&= \gcd(85, 35) \\
&= \gcd(35, 15) \\
&= \gcd(15, 5) \\
&= \gcd(5, 0) \\
&= 5
\end{align*}
\)
Dengan demikian, GCD dari \( -35 \) dan \( 120 \) adalah \( 5 \).
Contoh 5
Carilah GCD dari \( 50 \) dan \( -39 \) dengan menggunakan Algoritma Euclid.
\( 50 = (-39) \cdot (-1) + 11 \)
Sisa bagi (remainder) \( r = 11 \)
Karena \( 11 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(50, -39) = \gcd(-39, 11) \)
\( -39 = 11 \cdot (-4) + 5 \)
Sisa bagi (remainder) \( r = 5 \)
Karena \( 5 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(-39, 11) = \gcd(11, 5) \)
\( 11 = 5 \cdot 2 + 1 \)
Sisa bagi (remainder) \( r = 1 \)
Karena \( 1 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(11, 5) = \gcd(5, 1) \)
\( 5 = 1 \cdot 5 + 0 \)
Sisa bagi (remainder) \( r = 0 \)
Karena \( r = 0 \) maka algoritma berhenti dan \( \gcd(5, 1) = \gcd(1, 0) \)
Dari rentetan algoritma ini diperoleh:
\(
\begin{align*}
\gcd(50, -39) &= \gcd(-39, 11) \\
&= \gcd(11, 5) \\
&= \gcd(5, 1) \\
&= \gcd(1, 0) \\
&= 1
\end{align*}
\)
Dengan demikian, GCD dari \( 50 \) dan \( -39 \) adalah \( 1 \). Berarti \( 50 \) dan \( -39 \) adalah dua bilangan yang relatif prima.
Contoh 6
Carilah GCD dari \( -14 \) dan \( -27 \) dengan menggunakan Algoritma Euclid.
\( -14 = (-27) \cdot 1 + 13 \)
Sisa bagi (remainder) \( r = 13 \)
Karena \( 13 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(-14, -27) = \gcd(-27, 13) \)
\( -27 = 13 \cdot (-3) + 12 \)
Sisa bagi (remainder) \( r = 12 \)
Karena \( 12 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(-27, 13) = \gcd(13, 12) \)
\( 13 = 12 \cdot 1 + 1 \)
Sisa bagi (remainder) \( r = 1 \)
Karena \( 1 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(13, 12) = \gcd(12, 1) \)
\( 12 = 1 \cdot 12 + 0 \)
Sisa bagi (remainder) \( r = 0 \)
Karena \( r = 0 \) maka algoritma berhenti dan \( \gcd(12, 1) = \gcd(1, 0) \)
Dari rentetan algoritma ini diperoleh:
\(
\begin{align*}
\gcd(-14, -27) &= \gcd(-27, 13) \\
&= \gcd(13, 12) \\
&= \gcd(12, 1) \\
&= \gcd(1, 0) \\
&= 1
\end{align*}
\)
Dengan demikian, GCD dari \( -14 \) dan \( -27 \) adalah \( 1 \). Berarti \( -14 \) dan \( -27 \) adalah dua bilangan yang koprima.
Contoh 7
Carilah GCD dari \(123456 \) dan \(60 \) dengan menggunakan Algoritma Euclid.
\( 123456 = 60 \cdot 2057 + 36 \)
Sisa bagi (remainder) \( r = 36\)
Karena \( 36 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(123456, 60) = \gcd(60, 36) \)
\( 60 = 36 \cdot 1 + 24 \)
Sisa bagi (remainder) \( r = 24 \)
Karena \( 24 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(60, 36) = \gcd(36, 24) \)
\( 36 = 24 \cdot 1 + 12 \)
Sisa bagi (remainder) \( r = 12 \)
Karena \( 12 \gt 0 \) maka algoritma dilanjutkan dan \( \gcd(36, 24) = \gcd(24, 12) \)
\( 24 = 12 \cdot 2 + 0 \)
Sisa bagi (remainder) \( r = 0 \)
Karena \( r = 0 \) maka algoritma berhenti dan \( \gcd(24, 12) = \gcd(12, 0) \)
Dari rentetan algoritma ini diperoleh:
\(
\begin{align*}
\gcd(123456, 60) &= \gcd(60, 36) \\
&= \gcd(36, 24) \\
&= \gcd(24, 12) \\
&= \gcd(12, 0) \\
&= 12
\end{align*}
\)
Dengan demikian, GCD dari \( 123456 \) dan \( 60 \) adalah \( 12 \).