Öklid algoritmasını kullanarak düğümleri bulma ve asal çarpanlara ayırma. Sayıları asal faktörlere ayırarak nok bulma Öklid'in gcd bulma algoritması

En büyük ortak böleni bulmanın iki yolunu düşünün.

Faktoring Yoluyla Bulmak

Birinci yol, verilen sayıların en büyük ortak böleni bulmaktır. asal faktörler.

Birkaç sayının GCD'sini bulmak için, onları asal çarpanlara ayırmak ve verilen tüm sayılarda ortak olanları kendi aralarında çarpmak yeterlidir.

örnek 1 OBEB'i (84, 90) bulalım.

84 ve 90 sayılarını asal çarpanlarına ayırıyoruz:

Böylece, tüm ortak asal faktörlerin altını çizdik, onları kendi aralarında çarpmak kalıyor: 1 2 3 = 6.

Yani gcd(84, 90) = 6.

Örnek 2 OBEB'yi (15, 28) bulalım.

15 ve 28'i asal çarpanlarına ayırıyoruz:

15 ve 28 sayıları en büyük ortak bölenleri bir olduğu için aralarında asaldır.

gcd (15, 28) = 1.

Öklid'in algoritması

İkinci yöntem (Öklid yöntemi olarak da adlandırılır), ardışık bölme yoluyla OAB'yi bulmaktır.

İlk olarak, bu yöntemi sadece verilen iki sayıya uygulanmış olarak inceleyeceğiz ve ardından onu üç veya daha fazla sayıya nasıl uygulayacağımızı bulacağız.

Verilen iki sayıdan büyük olanı küçüğüne bölünebiliyorsa, küçük olan sayı onların en büyük ortak böleni olacaktır.

örnek 1 27 ve 9 olmak üzere iki sayı alın. 27, 9'a ve 9 da 9'a bölünebildiğine göre, 9, 27 ve 9 sayılarının ortak bölenidir. Bu nedenle, gcd (27, 9) = 9.

Diğer durumlarda, iki sayının en büyük ortak bölenini bulmak için kullanılır. sıradaki sipariş hareketler:

1. Verilen iki sayıdan büyük olan sayı küçük olana bölünür.
2. Daha sonra, küçük sayı, bölme işleminden elde edilen kalana bölünür. daha fazla daha ucuza.
3. Ayrıca, ilk kalan, daha küçük sayının birinci kalana bölünmesiyle elde edilen ikinci kalana bölünür.
4. İkinci kalan üçüncüye bölünür, bu da birinci kalanı ikinciye bölerek elde edilir ve bu böyle devam eder.
5. Böylece kalan sıfır olana kadar bölme işlemi devam eder. Son bölen en büyük ortak bölen olacaktır.

Örnek 2 140 ve 96 sayılarının en büyük ortak bölenini bulalım:

1) 140: 96 = 1 (kalan 44)

2) 96: 44 = 2 (kalan 8)

3) 44: 8 = 5 (kalan 4)

Son bölen 4'tür, yani gcd(140, 96) = 4'tür.

Sıralı bölme ayrıca bir sütuna da yazılabilir:

Verilen üç veya daha fazla sayının en büyük ortak bölenini bulmak için aşağıdaki prosedürü kullanın:

1. İlk olarak, birden çok veri kümesinden herhangi iki sayının en büyük ortak bölenini bulun.
2. Sonra bulunan bölenin OBEB'ini ve verilen üçüncü bir sayıyı buluruz.
3. Sonra en son bulunan bölenin OBEB'ini ve verilen dördüncü sayıyı buluruz, vb.

Örnek 3 140, 96 ve 48 sayılarının en büyük ortak bölenini bulalım. Önceki örnekte 140 ve 96 sayılarının EBOB'unu bulduk (bu 4 sayısı). Geriye 4 sayısının ve verilen üçüncü sayının en büyük ortak bölenini bulmak kalıyor - 48:

48 sayısı 4'e kalansız bölünür. Yani gcd(140, 96, 48) = 4.

Bir sayıyı asal sayıların çarpımı olarak göstermeye denir bu sayıyı asal çarpanlarına ayırıyoruz.

Örneğin, 110 = 2 5 11 girişi, 110 sayısının 2, 5 ve 11 asal çarpanlarına ayrıldığını gösterir.

Genel olarak, her şey asal faktörlere ayrılabilir. bileşik sayı ayrıca, faktörlerin sırası dikkate alınmazsa, herhangi bir yöntemle bir ve aynı ayrıştırma elde edilir. Bu nedenle, 110 sayısının 2 · 5 · 11'in veya 5 · 2 · 11'in çarpımı olarak gösterimleri, özünde, 110 sayısının asal çarpanlara ayrılmasıyla aynıdır.

Sayıları 2, 3, 5 vb. ile bölme işaretlerini kullanarak asal çarpanlara ayırırken, bir sayının asal çarpanlara ayrıştırılmasını nasıl yazacağımızı hatırlayalım. Örneğin 720 sayısını asal çarpanlarına ayıralım 720 sayısı 2'ye bölünür. Dolayısıyla 2, 720 sayısının ayrıştırılmasında asal çarpanlardan biridir. 720'yi 2'ye bölün. eşittir işaretinin sağında ve 360 ​​bölümü 720 sayısının altına yazılır. 360 sayısının 2'ye bölünmesi, 180'i elde ederiz. 180'i 2'ye böleriz, 90'ı buluruz, 90'ı 2'ye böleriz, 45'i buluruz, 45'i böleriz 3, 15 elde ederiz, 15'i 3'e böleriz, 5 elde ederiz. 5 asaldır, 5'e bölündüğünde 1 elde ederiz. Çarpanlara ayırma tamamlanır.

720 = 2 2 2 2 3 3 5

Özdeş faktörlerin çarpımını bir güçle değiştirmek gelenekseldir: 720 = 5. 720 sayısının böyle bir temsiline denir. kanonik görünüm bu numara.

Bir sayıyı asal çarpanlara ayırmak, bunların en büyük ortak bölenini ve en küçük ortak katını bulmak için kullanılır.

Örneğin, 3600 ve 288 sayılarının en büyük ortak bölenini ve en küçük ortak katını bulun.

Bu sayıların her birini temsil edelim kanonik biçim.

3600 = 2 2 2 2 3 3 5 5 = ; 288 = 2 2 2 2 2 3 3 =

3600 ve 288 sayılarının en büyük ortak böleninin asal çarpanlarına ayırma işleminde, tüm ortak basit çarpma, verilen sayıların açılımlarında yer alan ve her biri en düşük gösterge bununla her iki genişlemeye de girer. Bu nedenle, 3600 ve 288 sayılarının en büyük ortak böleninin açılımı çarpanları ve . O halde D (3600? 288) = · = 144.

3600 ve 288'in en küçük ortak katının asal çarpanlarına ayrılması, içerdiği tüm asal çarpanları içermelidir. en az birinde 3600 ve 288 sayılarının açılımlarından ve her biri alınmalıdır en yüksek puana sahip, bu sayıların her iki açılımına da dahildir. Bu nedenle, 3600 ve 288'in en küçük ortak katının açılımı, , , 5 çarpanlarını içerecektir.

K (3600, 288) = 5 = 7200.

Genel olarak, verilen sayıların en büyük ortak bölenini bulmak için:

2) Verilen tüm sayılarda ortak olan asal çarpanların bir çarpımını oluşturuyoruz ve bunların her biri, bu sayıların tüm açılımlarına girdiği en küçük üsle alınır;

3) Bu ürünün değerini buluruz - bu sayıların en büyük ortak böleni olacaktır.

Verilen sayıların en küçük ortak katını bulmak için:

1) Verilen her bir sayıyı kanonik biçimde temsil ediyoruz;

2) Bu sayıların açılımlarında bulunan tüm asal çarpanlardan bir çarpım oluşturuyoruz ve her biri bu sayıların açılımlarına girdiği en büyük üs ile alınır;

3) Bu ürünün değerini buluyoruz - bu sayıların en küçük ortak katı olacak.

Bilet numarası 45. Sayıların en küçük ortak katı. Özellikleri ve bulma yöntemleri. Örnekler.

gcd(en küçük ortak bölen) ile en küçük ortak katın (LCM) hesaplanması

En az ortak katı bulmanın bir yolu, LCM ve GCD arasındaki ilişkiye dayanmaktadır. LCM ve GCD arasındaki mevcut ilişki, bilinen en büyük ortak bölen aracılığıyla iki pozitif tamsayının en küçük ortak katını hesaplamanıza olanak tanır. Karşılık gelen formül forma sahiptir LCM(a, b)=a b: GCM(a, b) . Yukarıdaki formüle göre LCM bulma örneklerini düşünün.

Örnek.

İki sayının en küçük ortak katını bulun 126 ve 70 .

Çözüm.

Bu örnekte a=126, b=70. LCM ve GCD arasındaki formülle ifade edilen ilişkiyi kullanalım. LCM(a, b)=a b: GCM(a, b). Yani, önce sayıların en büyük ortak bölenini bulmalıyız. 70 ve 126 , bundan sonra bu sayıların LCM'sini yazılı formüle göre hesaplayabiliriz.

Bulalım OBEB(126, 70), Öklid algoritmasını kullanarak: 126=70 1+56, 70=56 1+14, 56=14 4, Sonuç olarak, gcd(126, 70)=14.

Şimdi gerekli en küçük ortak katı buluyoruz: LCM(126, 70)=126 70: GCM(126, 70)=126 70:14=630.

Cevap:

LCM(126, 70)=630.

Örnek.

neye eşittir MOK(68, 34)?

Çözüm.

Çünkü 68 tamamen bölünmüş 34 , sonra OBEB(68, 34)=34. Şimdi en küçük ortak katı hesaplıyoruz: LCM(68, 34)=68 34:GCM(68, 34)=68 34:34=68.

Cevap:

LCM(68, 34)=68.

Önceki örneğin, pozitif tamsayılar için LCM'yi bulmak için aşağıdaki kurala uyduğunu unutmayın. a ve b: eğer sayı a bölü b, o zaman bu sayıların en küçük ortak katı a.

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

En küçük ortak katı bulmanın başka bir yolu da sayıları asal çarpanlara ayırmaktır. Bu sayıların tüm asal çarpanlarının çarpımını yaparsak, daha sonra bu sayıların açılımlarında bulunan tüm ortak asal çarpanları bu çarpımdan çıkarırsak, sonuç bu sayıların en küçük ortak katına eşit olacaktır.

LCM'yi bulmak için ilan edilen kural eşitlikten kaynaklanmaktadır. LCM(a, b)=a b: GCM(a, b). Nitekim sayıların çarpımı a ve b sayıların açılımlarında yer alan tüm faktörlerin ürününe eşittir a ve b. Sırasıyla gcd(a, b) sayıların açılımlarında aynı anda bulunan tüm asal faktörlerin ürününe eşittir a ve b(sayıları asal çarpanlara ayırarak GCD bulma bölümünde açıklanmıştır).

Bir örnek alalım. bize bildirin 75=3 5 5 ve 210=2 3 5 7. Bu açılımların tüm faktörlerinin ürününü oluşturun: 2 3 3 5 5 5 7. Şimdi, sayının genişlemesinde de mevcut olan tüm faktörleri bu üründen hariç tutuyoruz. 75 ve sayının genişlemesinde 210 (bu tür faktörler 3 ve 5 ), daha sonra ürün şeklini alacaktır 2 3 5 5 7. Bu ürünün değeri sayıların en küçük ortak katına eşittir. 75 ve 210 , yani, LCM(75, 210)= 2 3 5 5 7=1 050.

Örnek.

Sayıları genişletmek 441 ve 700 asal çarpanlarına ayırarak bu sayıların en küçük ortak katını bulunuz.

Çözüm.

sayıları ayrıştıralım 441 ve 700 asal faktörler için:

alırız 441=3 3 7 7 ve 700=2 2 5 5 7.

Şimdi bu sayıların açılımlarında yer alan tüm faktörlerin bir çarpımını yapalım: 2 2 3 3 5 5 7 7 7. Her iki genişlemede de aynı anda mevcut olan tüm faktörleri bu üründen hariç tutalım (böyle bir faktör var - bu sayı 7 ): 2 2 3 3 5 5 7 7. Böylece, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.

Cevap:

LCM(441, 700)= 44 100.

Sayıların asal faktörlere ayrıştırılmasını kullanarak LCM'yi bulma kuralı biraz farklı formüle edilebilir. Sayının genişlemesinden faktörlere ise a sayının genişlemesinden eksik faktörleri ekleyin b, o zaman elde edilen ürünün değeri sayıların en küçük ortak katına eşit olacaktır. a ve b .

Örneğin, aynı sayıları alalım 75 ve 210 , çarpanlarına ayırmaları aşağıdaki gibidir: 75=3 5 5 ve 210=2 3 5 7. çarpanlara 3 , 5 ve 5 sayının ayrıştırılmasından 75 2 ve 7 sayının ayrıştırılmasından 210 , ürünü alıyoruz 2 3 5 5 7, kimin değeri NOC(75, 210).

Örnek.

Sayıların en küçük ortak katını bulun 84 ve 648 .

Çözüm.

İlk önce sayıların ayrıştırılmasını elde ederiz. 84 ve 648 asal faktörlere. benziyorlar 84=2 2 3 7 ve 648=2 2 2 3 3 3 3. çarpanlara 2 , 2 , 3 ve 7 sayının ayrıştırılmasından 84 eksik faktörlerin eklenmesi 2 , 3 , 3 ve 3 sayının ayrıştırılmasından 648 , ürünü alıyoruz 2 2 2 3 3 3 3 7, şuna eşit 4 536 . Böylece, sayıların istenen en küçük ortak katı 84 ve 648 eşittir 4 536 .

Cevap:

LCM(84, 648)=4536.

İki ana yolla GCD'yi bulmak için iki ana yöntem düşünün: Öklid algoritmasını kullanarak ve çarpanlara ayırarak. İki, üç ve daha fazla sayı için her iki yöntemi de uygulayalım.

Yandex.RTB R-A-339285-1

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

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

Algoritmanın özü, formun bir dizi eşitliğinin elde edildiği bir kalanla sürekli olarak bölme yapmaktır:

a = 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 = gcd (a , b).

örnek 1

64 ve 48 .

Çözüm

Şu gösterimi tanıtalım: a = 64 , b = 48 .

Öklid algoritmasına dayanarak, bölme işlemini gerçekleştireceğiz. 64 üzerinde 48 .

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

İkinci adım bölmek 48 16 ile 3 elde ederiz. Yani q2 = 3, a r2 = 0 . Böylece, 16 sayısı, koşuldan gelen 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 üzerinde 111 . Euclid'in algoritmasına göre, 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 eşitlikler zincirini elde ederiz.

Buna göre sayıların en büyük ortak böleni 111 ve 432 3'tür.

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 OBEB'i Bulma

İki sayının en büyük ortak bölenini çarpanlara ayırarak bulmak için, bu iki sayının ayrıştırılmasıyla elde edilen ve aralarında ortak olan tüm asal çarpanları çarpmak gerekir.

Örnek 4

220 ve 600 sayılarını asal çarpanlarına ayırırsak iki sonuç elde ederiz: 220 = 2 2 5 11 ve 600 = 2 2 2 3 5 5. Bu iki ürünün ortak çarpanları 2, 2 ve 5 olacaktır. Bu, NOD'un (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ının ortak asal çarpanları: 2 , 2 , 2 ve 3 . Bu, NOD'un (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ı, gcd (m a 1 , m b 1) = m gcd (a 1 , b 1) olan en büyük ortak bölenin özelliklerine dayanır, burada m herhangi bir pozitif tam sayıdır. .

Üç veya daha fazla sayıdan oluşan GCD'yi bulma

GCD'yi bulmamız gereken sayıların sayısından bağımsız olarak, art arda iki sayının GCD'sini bulmaktan oluşan aynı algoritmaya göre hareket edeceğiz. Bu algoritma, aşağıdaki teoremin uygulanmasına dayanmaktadır: Birkaç sayının GCD'si bir 1 , bir 2 , … , bir k sayıya eşittir dk gcd'nin sıralı hesaplanmasında bulunan (a 1 , a 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

78, 294, 570 ve 78 sayılarının en büyük ortak bölenini bulunuz. 36 .

Çözüm

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

78 ve 294 sayılarının GCD'sini 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 . Demek oluyor d3 = GCD (6 , 570) = 6 .

d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) bulun. 36 6 ile kalansız bölünür. 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 OBEB'i 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 çarpanlarına 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.

NOD olduğu ortaya çıktı (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 koyalım: GCD (− 231 , − 140) = GCD (231, 140) . Şimdi iki sayının asal çarpanlarını bulmak için Öklid'in 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 (231, 140) = 7'yi elde ederiz. .

Ve NOD'dan beri (− 231 , − 140) = GCD (231 , 140) , sonra 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ı onların yerine yazalım. mutlak değerler, GCD alıyoruz (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Sonra verilen tüm sayıları asal çarpanlarına 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ı için ortaktır. gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 olduğu ortaya çıktı.

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

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