მაგრამ ბევრი ნატურალური რიცხვი თანაბრად იყოფა სხვა ნატურალურ რიცხვებზე.

Მაგალითად:

რიცხვი 12 იყოფა 1-ზე, 2-ზე, 3-ზე, 4-ზე, 6-ზე, 12-ზე;

რიცხვი 36 იყოფა 1-ზე, 2-ზე, 3-ზე, 4-ზე, 6-ზე, 12-ზე, 18-ზე, 36-ზე.

რიცხვებს, რომლებზეც რიცხვი იყოფა (12-ისთვის ეს არის 1, 2, 3, 4, 6 და 12) ეწოდება რიცხვების გამყოფები. ნატურალური რიცხვის გამყოფი აარის ნატურალური რიცხვი, რომელიც ყოფს მოცემულ რიცხვს აუკვალოდ. ნატურალურ რიცხვს, რომელსაც აქვს ორზე მეტი ფაქტორი, ეწოდება კომპოზიტური. გაითვალისწინეთ, რომ 12 და 36 რიცხვებს აქვთ საერთო გამყოფები. ეს არის რიცხვები: 1, 2, 3, 4, 6, 12. ამ რიცხვების უდიდესი გამყოფი არის 12.

ორი მოცემული რიცხვის საერთო გამყოფი ადა ბარის რიცხვი, რომლითაც ორივე მოცემული რიცხვი იყოფა ნაშთების გარეშე ადა ბ. მრავალრიცხოვანი რიცხვების საერთო გამყოფი (GCD)არის რიცხვი, რომელიც ემსახურება თითოეული მათგანის გამყოფს.

მოკლედ რიცხვების უდიდესი საერთო გამყოფი ადა ბიწერება ასე:

მაგალითი: gcd (12; 36) = 12.

ამოხსნის ჩანაწერში რიცხვების გამყოფები აღინიშნება დიდი ასო "D"-ით.

მაგალითი:

gcd (7; 9) = 1

7 და 9 რიცხვებს აქვთ მხოლოდ ერთი საერთო გამყოფი - რიცხვი 1. ასეთ რიცხვებს უწოდებენ კოპრაიმიჩი სლემი.

კოპრიმი რიცხვებიარის ნატურალური რიცხვები, რომლებსაც აქვთ მხოლოდ ერთი საერთო გამყოფი - რიცხვი 1. მათი gcd არის 1.

უდიდესი საერთო გამყოფი (GCD), თვისებები.

• მთავარი თვისება: უდიდესი საერთო გამყოფი მდა ნიყოფა ამ რიცხვების ნებისმიერ საერთო გამყოფზე. მაგალითი: 12 და 18 რიცხვებისთვის ყველაზე დიდი საერთო გამყოფი არის 6; ის იყოფა ამ რიცხვების ყველა საერთო გამყოფზე: 1, 2, 3, 6.
• დასკვნა 1: საერთო გამყოფთა ნაკრები მდა ნემთხვევა გამყოფების სიმრავლეს gcd( მ, ნ).
• დასკვნა 2: საერთო ჯერადების ნაკრები მდა ნემთხვევა მრავალი LCM-ის სიმრავლეს ( მ, ნ).

ეს ნიშნავს, კერძოდ, რომ წილადის შეუქცევად ფორმამდე დასაყვანად აუცილებელია მისი მრიცხველი და მნიშვნელი გავყოთ მათ gcd-ზე.

• რიცხვების უდიდესი საერთო გამყოფი მდა ნშეიძლება განისაზღვროს, როგორც მათი ყველა წრფივი კომბინაციის სიმრავლის უმცირესი დადებითი ელემენტი:

და შესაბამისად წარმოადგენენ რიცხვთა წრფივ კომბინაციას მდა ნ:

ეს თანაფარდობა ე.წ ბეზუტის თანაფარდობადა კოეფიციენტები uდა ვ — ბეზუტის კოეფიციენტები. ბეზუტის კოეფიციენტები ეფექტურად გამოითვლება გაფართოებული ევკლიდის ალგორითმით. ეს განცხადება განზოგადებულია ნატურალური რიცხვების სიმრავლეებზე - მისი მნიშვნელობა ისაა, რომ სიმრავლის მიერ გენერირებული ჯგუფის ქვეჯგუფი არის ციკლური და წარმოიქმნება ერთი ელემენტით: gcd ( ა 1 , ა 2 , … , a n).

უდიდესი საერთო გამყოფის (gcd) გამოთვლა.

ორი რიცხვის gcd-ის გამოთვლის ეფექტური გზებია ევკლიდეს ალგორითმიდა ორობითიალგორითმი. გარდა ამისა, GCD მნიშვნელობა ( მ,ნ) ადვილად გამოითვლება, თუ ცნობილია რიცხვების კანონიკური გაფართოება მდა ნძირითადი ფაქტორებისთვის:

სადაც არის განსხვავებული მარტივი და და არის არაუარყოფითი მთელი რიცხვები (ისინი შეიძლება იყოს ნული, თუ შესაბამისი მარტივი არ არის დაშლაში). შემდეგ gcd ( მ,ნ) და LCM ( მ,ნ) გამოიხატება ფორმულებით:

თუ ორზე მეტი რიცხვია: , მათი GCD გვხვდება შემდეგი ალგორითმის მიხედვით:

- ეს არის სასურველი GCD.

ასევე, რათა იპოვოთ ყველაზე დიდი საერთო გამყოფი, შეგიძლიათ დაშალოთ თითოეული მოცემული რიცხვი მარტივ ფაქტორებად. შემდეგ ცალკე ჩამოწერეთ მხოლოდ ის ფაქტორები, რომლებიც შედის ყველა მოცემულ რიცხვში. შემდეგ ვამრავლებთ ერთმანეთში ჩაწერილ რიცხვებს - გამრავლების შედეგი არის უდიდესი საერთო გამყოფი .

მოდით გავაანალიზოთ უდიდესი საერთო გამყოფის გამოთვლა ეტაპობრივად:

1. დაშალე რიცხვების გამყოფები მარტივ ფაქტორებად:

გამოთვლები მოხერხებულად იწერება ვერტიკალური ზოლის გამოყენებით. ხაზის მარცხნივ ჯერ ჩაწერეთ დივიდენდი, მარჯვნივ - გამყოფი. შემდგომ მარცხენა სვეტში ჩვენ ვწერთ კერძოს მნიშვნელობებს. მოდი მაშინვე ავხსნათ მაგალითით. მოდით გავამრავლოთ 28 და 64 რიცხვები მარტივ ფაქტორებად.

2. ორივე რიცხვში ხაზს ვუსვამთ ერთსა და იმავე მარტივ ფაქტორებს:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. ვპოულობთ იდენტური მარტივი ფაქტორების ნამრავლს და ვწერთ პასუხს:

GCD (28; 64) = 2. 2 = 4

პასუხი: GCD (28; 64) = 4

თქვენ შეგიძლიათ მოაწყოთ GCD-ის მდებარეობა ორი გზით: სვეტში (როგორც ეს გაკეთდა ზემოთ) ან "ხაზში".

GCD ჩაწერის პირველი გზა:

იპოვეთ GCD 48 და 36.

GCD (48; 36) = 2. 2. 3 = 12

GCD ჩაწერის მეორე გზა:

ახლა მოდით დავწეროთ GCD საძიებო გადაწყვეტა ხაზში. იპოვეთ GCD 10 და 15.

D(10) = (1, 2, 5, 10)

D(15) = (1, 3, 5, 15)

D(10, 15) = (1, 5)

მოვაგვაროთ პრობლემა. ჩვენ გვაქვს ორი სახის ქუქი-ფაილები. ზოგი შოკოლადიანია, ზოგიც უბრალო. არის 48 შოკოლადის ნაჭერი, ხოლო მარტივი 36. ამ ნამცხვრებიდან აუცილებელია საჩუქრების მაქსიმალური რაოდენობა და ყველა მათგანი უნდა იქნას გამოყენებული.

ჯერ ჩამოვწეროთ ამ ორი რიცხვიდან თითოეულის ყველა გამყოფი, რადგან ორივე ეს რიცხვი უნდა იყოფა საჩუქრების რაოდენობაზე.

ვიღებთ

• 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
• 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

გამყოფებს შორის ვიპოვოთ საერთო, რაც აქვს როგორც პირველს, ასევე მეორე რიცხვს.

საერთო გამყოფები იქნება: 1, 2, 3, 4, 6, 12.

ყველაზე დიდი საერთო გამყოფი არის 12. ამ რიცხვს 36-ისა და 48-ის უდიდესი საერთო გამყოფი ეწოდება.

შედეგიდან გამომდინარე, შეგვიძლია დავასკვნათ, რომ 12 საჩუქრის დამზადება შესაძლებელია ყველა ქუქიიდან. ერთი ასეთი საჩუქარი შეიცავს 4 შოკოლადის ნამცხვარს და 3 ჩვეულებრივ ფუნთუშას.

ყველაზე დიდი საერთო გამყოფის პოვნა

• უდიდეს ნატურალურ რიცხვს, რომლითაც ორი რიცხვი a და b იყოფა ნაშთების გარეშე, ამ რიცხვების უდიდესი საერთო გამყოფი ეწოდება.

ზოგჯერ აბრევიატურა GCD გამოიყენება ჩანაწერის შემოკლებისთვის.

რიცხვების ზოგიერთ წყვილს აქვს ერთი ყველაზე დიდი საერთო გამყოფი. ასეთ ნომრებს ეძახიან თანაპრიმა რიცხვები.მაგალითად, რიცხვები 24 და 35. აქვს GCD =1.

როგორ მოვძებნოთ ყველაზე დიდი საერთო გამყოფი

იმისთვის, რომ ვიპოვოთ უდიდესი საერთო გამყოფი, არ არის საჭირო ამ რიცხვების ყველა გამყოფის ამოწერა.

სხვაგვარად შეგიძლია. პირველ რიგში, დააკავშირეთ ორივე რიცხვი პირველ ფაქტორებად.

• 48 = 2*2*2*2*3,
• 36 = 2*2*3*3.

ახლა, იმ ფაქტორებიდან, რომლებიც შედის პირველი რიცხვის გაფართოებაში, ჩვენ ვშლით ყველა იმ ფაქტორს, რომელიც არ შედის მეორე ნომრის გაფართოებაში. ჩვენს შემთხვევაში, ეს არის ორი დუქცია.

• 48 = 2*2*2*2*3 ,
• 36 = 2*2*3 *3.

რჩება ფაქტორები 2, 2 და 3. მათი ნამრავლია 12. ეს რიცხვი იქნება 48 და 36 რიცხვების უდიდესი საერთო გამყოფი.

ეს წესი შეიძლება გავრცელდეს სამი, ოთხი და ა.შ. ნომრები.

ყველაზე დიდი საერთო გამყოფის პოვნის ზოგადი სქემა

• 1. რიცხვების დაშლა მარტივ ფაქტორებად.
• 2. ამ რიცხვებიდან ერთ-ერთის გაფართოებაში შემავალი ფაქტორებიდან გადახაზეთ ისინი, რომლებიც არ შედის სხვა რიცხვების გაფართოებაში.
• 3. გამოთვალეთ დარჩენილი ფაქტორების ნამრავლი.

ნატურალური რიცხვების უმცირესი საერთო ჯერადი (LCM) და უდიდესი საერთო გამყოფის (GCD) პოვნა.

	2						5
	2						5
	3						3
	5

60=2*2*3*5
75=3*5*5
2) ჩვენ ვწერთ ამ რიცხვებიდან პირველის გაფართოებაში შემავალ ფაქტორებს და ვუმატებთ მათ მეორე რიცხვის გაფართოების გამოტოვებულ ფაქტორს 5. ვიღებთ: 2*2*3*5*5=300. ნაპოვნია NOC, ე.ი. ეს ჯამი = 300. არ დაგავიწყდეთ განზომილება და დაწერეთ პასუხი:
პასუხი: დედა თითოეულს 300 მანეთს აძლევს.

GCD-ის განმარტება:უდიდესი საერთო გამყოფი (GCD)ნატურალური რიცხვები ადა inდაასახელეთ უდიდესი ნატურალური რიცხვი გ, რომელსაც და ა, და ბგაყოფილი ნარჩენების გარეშე. იმათ. გარის უმცირესი ნატურალური რიცხვი, რომლისთვისაც და ადა ბმრავლობითია.

შეხსენება:ნატურალური რიცხვების განსაზღვრის ორი მიდგომა არსებობს

• რიცხვები, რომლებიც გამოიყენება: პუნქტების (პირველი, მეორე, მესამე, ...) ჩამოთვლაში (ნუმერაციაში); - სკოლებში, ჩვეულებრივ.
• ნივთების რაოდენობის მითითებით (პოკემონის გარეშე - ნული, ერთი პოკემონი, ორი პოკემონი, ...).

უარყოფითი და არამთლიანი (რაციონალური, რეალური, ...) რიცხვები ბუნებრივი არ არის. ზოგიერთი ავტორი შეიცავს ნულს ნატურალური რიცხვების სიმრავლეში, ზოგი კი არა. ყველა ნატურალური რიცხვის სიმრავლე ჩვეულებრივ აღინიშნება სიმბოლოთი ნ

შეხსენება:ნატურალური რიცხვის გამყოფი ადარეკეთ ნომერზე ბ,რომელსაც აგაყოფილი ნარჩენების გარეშე. ნატურალური რიცხვის მრავლობითი ბნატურალურ რიცხვს უწოდებენ ა, რომელიც იყოფა ბუკვალოდ. თუ ნომერი ბ- რიცხვის გამყოფი ა, მაშინ ამრავალჯერადი ბ. მაგალითი: 2 არის 4-ის გამყოფი და 4 არის 2-ის ჯერადი. 3 არის 12-ის გამყოფი, ხოლო 12 არის 3-ის ჯერადი.
შეხსენება:ბუნებრივ რიცხვებს უბრალო ეწოდება, თუ ისინი იყოფა ნარჩენების გარეშე მხოლოდ საკუთარ თავზე და 1-ზე. თანაპირველი რიცხვებია, რომლებსაც აქვთ მხოლოდ ერთი საერთო გამყოფი 1-ის ტოლი.

განმარტება, თუ როგორ უნდა იპოვოთ GCD ზოგად შემთხვევაში:საპოვნელად GCD (ყველაზე დიდი საერთო გამყოფი)საჭიროა რამდენიმე ნატურალური რიცხვი:
1) დაშალეთ ისინი პირველ ფაქტორებად. (პირველი რიცხვების დიაგრამა შეიძლება ძალიან სასარგებლო იყოს ამისთვის.)
2) ჩამოწერეთ ერთი მათგანის გაფართოებაში შემავალი ფაქტორები.
3) წაშალეთ ის, რაც არ შედის დარჩენილი ნომრების გაფართოებაში.
4) გავამრავლოთ მე-3 პუნქტში მიღებული ფაქტორები).

დავალება 2 (NOK):ახალი წლისთვის კოლია პუზატოვმა ქალაქში 48 ზაზუნა და 36 ყავის ქვაბი იყიდა. ფეკლა დორმიდონტოვას, როგორც კლასში ყველაზე პატიოსან გოგონას, დაევალა ეს ქონება გაეყო მასწავლებლებისთვის სასაჩუქრე კომპლექტებში რაც შეიძლება მეტი. რა არის კომპლექტების რაოდენობა? როგორია კომპლექტების შემადგენლობა?

მაგალითი 2.1. გკდ-ის პოვნის პრობლემის გადაჭრა. GCD-ის მოძიება შერჩევით.
გამოსავალი:თითოეული რიცხვი 48 და 36 უნდა გაიყოს საჩუქრების რაოდენობაზე.
1) ჩაწერეთ გამყოფები 48: 48, 24, 16, 12 , 8, 6, 3, 2, 1
2) ჩაწერეთ გამყოფები 36: 36, 18, 12 , 9, 6, 3, 2, 1 აირჩიეთ უდიდესი საერთო გამყოფი. ოპ-ლა-ლა! ნაპოვნია, ეს არის 12 ცალი კომპლექტების რაოდენობა.
3) 48 გავყოთ 12-ზე, მივიღებთ 4-ს, ვყოფთ 36-ს 12-ზე, მივიღებთ 3. არ დაგავიწყდეთ განზომილება და დაწერეთ პასუხი:
პასუხი: თითოეულ კომპლექტში მიიღებთ 4 ზაზუნის 12 კომპლექტს და 3 ყავის ქვაბს.

ორი რიცხვის უმცირესი საერთო ჯერადი პირდაპირ კავშირშია ამ რიცხვების უდიდეს საერთო გამყოფთან. ეს კავშირი GCD-სა და NOC-ს შორისგანისაზღვრება შემდეგი თეორემით.

თეორემა.

ორი დადებითი მთელი რიცხვის უმცირესი საერთო ჯერადი a და b უდრის a და b რიცხვების ნამრავლს გაყოფილი a და b რიცხვების უდიდეს საერთო გამყოფზე, ანუ, LCM(a, b)=a b: GCM(a, b).

მტკიცებულება.

დაე M არის a და b რიცხვების რამდენიმე ჯერადი. ანუ M იყოფა a-ზე და გაყოფის განმარტებით არის გარკვეული k რიცხვი ისეთი, რომ ტოლობა M=a·k მართალია. მაგრამ M ასევე იყოფა b-ზე, შემდეგ a k იყოფა b-ზე.

აღნიშნეთ gcd(a, b) როგორც d. მაშინ ჩვენ შეგვიძლია ჩავწეროთ ტოლობები a=a 1 ·d და b=b 1 ·d, და a 1 =a:d და b 1 =b:d იქნება თანაპირდაპირი რიცხვები. მაშასადამე, წინა აბზაცში მიღებული პირობა, რომ k იყოფა b-ზე, შეიძლება ჩამოყალიბდეს შემდეგნაირად: a 1 d k იყოფა b 1 d-ზე და ეს, გაყოფადობის თვისებებიდან გამომდინარე, უდრის იმ პირობას, რომ a 1 k. იყოფა b ერთზე.

ჩვენ ასევე უნდა ჩამოვწეროთ ორი მნიშვნელოვანი დასკვნა განხილული თეორემიდან.

ორი რიცხვის საერთო ჯერადი იგივეა, რაც მათი უმცირესი საერთო ჯერადი.

ეს ასეა, რადგან M რიცხვების ნებისმიერი საერთო ჯერადი a და b განისაზღვრება ტოლობით M=LCM(a, b) t ზოგიერთი მთელი რიცხვისთვის t .

თანაპირდაპირი დადებითი რიცხვების a და b უმცირესი საერთო ჯერადი მათი ნამრავლის ტოლია.

ამ ფაქტის დასაბუთება საკმაოდ აშკარაა. ვინაიდან a და b არის თანაპრიმიტეტები, მაშინ gcd(a, b)=1, შესაბამისად, LCM(a, b)=a b: GCD(a, b)=a b:1=a b.

სამი ან მეტი რიცხვის უმცირესი საერთო ჯერადი

სამი ან მეტი რიცხვის უმცირესი საერთო ჯერადის პოვნა შეიძლება შემცირდეს ორი რიცხვის LCM-ის თანმიმდევრულ პოვნამდე. როგორ კეთდება ეს ნაჩვენებია შემდეგ თეორემაში: a 1, a 2,…, a k ემთხვევა m k-1 და a k რიცხვების საერთო ჯერადებს, შესაბამისად, ემთხვევა m k-ის ჯერადებს. და რადგან m k რიცხვის უმცირესი დადებითი ჯერადი არის თავად m k რიცხვი, მაშინ a 1, a 2, …, a k რიცხვების უმცირესი საერთო ჯერადი არის m k.

ბიბლიოგრაფია.

• ვილენკინი ნ.ია. და ა.შ მათემატიკა. მე-6 კლასი: სახელმძღვანელო საგანმანათლებლო დაწესებულებებისთვის.
• ვინოგრადოვი ი.მ. რიცხვების თეორიის საფუძვლები.
• მიხელოვიჩ შ.ხ. რიცხვების თეორია.
• კულიკოვი ლ.ია. და სხვა ამოცანების კრებული ალგებრაში და რიცხვთა თეორიაში: სახელმძღვანელო ფიზ.-მატ. პედაგოგიური ინსტიტუტების სპეციალობები.

ეს სტატია ეხება ყველაზე დიდი საერთო გამყოფის პოვნა (gcd)ორი ან მეტი ნომერი. პირველ რიგში, განიხილეთ ევკლიდის ალგორითმი, ის საშუალებას გაძლევთ იპოვოთ ორი რიცხვის GCD. ამის შემდეგ, ჩვენ შევჩერდებით მეთოდზე, რომელიც საშუალებას გვაძლევს გამოვთვალოთ რიცხვების GCD, როგორც მათი საერთო მარტივი ფაქტორების ნამრავლი. შემდეგი, ჩვენ განვიხილავთ სამი ან მეტი რიცხვის უდიდესი საერთო გამყოფის პოვნას და ასევე მოვიყვანთ უარყოფითი რიცხვების GCD-ის გამოთვლის მაგალითებს.

გვერდის ნავიგაცია.

ევკლიდის ალგორითმი GCD-ს საპოვნელად

გაითვალისწინეთ, რომ თავიდანვე მარტივი რიცხვების ცხრილს რომ მივმართოთ, გავიგებდით, რომ რიცხვები 661 და 113 მარტივია, საიდანაც მაშინვე შეგვიძლია ვთქვათ, რომ მათი ყველაზე დიდი საერთო გამყოფი არის 1.

პასუხი:

gcd(661, 113)=1.

GCD-ის პოვნა რიცხვების ძირითად ფაქტორებად გადაყვანით

განიხილეთ სხვა გზა GCD-ის მოსაძებნად. ყველაზე დიდი საერთო გამყოფის პოვნა შესაძლებელია რიცხვების მარტივ ფაქტორებად გამრავლებით. ჩამოვაყალიბოთ წესი: a და b ორი დადებითი მთელი რიცხვის gcd ტოლია ყველა საერთო მარტივი ფაქტორების ნამრავლის a და b-ის პირველ ფაქტორიზაციებში..

მოდით მოვიყვანოთ მაგალითი GCD-ის პოვნის წესის ასახსნელად. გავიგოთ 220 და 600 რიცხვების გაფართოებები მარტივ ფაქტორებად, მათ აქვთ ფორმა 220=2 2 5 11 და 600=2 2 2 3 5 5 . საერთო მარტივი ფაქტორები, რომლებიც მონაწილეობენ 220 და 600 რიცხვების გაფართოებაში არის 2, 2 და 5. ამიტომ gcd(220, 600)=2 2 5=20 .

ამრიგად, თუ a და b რიცხვებს დავშლით მარტივ ფაქტორებად და ვიპოვით მათი საერთო ფაქტორების ნამრავლს, მაშინ ეს იპოვის a და b რიცხვების უდიდეს საერთო გამყოფს.

განვიხილოთ GCD-ის პოვნის მაგალითი გამოცხადებული წესის მიხედვით.

მაგალითი.

იპოვეთ 72-ისა და 96-ის უდიდესი საერთო გამყოფი.

გამოსავალი.

მოდით გავამრავლოთ რიცხვები 72 და 96:

ანუ 72=2 2 2 3 3 და 96=2 2 2 2 2 3 . საერთო მარტივი ფაქტორებია 2, 2, 2 და 3. ასე რომ, gcd(72, 96)=2 2 2 3=24 .

პასუხი:

gcd(72, 96)=24.

ამ ნაწილის დასასრულს, ჩვენ აღვნიშნავთ, რომ gcd-ის პოვნის ზემოაღნიშნული წესის მართებულობა გამომდინარეობს უდიდესი საერთო გამყოფის თვისებიდან, რომელიც აცხადებს, რომ GCD(m a 1, m b 1)=m GCD(a 1, b 1), სადაც m არის ნებისმიერი დადებითი მთელი რიცხვი.

სამი ან მეტი რიცხვის GCD-ის პოვნა

სამი ან მეტი რიცხვის უდიდესი საერთო გამყოფის პოვნა შეიძლება შემცირდეს ორი რიცხვის gcd-ის თანმიმდევრულ პოვნამდე. ეს აღვნიშნეთ GCD-ის თვისებების შესწავლისას. იქ ჩამოვაყალიბეთ და დავამტკიცეთ თეორემა: a 1 , a 2 , ... რამდენიმე რიცხვის უდიდესი საერთო გამყოფი, a k უდრის d k რიცხვს, რომელიც გვხვდება gcd(a 1, a 2)=d 2-ის თანმიმდევრულ გამოთვლაში. , gcd(d 2, a 3) =d 3, GCD(d 3, a 4)=d 4, …, GCD(d k-1, a k)=d k.

ვნახოთ, როგორ გამოიყურება რამდენიმე რიცხვის GCD-ის პოვნის პროცესი მაგალითის ამოხსნის გათვალისწინებით.

მაგალითი.

იპოვეთ ოთხი რიცხვის უდიდესი საერთო გამყოფი 78, 294, 570 და 36.

გამოსავალი.

ამ მაგალითში a 1 =78, a 2 =294, a 3 =570, a 4 =36.

პირველ რიგში, ევკლიდეს ალგორითმის გამოყენებით, ვადგენთ უდიდეს საერთო გამყოფს d 2 პირველი ორი რიცხვიდან 78 და 294. გაყოფისას ვიღებთ ტოლობას 294=78 3+60 ; 78=60 1+18 ; 60=18 3+6 და 18=6 3 . ამრიგად, d 2 =GCD(78, 294)=6.

ახლა გამოვთვალოთ d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). კვლავ ვიყენებთ ევკლიდეს ალგორითმს: 570=6·95 , შესაბამისად, d 3 =GCD(6, 570)=6 .

რჩება გამოთვლა d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). ვინაიდან 36 იყოფა 6-ზე, მაშინ d 4 \u003d GCD (6, 36) \u003d 6.

ამრიგად, ოთხი მოცემული რიცხვის უდიდესი საერთო გამყოფი არის d 4 =6, ანუ gcd(78, 294, 570, 36)=6.

პასუხი:

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

რიცხვების მარტივ ფაქტორებად დაშლა ასევე საშუალებას გაძლევთ გამოთვალოთ სამი ან მეტი რიცხვის GCD. ამ შემთხვევაში, უდიდესი საერთო გამყოფი გვხვდება მოცემული რიცხვების ყველა საერთო მარტივი ფაქტორების ნამრავლად.

მაგალითი.

გამოთვალეთ წინა მაგალითის რიცხვების GCD მათი მარტივი ფაქტორიზაციების გამოყენებით.

გამოსავალი.

78, 294, 570 და 36 რიცხვებს ვანაწილებთ მარტივ ფაქტორებად, ვიღებთ 78=2 3 13, 294=2 3 7 7, 570=2 3 5 19, 36=2 2 3. 3. ოთხივე რიცხვის საერთო მარტივი ფაქტორები არის რიცხვები 2 და 3. შესაბამისად, GCD(78, 294, 570, 36)=2 3=6.