Öklid algoritmasını okulda öğrenmek. Öklid Algoritması - En Büyük Ortak Böleni Bulmak

E-ticarette yaygın. Algoritma ayrıca Sturm yönteminde doğrusal Diophantine denklemlerinin çözümünde, sürekli kesirlerin oluşturulmasında kullanılır. Öklid'in algoritması, Lagrange'ın dört karenin toplamı hakkındaki teoremi ve aritmetiğin temel teoremi gibi modern sayı teorisindeki teoremleri kanıtlamak için ana araçtır.

Ansiklopedik YouTube

1 / 5

✪ Matematik. Doğal sayılar: Öklid'in algoritması. Foxford Çevrimiçi Öğrenim Merkezi

✪ Öklid'in algoritması

✪ Öklid'in algoritması, hızlı yol gcd'yi bul

✪ Matematik 71. En büyük ortak bölen. Öklid Algoritması - Eğlenceli Bilimler Akademisi

✪ 20 while Döngü Öklid Python Algoritması

altyazılar

Hikaye

Antik Yunan matematikçiler buna algoritma adını verdiler. ἀνθυφαίρεσις veya ἀνταναίρεσις - "karşılıklı çıkarma". Bu algoritma Öklid tarafından keşfedilmemiştir, çünkü daha önce bahsedilmiştir. Topeka Aristo. Öklid'in "Öğeler"inde, iki kez anlatılır - Kitap VII'de iki doğal sayının en büyük ortak bölenini bulmak için ve Kitap X'te iki homojen niceliğin en büyük ortak ölçüsünü bulmak için. Her iki durumda da, iki parçanın "ortak ölçüsünü" bulmak için algoritmanın geometrik bir açıklaması verilir.

Tanım

tamsayılar için Öklid'in algoritması

İzin vermek bir (\görüntü stili bir) Ve b (\görüntü stili b)- aynı anda sıfıra eşit olmayan tamsayılar ve bir dizi sayı

a > b > r 1 > r 2 > r 3 > r 4 > … > r n (\displaystyle a>b>r_(1)>r_(2)>r_(3)>r_(4)>\ \noktalar \ >r_(n))

gerçeği tarafından belirlenir, her r k (\displaystyle r_(k))- bu, önceki sayının önceki sayıya bölümünden kalandır ve sondan bir önceki sayının son sayıya bölünmesinden kalandır, yani:

a = b q 0 + r 1 , (\displaystyle a=bq_(0)+r_(1),) b = r 1 q 1 + r 2 , (\displaystyle b=r_(1)q_(1)+r_(2),) r 1 = r 2 q 2 + r 3 , (\displaystyle r_(1)=r_(2)q_(2)+r_(3),) ⋯ (\displaystyle \cdots ) r k − 2 = r k − 1 q k − 1 + r k , (\displaystyle r_(k-2)=r_(k-1)q_(k-1)+r_(k),) ⋯ (\displaystyle \cdots ) r n − 2 = r n − 1 q n − 1 + r n , (\displaystyle r_(n-2)=r_(n-1)q_(n-1)+r_(n),) r n - 1 = r n q n . (\displaystyle r_(n-1)=r_(n)q_(n).)

Sonra gcd( A, B), en büyük ortak bölen A Ve B, eşittir R n , bu dizinin sıfır olmayan son üyesi.

Varoluşçok R 1 , R 2 , ..., R n , yani kalanlı bölme olasılığı M Açık N herhangi bir bütün için M ve bütün N≠ 0 üzerinde tümevarımla kanıtlanmıştır M.

doğruluk bu algoritma aşağıdaki iki ifadeden çıkar:

• İzin vermek A = B⋅Q + R, o zaman ebob(a, b) = ebob(b, r).

Kanıt

• GCD( R, 0) = R sıfır olmayan herhangi biri için R(çünkü 0, sıfırdan başka herhangi bir tam sayıya bölünebilir).

Öklid'in geometrik algoritması

İki uzunluk parçası verilsin A Ve B. Küçük parçayı büyük parçadan çıkarın ve büyük parçayı ortaya çıkan farkla değiştirin. Segmentler eşit olana kadar bu işlemi tekrarlayın. Bu olursa, orijinal bölümler ölçülebilirdir ve elde edilen son bölüm onların en büyük ortak ölçüsüdür. Ortak bir ölçü yoksa süreç sonsuzdur. Bu formda, algoritma Öklid tarafından tarif edilir ve bir pusula ve cetvel kullanılarak gerçekleştirilir.

Örnek

Göstermek için, Öklid algoritması gcd'yi bulmak için kullanılacaktır. A= 1071 ve B= 462. Başlangıç ​​olarak, 462'den küçük bir fark elde edene kadar 1071'den 462'nin katlarını çıkarın. 462'yi iki kez çıkarmalıyız, ( Q 0 = 2), kalan 147 ile kalan:

1071 = 2 × 462 + 147.

Sonra 147'nin katını 462'den 147'den küçük bir fark elde edene kadar çıkarırız. 147'yi üç kez çıkarmalıyız ( Q 1 = 3), kalan 21 ile kalan:

462 = 3x147 + 21.

Sonra 21'in katını 147'den 21'den küçük bir fark elde edene kadar çıkarırız. 21'i yedi kez çıkarmalıyız ( Q 2 = 7), kalansız kalan:

147 = 7x21 + 0.

Böylece a > b > dizisi R 1 > R 2 > R 3 > … > R n bu özel durumda şöyle görünür:

1071 > 462 > 147 > 21.

Son kalan sıfır olduğu için algoritma 21 ve ebob(1071, 462) = 21 ile bitiyor.

Tablo biçiminde, adımlar aşağıdaki gibiydi:

Uygulamalar

Genişletilmiş Öklid Algoritması ve Bezout İlişkisi

için formüller r ben (\displaystyle r_(i))şu şekilde yeniden yazılabilir:

r 1 = a + b (− q 0) (\displaystyle r_(1)=a+b(-q_(0))) r 2 = b − r 1 q 1 = a (− q 1) + b (1 + q 1 q 0) (\displaystyle r_(2)=b-r_(1)q_(1)=a(-q_( 1)+b(1+q_(1)q_(0))) ⋮ (\displaystyle \vdots ) GCD (a , b) = r n = a s + b t (\displaystyle (a,b)=r_(n)=as+bt)

Burada S Ve T tüm. En büyük ortak bölenin bu temsiline Bezout bağıntısı denir ve sayılar S Ve T- katsayılar Bezu . Bezout'un bağıntısı, Öklid lemmasının ispatında ve aritmetiğin ana teoreminde anahtardır.

Devam eden kesirler

Öklid'in algoritması, sürekli kesirler ile oldukça yakından ilgilidir. Davranış A/B sürekli bir kesir temsilini kabul eder:

bir b = [ q 0 ; q 1 , q 2 , ⋯ , q n ] (\displaystyle (\frac (a)(b))=).

Bu durumda, son terim olmadan devam eden kesrin Bezout katsayılarının oranına eşittir. T/S eksi işareti ile alınır:

[ q 0 ; q 1 , q 2 , ⋯ , q n - 1 ] = - t s (\displaystyle =-(\frac (t)(s))).

Öklid algoritmasını tanımlayan eşitlik dizisi şu şekilde yeniden yazılabilir:

a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k - 2 r k - 1 = q k + r k r k - 1 ⋮ r N - 2 r N - 1 = q N (\displaystyle (\begin(hizalı)(\frac (a)(b))&=q_(0)+(\frac (r_(0))(b))\\(\frac (b) )(r_(0)))&=q_(1)+(\frac (r_(1))(r_(0)))\\(\frac (r_(0))(r_(1)))& =q_(2)+(\frac (r_(2))(r_(1))\\&()\ \vdots \\(\frac (r_(k-2))(r_(k-1)) )&=q_(k)+(\frac (r_(k))(r_(k-1)))\\&()\ \vdots \\(\frac (r_(N-2))(r_ (N-1)))&=q_(N)\end(hizalı)))

Bir denklemin sağ tarafındaki son terim her zaman aşağıdaki denklemin sol tarafının tersine eşittir. Bu nedenle, ilk iki denklem şu şekilde birleştirilebilir:

a b = q 0 + 1 q 1 + r 1 r 0 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (r_() 1)(r_(0))))))

Üçüncü eşitlik, ifadenin paydasını değiştirmek için kullanılabilir. R 1 /R 0 , şunu elde ederiz:

a b = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\ cfrac (1)(q_(2)+(\cfrac (r_(2))(r_(1))))))))

Son Kalıntı Oranı R k /R k−1 her zaman dizideki bir sonraki eşitlik kullanılarak değiştirilebilir ve son denkleme kadar böyle devam eder. Sonuç, sürekli bir kesirdir:

a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [ q 0 ; q 1 , q 2 , … , q N ] (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (1)(q_) (2)+(\cfrac (1)(\ddots +(\cfrac (1)(q_(N))))))))=)

Polinomlar için genelleştirilmiş Öklid algoritması

Öklid Algoritması ve Genişletilmiş Öklid Algoritması doğal olarak polinomların   halkasına genelleştirir k[X] keyfi bir alan üzerinden bir değişkenden k, çünkü bu tür polinomlar için kalanlı bölme işlemi tanımlanır. Öklid'in polinomlar için algoritmasını yürütürken, Öklid'in tamsayılar için algoritmasına benzer şekilde, bir dizi polinom kalanları (PRS) elde edilir.

Yüzük örneği Z[X]

devam(f) tanımı gereği Z[x]'ten f(x) polinomunun katsayılarının gcd'si olsun - içerik polinom. f(x)'in cont(f)'ye bölümünün bölümüne denir ilkel kısım polinom f(x) ve primpart(f(x)) ile gösterilir. Bu tanımlar, iki polinomun gcd'sini bulmak için gerekli olacaktır. p 1 (x) Ve p 2 (x) Z[x] halkasında. Tamsayılar üzerindeki polinomlar için aşağıdakiler doğrudur:

C Ö n t ((\displaystyle devam() NODNOD ( c Ö n t (p 1 (x)) , c Ö n t (p 2 (x)) ) , (\displaystyle \(cont(p_(1)(x))),cont(p_(2)(x))\),)

P r ben m p a r t ((\displaystyle primpart() GCD ( p 1 (x) , p 2 (x) )) = (\displaystyle \(p_(1)(x),p_(2)(x)\))=) GCD ( ilk kısım (p 1 (x)) , ilk kısım (p 2 (x)) ) . (\displaystyle \(primpart(p_(1)(x))),primpart(p_(2)(x))\).)

Böylece, keyfi iki polinomun gcd'sini bulma sorunu, ilkel polinomların gcd'sini bulma sorununa indirgenmiştir.

Güçleri arasındaki ilişkinin sağlandığı Z[x]'ten p 1 (x) ve p 2 (x) iki ilkel polinom olsun: derece(p 1 (x)) = m ve derece(p 2 (x) ) = n, m > n. Polinomların bir kalanla bölünmesi, bölenin en yüksek katsayısının bölenin en yüksek katsayısına tam olarak bölünebilirliğini ifade eder; genel durumda, kalanla bölme gerçekleştirilemez. Bu nedenle, bir sözde bölme algoritması tanıtılır, ancak yine de kişinin kendileri tamsayılar üzerinden polinomlar kümesine ait olacak bir sözde bölüm ve bir sözde kalan (prem) elde etmesine izin verir.

Sözde bölme derken, bölmenin kendisinden önce polinomun çarpılmasının geldiğini kastediyoruz. p 1 (x) (\displaystyle p_(1)(x)) Açık (l c (p 2 (x)))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), yani

L c (p 2 (x)) m - n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x) , derece ⁡ (r (x))< deg ⁡ (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}

Nerede q (x) (\displaystyle q(x)) Ve r (x) (\displaystyle r(x))- sırasıyla psödopartial ve psödoresidue.

Bu yüzden, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1)(x),p_(2)(x)\in Z[x]), Dahası derece ⁡ (p 1) = n 1 ≥ derece ⁡ (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). O zaman Öklid'in algoritması aşağıdaki adımlardan oluşur:

1. GCD içeriğinin hesaplanması:

C:= (\görüntü stili c:=) GCD ( c Ö n t (p 1) , c Ö n t (p 2) ) (\displaystyle \(devam(p_(1))),devam(p_(2))\)).

2. İlkel parçaların hesaplanması:

P 1 ′ (x) := p r ben m p a r t (p 1 (x)) ; (\displaystyle p_(1)"(x):=primpart(p_(1)(x));)

P 2 ′ (x) := p r ben m p a r t (p 2 (x)) . (\displaystyle p_(2)"(x):=primpart(p_(2)(x))).)

3. Bir dizi polinom kalıntısı oluşturmak:

P 1 ′ (x) , (\displaystyle p_(1)"(x),)

P 2 ′ (x) , (\displaystyle p_(2)"(x),)

P 3 (x) := p r e m (p 1 ′ (x) , p 2 ′ (x)) , (\displaystyle p_(3)(x):=prem(p_(1)"(x),p_(2) )"(X)))

P 4 (x) := p r e m (p 2 ′ (x) , p 3 (x)) , (\displaystyle p_(4)(x):=prem(p_(2)"(x),p_(3) (X)))

P 5 (x) := p r e m (p 3 (x) , p 4 (x)) , (\displaystyle p_(5)(x):=prem(p_(3)(x),p_(4)(x) ))))

. . . (\görüntü stili...)

P h (x) := p r e m (p h - 2 (x) , p h - 1 (x)) . (\displaystyle p_(h)(x):=prem(p_(h-2)(x),p_(h-1)(x))).)

En büyük ortak böleni

Tanım 2

Bir a doğal sayısı $b$ doğal sayısıyla bölünebiliyorsa, $b$'a $a$'ın böleni, $a$ sayısına da $b$'ın katı denir.

$a$ ve $b$ doğal sayılar olsun. $c$ sayısına hem $a$ hem de $b$ için ortak bölen denir.

$a$ ve $b$ sayılarının ortak bölenleri kümesi sonludur, çünkü bu bölenlerin hiçbiri $a$'dan büyük olamaz. Bu, bu bölenler arasında $a$ ve $b$ sayılarının en büyük ortak böleni olarak adlandırılan en büyüğü olduğu anlamına gelir ve bunu belirtmek için notasyon kullanılır:

$gcd \ (a;b) \ ​​​​veya \ D \ (a;b)$

İki sayının en büyük ortak bölenini bulmak için:

1. 2. adımda bulunan sayıların çarpımını bulun. Ortaya çıkan sayı, istenen en büyük ortak bölen olacaktır.

örnek 1

$121$ ve $132.$ sayılarının gcd'sini bulun.

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Bu sayıların açılımına dahil olan sayıları seçin

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

2. adımda bulunan sayıların çarpımını bulun. Ortaya çıkan sayı, istenen en büyük ortak bölen olacaktır.

$gcd=2\cdot 11=22$

Örnek 2

$63$ ve $81$ monomlarının GCD'sini bulun.

Sunulan algoritmaya göre bulacağız. Bunun için:

Sayıları asal çarpanlara ayıralım

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Bu sayıların açılımına dahil olan sayıları seçiyoruz.

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

2. adımda bulunan sayıların çarpımını bulalım. Ortaya çıkan sayı istenen en büyük ortak bölen olacaktır.

$gcd=3\cdot 3=9$

Sayı bölenleri kümesini kullanarak iki sayının GCD'sini başka bir şekilde bulabilirsiniz.

Örnek 3

$48$ ve $60$ sayılarının gcd'sini bulun.

Çözüm:

$48$'ın bölenleri kümesini bulun: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$

Şimdi $60$'ın bölenleri kümesini bulalım:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\)$

Bu kümelerin kesişimini bulalım: $\left\((\rm 1,2,3,4,6,12)\right\)$ - bu küme, $48$ ve $60 sayılarının ortak bölenleri kümesini belirleyecektir $. Bu kümedeki en büyük eleman $12$ sayısı olacaktır. Yani 48$ ve 60$'ın en büyük ortak böleni 12$'dır.

NOC'un tanımı

Tanım 3

doğal sayıların ortak katı$a$ ve $b$, hem $a$ hem de $b$'ın katı olan bir doğal sayıdır.

Sayıların ortak katları, aslına kalansız bölünebilen sayılardır. Örneğin, $25$ ve $50$ sayıları için, ortak katlar $50,100,150,200$ vb. olacaktır.

En küçük ortak kat, en küçük ortak kat olarak adlandırılır ve LCM$(a;b)$ veya K$(a;b)$ ile gösterilir.

İki sayının LCM'sini bulmak için şunlara ihtiyacınız vardır:

1. Sayıları asal çarpanlara ayırma
2. Birinci sayının parçası olan çarpanları yazın ve onlara ikincinin parçası olan ve birinciye gitmeyen çarpanları ekleyin.

Örnek 4

$99$ ve $77$ sayılarının LCM'sini bulun.

Sunulan algoritmaya göre bulacağız. Bunun için

Sayıları asal çarpanlara ayırma

$99=3\cdot 3\cdot 11$

Birinci maddede yer alan faktörleri yazınız.

onlara ikincinin parçası olan ve birinciye gitmeyen faktörleri ekleyin

2. adımda bulunan sayıların çarpımını bulun. Ortaya çıkan sayı, istenen en küçük ortak kat olacaktır.

$LCC=3\cdot 3\cdot 11\cdot 7=693$

Sayıların bölen listelerini derlemek genellikle çok zaman alır. Öklid algoritması adı verilen GCD'yi bulmanın bir yolu var.

Euclid'in algoritmasının dayandığı ifadeler:

$a$ ve $b$ doğal sayılarsa ve $a\vdots b$ ise, $D(a;b)=b$

$a$ ve $b$ doğal sayılarsa, $b

$D(a;b)= D(a-b;b)$ kullanarak, biri diğerine bölünebilen bir sayı çiftine ulaşana kadar incelenen sayıları art arda azaltabiliriz. O zaman bu sayılardan küçük olanı, $a$ ve $b$ sayıları için istenen en büyük ortak bölen olacaktır.

GCD ve LCM'nin Özellikleri

1. $a$ ve $b$'ın herhangi bir ortak katı K$(a;b)$ ile bölünebilir
2. $a\vdots b$ ise, K$(a;b)=a$

K$(a;b)=k$ ve $m$-doğal sayı ise, K$(am;bm)=km$

$d$, $a$ ve $b$ için ortak bir bölen ise, K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d) ) $

$a\vdots c$ ve $b\vdots c$ ise, $\frac(ab)(c)$, $a$ ve $b$'ın ortak katıdır

$a$ ve $b$ herhangi bir doğal sayı için eşitlik

$D(a;b)\cdot K(a;b)=ab$

$a$ ve $b$'ın herhangi bir ortak böleni, $D(a;b)$'ın bölenidir

Öklid'in algoritması iki tamsayının en büyük ortak bölenini (gcd) bulmanın bir yoludur. Algoritmanın orijinal versiyonu, GCD çıkarma işlemiyle bulunduğunda, Öklid (MÖ 3. yüzyıl) tarafından keşfedilmiştir. Şu anda, bu yöntem daha verimli olduğundan, Öklid algoritması tarafından GCD hesaplanırken bölme daha sık kullanılmaktadır.

Bölünerek gcd'yi hesaplama

Bir sayı çiftinin en büyük ortak böleni, çiftin her iki sayısını bölen en büyük sayıdır. 108 ve 72 sayıları için OBEB hesaplamak istensin. Bölme hesaplama algoritması aşağıdaki gibi olacaktır:

1. Büyük sayıyı (bölünen) küçük olana (bölen) bölün: 108 / 72 = 1, kalan 36.
2. Kalan sıfıra eşit olmadığı için böleni bölünebilir, kalanı bölen yapacağız: 72 / 36 = 2, kalan 0.
3. Kalan sıfır olduğunda, bölen, verilen sayı çifti için istenen gcd'dir. Yani ebob(108, 72) = 36. Nitekim 108/36 = 3 ve 72/36 = 2.

Bu algoritmada bölme işlemi kalan sıfır olana kadar tekrarlanır. O olduğunda GCD, son bölümün böleni. Örneğin, OBEB(106, 16)'yı bulmak istiyorsunuz:

1. 106 / 16 = 6, kalan 10
2. 16 / 10 = 1, kalan 6
3. 10 / 6 = 1, kalan 4
4. 6 / 4 = 1, kalan 2
5. 4 / 2 = 2, kalan 0
6. gcd(106, 16) = 2

Çıkarma yoluyla GCD hesaplaması

Çıkarma ile OBEB bulunurken sıfıra ulaşması da gerekir. Algoritma, bölme yöntemine benzer, ancak burada, sonraki her aşamada, çıkarılan ve önceki adımdan fark çıkarılır ve azaltılır. Küçük sayı her zaman büyük sayıdan çıkarılır. Bu tür bir algoritma yalnızca pozitif tamsayılar için uygundur.

OBEB(108, 72)'yi bulmak istensin:

1. 108 - 72 = 36
2. 72 - 36 = 36
3. 36 - 36 = 0
4. gcd(108, 72) = 36

gcd(44, 60)'yi bulun:

1. 60 - 44 = 16
2. 44 - 16 = 28
3. 28 - 16 = 12
4. 16 - 12 = 4
5. 12 - 4 = 8
6. 8 - 4 = 4
7. 4 - 4 = 0
8. gcd(44, 60) = 4

Bu algoritma bazen farklı tarif edilir. Çıkarma, bir sayının diğerini böldüğü adımda daha önce sona erer. Yani, çıkarma işlemini bölünebilirlik testi ile birleştirir. O zaman 44 ve 60 için OBEB bulmak şöyle görünecektir:

1. 44, 60'ı eşit olarak böler mi? HAYIR. 60 - 44 = 16.
2. 16, 44'ü eşit olarak böler mi? HAYIR. 44 - 16 = 28.
3. 16, 28'i eşit olarak böler mi? HAYIR. 28 - 16 = 12.
4. 12, 16'yı eşit olarak böler mi? HAYIR. 16 - 12 = 4.
5. 4, 12'yi eşit olarak böler mi? Evet. Yani ebob(44, 60) = 4.

Not, OBEB bir bölüm değil, bölendir. Örnekte 12'yi 4'e bölersek bölüm 3'ü elde ederiz. Ancak bu OBEB değildir.

Öklid algoritmasının kanıtı

Bir çiftten bir doğal sayı diğerini bölerse, gcd'lerinin küçük olanına eşit olacağı gerçeğini hesaba katalım. Bunu şu şekilde yazabilirsiniz:

a / b tamsayı ise, o zaman ebob(a, b) = b. Örneğin, ebob(15, 5) = 5.

Böylece, sonunda biri diğerini bölen bir sayı çiftine gelirsek, o zaman küçük olan her ikisi için de en büyük ortak bölen olacaktır. Öklid'in algoritması tarafından aranan böyle bir sayı çiftidir: bir sayı diğerini tamamen böler.

İkinci gerçek. Bir sayı diğerinden büyükse, en büyük ortak bölenlerinin çiftten daha küçük sayının en büyük ortak bölenine ve daha büyük ve daha küçük sayılar arasındaki farka eşit olduğunu kanıtlamak gerekir. Bu şu şekilde yazılabilir:

Eğer bir< b, то НОД(a, b) = НОД(a, b - a).

ebob(a, b) = ebob(a, b - a) olduğunu aşağıdaki gibi ispatlayabiliriz. b - a = c olsun. Herhangi bir x sayısı a ve b'yi bölerse, c'yi de böler. Sonuçta, a ve b farklıysa, bölen onlara bir tam sayı, ancak farklı sayıda uyar. Ve birini diğerinden çıkarırsanız, bölen de sonuçta ortaya çıkan farka bir tam sayıyı sığdırmalıdır.

A ve b'yi art arda azaltırsak, er ya da geç, daha büyük olanı tamamen bölen daha küçük bir değere geleceğiz. Böyle bir çiftten küçük olanı, orijinal doğal sayı çifti için en büyük ortak bölen olacaktır. Öklid'in algoritmasının amacı budur.

GCD'yi iki ana yolla bulmak için iki ana yöntemi ele alalım: Öklid algoritmasını kullanarak ve faktoring yaparak. İki, üç ve daha fazla sayı için her iki yöntemi de uygulayalım.

GCD'yi bulmak için Öklid'in algoritması

Öklid'in algoritması, iki pozitif sayının en büyük ortak bölenini hesaplamayı kolaylaştırır. Öklid algoritmasının formüllerini ve ispatını En Büyük Ortak Bölen: Determinant, Örnekler bölümünde vermiştik.

Algoritmanın özü, formun bir dizi eşitliğinin elde edildiği, kalanla bölmeyi tutarlı bir şekilde gerçekleştirmektir:

bir = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Bölümü ne zaman bitirebiliriz? rk + 1 = 0, burada r k = ebob (a , b).

örnek 1

64 Ve 48 .

Çözüm

Gösterimi tanıtalım: a = 64 , b = 48 .

Öklid algoritmasına dayanarak, bölümü gerçekleştireceğiz 64 Açık 48 .

1 alırız ve kalan 16 . q 1 = 1, r 1 = 16 olduğu ortaya çıktı.

İkinci adım bölmek 48 16'ya kadar 3 alırız. Yani q2 = 3, A r2 = 0 . Böylece, 16 sayısı, koşuldaki sayıların en büyük ortak bölenidir.

Cevap: gcd(64, 48) = 16.

Örnek 2

Sayıların GCD'si nedir? 111 Ve 432 ?

Çözüm

Bölmek 432 Açık 111 . Öklid'in algoritmasına göre, eşitlik zincirini elde ederiz 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 .

Böylece, sayıların en büyük ortak böleni 111 Ve 432 3 .

Cevap: gcd(111, 432) = 3.

Örnek 3

661 ve 113'ün en büyük ortak bölenini bulun.

Çözüm

Sayıları sırayla böleceğiz ve GCD'yi alacağız (661 , 113) = 1 . Bu, 661 ve 113'ün nispeten asal sayılar olduğu anlamına gelir. Asal sayılar tablosuna bakarsak, hesaplamalara başlamadan önce bunu anlayabiliriz.

Cevap: gcd(661, 113) = 1.

Sayıları Asal Faktörlere Ayırarak GCD'yi Bulma

Çarpanlara ayırma yöntemiyle iki sayının en büyük ortak bölenini bulmak için bu iki sayının ayrıştırılmasıyla elde edilen ve ortak olan tüm asal çarpanları çarpmak gerekir.

Örnek 4

220 ve 600 sayılarını asal çarpanlarına ayırırsak iki ürün elde ederiz: 220 = 2 2 5 11 Ve 600 = 2 2 2 3 5 5. Bu iki ürünün ortak bölenleri 2, 2 ve 5 olacaktır. Bu NOD anlamına gelir (220, 600) = 2 2 5 = 20.

Örnek 5

Sayıların en büyük ortak bölenini bulun 72 Ve 96 .

Çözüm

Sayıların tüm asal çarpanlarını bulun 72 Ve 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

İki sayı için ortak asal çarpanlar: 2 , 2 , 2 ve 3 . Bu NOD anlamına gelir (72, 96) = 2 2 2 3 = 24.

Cevap: gcd(72, 96) = 24.

İki sayının en büyük ortak bölenini bulma kuralı, en büyük ortak bölenin özelliklerine dayanır. .

Üç veya daha fazla sayının GCD'sini bulma

OBEB'i bulmamız gereken sayıların sayısından bağımsız olarak, art arda iki sayının OBEB'ini bulmaya dayanan aynı algoritmayı izleyeceğiz. Bu algoritma, aşağıdaki teoremin uygulanmasına dayanmaktadır: Birkaç sayının OBEB'i bir 1 , bir 2 , … , bir k sayıya eşittir dk gcd'nin sıralı hesaplamasında bulunan (bir 1 , bir 2) = d 2 OBEB (d 2 , a 3) = d 3 , OBEB (d 3 , a 4) = d 4 , … , OBEB (d k - 1 , a k) = d k .

Örnek 6

Dört sayının en büyük ortak bölenini bulun 78 , 294 , 570 ve 36 .

Çözüm

Gösterimi tanıtalım: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

78 ve 294 sayılarının OBEB'ini bularak başlayalım: d2= GCD (78 , 294) = 6 .

Şimdi d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) bulmaya başlayalım. Öklid algoritmasına göre 570 = 6 95 . Bu demektir g3 = GCD (6 , 570) = 6 .

Bul d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) . 36 6 ile kalansız bölünebilir. Bu, almamızı sağlar d4= GCD (6 , 36) = 6 .

d4 = 6, yani GCD (78 , 294 , 570 , 36) = 6 .

Cevap:

Şimdi bu ve daha fazla sayı için GCD'yi hesaplamanın başka bir yoluna bakalım. Sayıların tüm ortak asal çarpanlarını çarparak gcd'yi bulabiliriz.

Örnek 7

78 , 294 , 570 sayılarının gcd'sini hesaplayın ve 36 .

Çözüm

Bu sayıları asal çarpanlara ayıralım: 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .

Dört sayının tümü için ortak asal çarpanlar 2 ve 3 sayıları olacaktır.

Görünüşe göre NOD (78, 294, 570, 36) = 2 3 = 6.

Cevap: gcd(78 , 294 , 570 , 36) = 6 .

Negatif sayıların gcd'sini bulma

Negatif sayılarla uğraşmak zorunda kalırsak, en büyük ortak böleni bulmak için bu sayıların modüllerini kullanabiliriz. Bunu zıt işaretli sayıların özelliğini bilerek yapabiliriz: sayılar N Ve -N aynı bölenlere sahiptir.

Örnek 8

Negatif tam sayıların gcd'sini bulun − 231 Ve − 140 .

Çözüm

Hesaplamalar yapmak için koşulda verilen sayıların modüllerini alalım. Bunlar 231 ve 140 sayıları olacaktır. Kısaca anlatalım: GCD (− 231 , − 140) = OBEB (231 , 140) . Şimdi iki sayının asal çarpanlarını bulmak için Öklid algoritmasını uygulayalım: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 ve 42 = 7 6. Bu gcd'yi (231, 140) = 7 olarak elde ederiz. .

Ve NOD'dan beri (− 231 , − 140) = GCD (231 , 140) , ardından sayıların gcd'si − 231 Ve − 140 eşittir 7 .

Cevap: gcd (- 231 , - 140) = 7 .

Örnek 9

Üç sayının gcd'sini belirleyin - 585, 81 ve − 189 .

Çözüm

Yukarıdaki listedeki negatif sayıları mutlak değerleri ile değiştirelim, OBEB elde ederiz. (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Sonra verilen tüm sayıları asal çarpanlara ayırırız: 585 = 3 3 5 13, 81 = 3 3 3 3 ve 189 = 3 3 3 7. 3 ve 3 asal çarpanları üç sayıda ortaktır. Görünüşe göre ebob (585 , 81 , 189) = ebob (- 585 , 81 , - 189) = 9 .

Cevap: OBEB (- 585 , 81 , - 189) = 9 .

Metinde bir hata fark ederseniz, lütfen onu vurgulayın ve Ctrl+Enter tuşlarına basın.

Öklid'in algoritması

En büyük ortak böleni

Aşağıdaki problemi ele alalım: iki doğal sayının en büyük ortak bölenini (OBEB) belirlemek için bir program yazmak gerekiyor.

Matematiği hatırlayalım. İki doğal sayının en büyük ortak böleni, eşit olarak bölünebildikleri en büyük doğal sayıdır. Örneğin 12 ve 18 sayılarının ortak bölenleri vardır: 2, 3, 6. En büyük ortak bölen 6'dır. Bu şöyle yazılır:

gcd(12, 18) = 6.

İlk verileri M u N olarak belirtin. Problem ifadesi aşağıdaki gibidir:
verilen: M, K
Bulmak: OBEB(M, N).

Bu durumda, ek matematiksel biçimlendirme gerekmez. Problemin ifadesinin kendisi formal bir matematiksel niteliktedir. M ve N değerlerinden OBEB(M, N) hesaplamak için bir formül yoktur. Ancak öte yandan, oldukça uzun zaman önce, bilgisayarların ortaya çıkmasından çok önce, bu sorunu çözmek için algoritmik bir yöntem biliniyordu. . denir Öklid'in algoritması .

Öklid'in algoritması fikri

Bu algoritmanın fikri, eğer M>N ise, o zaman

OBEB(M, N) = OBEB(M - N, N).

Başka bir deyişle, iki doğal sayının gcd'si, pozitif farklarının (farklarının modülü) ve küçük sayının gcd'sine eşittir.

Bu özelliği kanıtlamak kolaydır. K bir ortak bölen M uN olsun (M > N). Bu, M \u003d mK, N \u003d nK olduğu anlamına gelir; burada m, n doğal sayılardır ve m > n. O zaman M - N \u003d K (m - n), bu, K'nin M - N sayısının bir böleni olduğu anlamına gelir. Bu nedenle, M ve N sayılarının tüm ortak bölenleri, en büyükleri de dahil olmak üzere M - N farklarının bölenleridir. ortak bölen

İkinci bariz özellik:

OBEB(M, M) = M.

"Manuel" sayma için Öklid'in algoritması şöyle görünür:

1) sayılar eşitse, herhangi birini cevap olarak alın, aksi takdirde algoritmaya devam edin;

2) büyük sayıyı, sayıların büyüğü ve küçüğü arasındaki farkla değiştirin;

3) 1. paragrafın uygulanmasına geri dönün.

Bu algoritmayı M=32, N=24 örneğinde düşünün:

Algoritmanın yapısı, iç içe dallanma içeren bir while döngüsüdür. Döngü, M ve N değerleri birbirine eşit olana kadar tekrar eder. Dallanmada, iki değerden büyük olanı, farkları ile değiştirilir.

Şimdi M = 32, N = 24 başlangıç ​​​​değerleri için algoritmanın izleme tablosuna bakın.

Adım	Operasyon	M	N	Durum
1	M girişi	32
2	N girişi		24
3	M ¹ K			32 ¹ 24, evet
4	M>N			32>24, evet
5	M:=M-N	8
6	M ¹ K			8 ¹ 24, evet
7	M>N			8>24, hayır
8	N:=N-M		16
9	M ¹ K			8 ¹ 16, evet
10	M>N			8>16, hayır
11	N:=N-M		8
12	M ¹ K			8 ¹ 8, hayır
13	terminal M	8
14	son

Nihai sonuç doğru olandır.

A'dan Z'ye ve Pascal'da program

Algoritmayı AI'da ve programı Pascal'da yazıyoruz.

Sorular ve görevler

1. Bilgisayarınızda Evklid programını çalıştırın. M=32, N=24 üzerinde test edin; M = 696, N = 234.

2. Aşağıdaki formülü kullanarak üç sayının en büyük ortak bölenini bulan bir program yazın:

ebob(A, B, C) = ebob(OBEB(A, B), C).

3. Aşağıdaki formülü kullanarak iki sayının en küçük ortak katını (EKOK) bulan bir program yazın:

A × B = OBEB(A, B) × EKOK(A, B).