Ring Euclid

1. Definisi Ring Euclid

Misalkan R ring komutatif tanpa pembagi nol. Ring R disebut Ring Euclid jika terdapat pemetaan d : R → ℕ ∪ {0} yang memenuhi sifat-sifat:

• d(0) = 0.

• (∀a, b ∈ R\{0}). d(a) ≤ d(ab)

• (∀a, b ∈ R\{0})(∃q, r ∈ R) ∋ a = bq + r ∧ [r = 0 ∨ d(r) < d(b)]

Fungsi d ini disebut fungsi penilaian Euclid.

Contoh:

Misal ring J[i] = {a + bi : a, b ∈ ℤ} ⊆ ℂ. Ring J[i] komutatif tanpa pembagi nol.

Misal didefinisikan d : R → ℕ ∪ {0} dengan d(a + bi) = a² + b², perhatikan

• d(0 + 0i) = 0 + 0 = 0

• Untuk sebarang c₁, c₂ ∈ J[i]\{0} dengan c₁ = a₁ + b₁i, c₂ = a₂ + b₂i; a₁² + b₁² ≥ 1 > 0; a₂² + b₂² ≥ 1 > 0 (ini benar karena kuadrat bilangan bulat taknol selalu lebih dari atau sama dengan 1).

d(c₁) = d(a₁ + b₁i) = a₁² + b₁² ≥ 1 > 0.

d(c₁c₂) = d[(a₁ + b₁i)(a₂ + b₂i)] = d[(a₁a₂ – b₁b₂) + i(a₁b₂ + b₁a₂)] = (a₁a₂ – b₁b₂)² + (a₁b₂ + b₁a₂)² = a₁²a₂² + b₁²b₂² – 2a₁a₂b₁b₂ + a₁²b₂² + b₁²a₂² + 2a₁a₂b₁b₂ = a₁²a₂² + b₁²b₂² + a₁²b₂² + b₁²a₂² = (a₁² + b₁²)(a₂² + b₂²) = d(c₁)·(a₂² + b₂²) = d(c₁)·d(c₂) ≥ d(c₁). Ini benar karena hasil kali sesama bilangan asli selalu bilangan asli.

• Lakukan pembagian

c₁/c₂ = (a₁ + b₁i)/(a₂ + b₂i) = [(a₁ + b₁i)(a₂ – b₂i)]/[(a₂ + b₂i)(a₂ – b₂i)] = [(a₁a₂ + b₁b₂) + i(a₂b₁ – a₁b₂)]/(a₂² + b₂²)

= (a₁a₂ + b₁b₂)/(a₂² + b₂²) + i(a₂b₁ – a₁b₂)/(a₂² + b₂²)

Misal k₁ = (a₁a₂ + b₁b₂)/(a₂² + b₂²) dan k₂ = (a₂b₁ – a₁b₂)/(a₂² + b₂²)

Pilih q₁, q₂ ∈ ℤ ∋ |k₁ – q₁| ≤ ½ ∧ |k₂ – q₂| ≤ ½ untuk membentuk q = q₁ + q₂i.

Misal c₁ – c₂q = r = r₁ + r₂i, terdapat ketaksamaan |r₁| ≤ ½|a₂| dan |r₂| ≤ ½|b₂|, sehingga diperoleh

d(r) = r₁² + r₂² ≤ ½²a₂² + ½²b₂² = ¼a₂² + ¼b₂² = ¼(a₂² + b₂²) < a₂² + b₂².

Jadi, dengan fungsi d ini J[i] merupakan ring Euclid.

2. Hirarki Ring Euclid

A. Field

Setiap field merupakan ring Euclid.

Bukti:

Misal F field, jelas bahwa F ring komutatif tanpa pembagi nol. Misal dibuat fungsi d : F → ℕ ∪ {0} dengan

(∀a ∈ F). d(a) = 0, berikut ini sifat-sifatnya:

• Jelas bahwa d(0) = 0.

• Untuk sebarang a, b ∈ F selalu d(a) = d(ab) = 0.

• Untuk sebarang a, b ∈ F\{0} berlaku

a = a·1 = a(b⁻¹b) = (ab⁻¹)b = (ab⁻¹)b + 0

Jadi, dengan fungsi d ini, F merupakan ring Euclid.

B. Ring Ideal Utama

Setiap ring Euclid merupakan ring ideal utama.

Bukti:

Misal R ring Euclid dengan fungsi penilaian Euclid d. Misal S sebarang ideal di R.

Untuk S = {0}, jelas bahwa S = 〈0〉 sehingga merupakan ideal utama.

Untuk S ≠ {0} ⇔ (∃a ∈ S) ∋ a ≠ 0:

Misal T = {d(a) : a ∈ S\{0}}, jelas bahwa T ⊆ ℕ ∪ {0}.

Misal k bilangan terkecil di dalam T, jelas (∃b ∈ S\{0}) ∋ d(b) = k.

Ambil sebarang a, b ∈ S\{0} ⊂ R. Karena R ring Euclid, (∃q, r ∈ R) ∋ a = bq + r ∧ [r = 0 ∨ d(r) < d(b)].

Karena a ∈ S dan bq ∈ S (karena b ∈ S ∧ q ∈ R dan S ideal), maka r = a – bq ∈ S dengan r = 0 ∨ d(r) < d(b).

Karena d(b) elemen terkecil dari T, dan r ∈ S, mustahil d(r) < d(b), sehingga diharuskan r = 0.

Kita peroleh (∃q ∈ R) ∋ a = bq.

Jadi, (∀a ∈ S)(∃q ∈ R) ∋ a = bq. Dengan kata lain, S adalah ideal utama yang dibangun oleh b.

Karena S sebarang ideal di R, disimpulkan setiap ideal di R merupakan ideal utama, termasuk R.

Misal R = 〈c〉, berarti (∀a ∈ R)(∃p ∈ R) ∋ a = cp.

Pertimbangkan c = ct, t ∈ R. Untuk a = cp, perhatikan:

at = (cp)t = (pc)t = p(ct) = pc = cp = a.

Jadi, t merupakan elemen satuan di R. Lebih lanjut, R merupakan ring ideal utama.

3. Keterbagian

A. Faktor dan Kelipatan

Misal R ring komutatif, dan diberikan a, b ∈ R dengan b ≠ 0. Dikatakan b faktor a atau b membagi habis a (semakna dengan a kelipatan b), jika (∃k ∈ R) ∋ a = bk.

b membagi a disimbolkan dengan b | a, sedangkan b tidak membagi a disimbolkan dengan b ∤ a.

B. Faktor Persekutuan Terbesar

Misal R ring komutatif, dan diberikan a, b ∈ R. Elemen d ∈ R disebut faktor persekutuan terbesar (FPB) dari a dan b jika:

• d | a ∧ d | b

• (∀c ∈ R). c | a ∧ c | b ⇒ c | d

Hal ini dinotasikan (a, b) = d.

C. Kelipatan Persekutuan Terkecil

Misal R ring komutatif, dan diberikan a, b ∈ R. Elemen d ∈ R disebut kelipatan persekutuan terkecil (KPK) dari a dan b jika:

• a | d ∧ b | d

• (∀c ∈ R). a | c ∧ a | c ⇒ d | c

D. Eksistensi Kombinasi FPB

Misal R ring Euclid. Misal diberikan a, b ∈ R\{0}. Jika FPB dari a dan b adalah c, maka

(∃k, l ∈ R) ∋ ak + bl = c.

E. Algoritma Euclid untuk FPB

Misalkan R suatu ring Euklid, dan a, b ∈ R\{0}. FPB dari a dan b dapat diperoleh dari algoritma pembagian:

b = q₀a + r₁;    dengan d(r₁) < d(a)

a = q₁r₁ + r₂;    dengan d(r₂) < d(r₁)

r₁ = q₂r₂ + r₃;    dengan d(r₃) < d(r₂)

⋮

rₙ₋₂ = qₙ₋₁rₙ₋₁ + rₙ;    dengan d(rₙ) < d(rₙ₋₁)

rₙ₋₁ = qₙrₙ;

dengan r₁, r₂, ··· , rₙ, q₀, q₁, ··· , qₙ ∈ R\{0}.

FPB dari a dan b adalah rₙ.

Dengan substitusi balik dari algoritma Euclid, akan diperoleh kombinasi ak + bl = rₙ.

Contoh penggunaan:

Tentukan (10587, 534) dan tentukan kombinasi linear 10587k + 534l = (10587, 534)

10587 = 534·19 + 441

534 = 441·1 + 93

441 = 93·4 + 69

93 = 69·1 + 24

69 = 24·2 + 21

24 = 21·1 + 3

21 = 3·7 + 0

Sehingga diperoleh (10587, 534) = 3

Selanjutnya,

3 = 24 − 21·1

= 24 − (69 − 24·2)

= 24·3 − 69

= (93 − 69)·3 − 69

= 93·3 − 69·4

= 93·3 − (441 − 93·4)·4

= 93·19 − 441·4

= (534 − 441·1)·19 − 441·4

= 534·19 − 441·23

= 534·19 − (10587 − 534·19)·23

= 534·456 − 10587·23

Jadi, FPB dari 10587 dan 534 adalah 3, sedangkan nilai k dan l yang memenuhi 10587k + 534l = 3 adalah k = −23 dan l = 456.