İçerik

• adımlar
• Yöntem 1/2: Bölücü Algoritması
• Yöntem 2/2: Asal Faktörler
• İpuçları

İki tamsayının En Büyük Ortak Bölen (GCD), bu sayıların her birini bölen en büyük tamsayıdır. Örneğin, 20 ve 16 için gcd 4'tür (hem 16 hem de 20'nin büyük bölenleri vardır, ancak bunlar yaygın değildir - örneğin, 8, 16'nın bir bölenidir, ancak 20'nin böleni değildir). GCD'yi bulmak için "Öklid'in algoritması" adı verilen basit ve sistematik bir yöntem vardır. Bu makale size iki tamsayının en büyük ortak bölenini nasıl bulacağınızı gösterecektir.

adımlar

Yöntem 1/2: Bölücü Algoritması

1. 1 Herhangi bir eksi işaretini atlayın.
2. 2 Terminolojiyi öğrenin: 32'yi 5'e bölerken,
   • 32 - temettü
   • 5 - bölen
   • 6 - özel
   • 2 - kalan
3. 3 Sayılardan büyük olanı belirleyiniz. Bölünebilir olacak ve daha küçük sayı bölen olacaktır.
4. 4 Aşağıdaki algoritmayı yazın: (temettü) = (bölen) * (bölüm) + (kalan)
5. 5 Bölen yerine daha büyük bir sayı ve bölen yerine daha küçük bir sayı koyun.
6. 6 Büyük sayının küçük sayıya kaç kez bölündüğünü bulun ve sonucu bölüm yerine yazın.
7. 7 Kalanı bulun ve algoritmada uygun konuma yazın.
8. 8 Algoritmayı yeniden yazın, ancak (A) önceki böleni yeni bir bölen olarak ve (B) önceki kalanı yeni bir bölen olarak yazın.
9. 9 Kalan 0 olana kadar önceki adımı tekrarlayın.
10. 10 Son bölen en büyük ortak bölen (GCD) olacaktır.
11. 11 Örneğin, 108 ve 30 için GCD'yi bulalım:
12. 12 İlk satırdaki 30 ve 18 sayılarının ikinci satırı nasıl oluşturduğuna dikkat edin. Ardından 18 ve 12 üçüncü sırayı, 12 ve 6 ise dördüncü sırayı oluşturur. 3, 1, 1 ve 2'nin katları kullanılmaz. Bölünenin bölen tarafından bölünebilme sayısını temsil ederler ve bu nedenle her satır için benzersizdirler.

Yöntem 2/2: Asal Faktörler

1. 1 Herhangi bir eksi işaretini atlayın.
2. 2 Sayıların asal çarpanlarını bulun. Bunları resimde gösterildiği gibi sunun.
   • Örneğin, 24 ve 18 için:
     • 24- 2x2x2x3
     • 18- 2x3x3
   • Örneğin, 50 ve 35 için:
     • 50- 2x5x5
     • 35- 5x7
3. 3 Ortak asal çarpanları bulun.
   • Örneğin, 24 ve 18 için:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Örneğin, 50 ve 35 için:
     • 50 - 2 kez 5 x 5
     • 35- 5 x 7
4. 4 Ortak asal çarpanları çarpın.
   • 24 ve 18 için çarpın 2 ve 3 ve Al 6... 6, 24 ve 18'in en büyük ortak paydasıdır.
   • 50 ve 35 için çarpılacak bir şey yok. 5 Tek ortak asal faktördür ve GCD'dir.
5. 5 Yaptı!

İpuçları

• Bunu yazmanın bir yolu şudur: temettü> mod bölücü> = kalan; Mod b = 0 ise GCD (a, b) = b ve aksi takdirde gcd (a, b) = gcd (b, a mod b) olur.
• Örnek olarak, OBEB'yi (-77.91) bulalım. İlk olarak, -77 yerine 77 kullanın: GCD (-77.91), GCD'ye (77.91) dönüşür. 77, 91'den küçüktür, bu yüzden onları değiştirmeliyiz, ancak yapmazsak algoritmanın nasıl çalıştığını düşünün. 77 mod 91'i hesaplarken 77 elde ederiz (77 = 91 x 0 + 77). Bu sıfır olmadığı için (b, a mod b), yani OBEB (77.91) = OBEB (91.77) durumunu ele alıyoruz. 91 mod 77 = 14 (14 kalan). Sıfır değildir, dolayısıyla OBEB (91.77) OBEB (77.14) olur. 77 mod 14 = 7. Bu sıfır değildir, dolayısıyla OBEB (77.14) OBEB (14.7) olur. 14 mod 7 = 0 (14/7 = 2'den beri kalansız). Cevap: OBEB (-77.91) = 7.
• Açıklanan yöntem, kesirleri basitleştirmek için çok kullanışlıdır. Yukarıdaki örnekte: -77/91 = -11/13, çünkü 7, -77 ve 91'in en büyük ortak paydasıdır.
• Eğer a ve b sıfıra eşitse, sıfır olmayan herhangi bir sayı onların bölenidir, yani bu durumda GCD yoktur (matematikçiler 0 ve 0'ın en büyük ortak böleninin 0 olduğuna inanırlar).