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 \).

Last updated: 5 October 2026