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

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

მოძიება ფაქტორინგით

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

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

მაგალითი 1მოდი ვიპოვოთ GCD (84, 90).

ჩვენ ვყოფთ რიცხვებს 84 და 90 მარტივ ფაქტორებად:

ამრიგად, ჩვენ ხაზი გავუსვით ყველა საერთო პირველ ფაქტორს, რჩება მათი ერთმანეთში გამრავლება: 1 2 3 = 6.

ასე რომ, gcd (84, 90) = 6.

მაგალითი 2ვიპოვოთ GCD (15, 28).

ჩვენ ვშლით 15 და 28 პირველ ფაქტორებად:

რიცხვები 15 და 28 თანაპირველია, რადგან მათი ყველაზე დიდი საერთო გამყოფი არის ერთი.

gcd (15, 28) = 1.

ევკლიდეს ალგორითმი

მეორე მეთოდი (სხვაგვარად ევკლიდის მეთოდს უწოდებენ) არის GCD-ის პოვნა თანმიმდევრული გაყოფით.

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

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

მაგალითი 1ავიღოთ ორი რიცხვი 27 და 9. ვინაიდან 27 იყოფა 9-ზე და 9 იყოფა 9-ზე, მაშინ 9 არის 27 და 9 რიცხვების საერთო გამყოფი. ეს გამყოფი ასევე ყველაზე დიდია, რადგან 9 არ შეიძლება დაიყოს არცერთ რიცხვზე. 9-ზე მეტი. ამიტომ, gcd (27, 9) = 9.

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

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

მაგალითი 2ვიპოვოთ 140 და 96 რიცხვების უდიდესი საერთო გამყოფი:

1) 140: 96 = 1 (დარჩენილი 44)

2) 96: 44 = 2 (დარჩენილი 8)

3) 44: 8 = 5 (დარჩენილი 4)

ბოლო გამყოფი არის 4, რაც ნიშნავს gcd(140, 96) = 4.

თანმიმდევრული გაყოფა ასევე შეიძლება დაიწეროს სვეტში:

სამი ან მეტი რიცხვის უდიდესი საერთო გამყოფის საპოვნელად გამოიყენეთ შემდეგი პროცედურა:

1. პირველი, იპოვნეთ ნებისმიერი ორი რიცხვის უდიდესი საერთო გამყოფი მრავალი მონაცემთა ნაკრებიდან.
2. შემდეგ ვპოულობთ ნაპოვნი გამყოფის GCD-ს და მესამე მოცემულ რიცხვს.
3. შემდეგ ვპოულობთ ბოლო ნაპოვნი გამყოფის GCD-ს და მეოთხე მოცემულ რიცხვს და ა.შ.

მაგალითი 3ვიპოვოთ 140, 96 და 48 რიცხვების უდიდესი საერთო გამყოფი. წინა მაგალითში უკვე ვიპოვეთ 140 და 96 რიცხვების GCD (ეს არის რიცხვი 4). რჩება 4 რიცხვისა და მესამე მოცემული რიცხვის უდიდესი საერთო გამყოფის პოვნა - 48:

48 იყოფა ოთხზე ნაშთის გარეშე. ასე რომ, gcd (140, 96, 48) = 4.

რიცხვის წარმოდგენა მარტივი რიცხვების ნამრავლად ეწოდება ამ რიცხვის დაშლა პირველ ფაქტორებად.

მაგალითად, ჩანაწერი 110 = 2 5 11 მიუთითებს, რომ რიცხვი 110 იშლება პირველ ფაქტორებად 2, 5 და 11.

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

რიცხვების მარტივ ფაქტორებად დაშლისას, 2-ზე, 3-ზე, 5-ზე და ა.შ. გაყოფის ნიშნების გამოყენებით, გავიხსენოთ რიცხვის დაშლის მარტივ ფაქტორებად ჩაწერის ხერხი. მოდით დავშალოთ, მაგალითად, რიცხვი 720 მარტივ ფაქტორებად. რიცხვი 720 იყოფა 2-ზე. აქედან გამომდინარე, 2 არის 720 რიცხვის დაშლის ერთ-ერთი მთავარი ფაქტორი. 720 გავყოთ 2-ზე. რიცხვი 2 იწერება ტოლობის ნიშნის მარჯვენა და 720 რიცხვის ქვეშ იწერება კოეფიციენტი 360. რიცხვი 360 გავყოთ 2-ზე მივიღებთ 180. 180 გავყოთ 2-ზე, მივიღებთ 90-ს, გავყოფთ 90-ს 2-ზე, მივიღებთ 45-ს, ვყოფთ 45-ზე. 3, მივიღებთ 15-ს, ვყოფთ 15-ს 3-ზე, მივიღებთ 5. რიცხვი 5 არის მარტივი, როდესაც გავყოფთ 5-ზე ვიღებთ 1. ფაქტორიზაცია დასრულებულია.

720 = 2 2 2 2 3 3 5

ჩვეულებრივია იდენტური ფაქტორების ნამრავლის ჩანაცვლება სიმძლავრით: 720 = 5. 720 რიცხვის ასეთი წარმოდგენა ე.წ. კანონიკური შეხედულებაეს ნომერი.

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

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

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

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

3600 და 288 რიცხვების უდიდესი საერთო გამყოფის პირველ ფაქტორიზაციით, ყველა საერთო მარტივი გამრავლება,რომლებსაც შეიცავს მოცემული რიცხვების გაფართოებები და თითოეული მათგანი უნდა იყოს აღებული ყველაზე დაბალი მაჩვენებელირომლითაც იგი ორივე გაფართოებაში შედის. მაშასადამე, 3600 და 288 რიცხვების უდიდესი საერთო გამყოფის გაფართოება მოიცავს ფაქტორებს და . ასე რომ, D (3600? 288) = · = 144.

3600-ისა და 288-ის უმცირესი საერთო ჯერადის ძირითადი ფაქტორიზაცია უნდა მოიცავდეს ყველა მარტივ ფაქტორს, რომელიც შეიცავს ერთში მაინც 3600 და 288 რიცხვების გაფართოებებიდან და თითოეული მათგანი უნდა იქნას აღებული უმაღლესი ქულით,შედის ამ რიცხვების ორივე გაფართოებაში. მაშასადამე, 3600-ისა და 288-ის უმცირესი საერთო ჯერადის გაფართოება მოიცავს ფაქტორებს , , 5. აქედან გამომდინარე,

K (3600, 288) = 5 = 7200.

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

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

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

მოცემული რიცხვების უმცირესი საერთო ჯერადის საპოვნელად:

1) ჩვენ წარმოვადგენთ თითოეულ მოცემულ რიცხვს კანონიკური ფორმით;

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

3) ჩვენ ვიპოვით ამ ნამრავლის მნიშვნელობას - ეს იქნება ამ რიცხვების უმცირესი საერთო ჯერადი.

ბილეთის ნომერი 45. რიცხვების უმცირესი საერთო ჯერადი. მისი თვისებები და აღმოჩენის მეთოდები. მაგალითები.

უმცირესი საერთო ჯერადი (LCM) გამოთვლა gcd (უმცირესი საერთო გამყოფის) მეშვეობით

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

მაგალითი.

იპოვეთ ორი რიცხვის უმცირესი საერთო ჯერადი 126 და 70 .

გამოსავალი.

ამ მაგალითში a=126, b=70. მოდით გამოვიყენოთ ფორმულით გამოხატული კავშირი LCM-სა და GCD-ს შორის LCM(a, b)=a b: GCM(a, b). ანუ ჯერ უნდა ვიპოვოთ რიცხვების უდიდესი საერთო გამყოფი 70 და 126 , რის შემდეგაც შეგვიძლია დაწერილი ფორმულის მიხედვით გამოვთვალოთ ამ რიცხვების LCM.

მოდი ვიპოვოთ GCD(126, 70)ევკლიდის ალგორითმის გამოყენებით: 126=70 1+56, 70=56 1+14, 56=14 4, შესაბამისად, gcd(126, 70)=14.

ახლა ჩვენ ვიპოვით საჭირო უმცირეს საერთო ჯერადს: LCM(126, 70)=126 70: GCM(126, 70)=126 70:14=630.

პასუხი:

LCM(126, 70)=630.

მაგალითი.

რისი ტოლია NOC(68, 34)?

გამოსავალი.

იმიტომ რომ 68 მთლიანად იყოფა 34 , მაშინ GCD(68, 34)=34. ახლა ჩვენ ვიანგარიშებთ უმცირეს საერთო ჯერადს: LCM(68, 34)=68 34:GCM(68, 34)=68 34:34=68.

პასუხი:

LCM(68, 34)=68.

გაითვალისწინეთ, რომ წინა მაგალითი შეესაბამება შემდეგ წესს დადებითი მთელი რიცხვებისთვის LCM-ის მოსაძებნად ადა ბ: თუ ნომერი აიყოფა ბ, მაშინ ამ რიცხვების უმცირესი საერთო ჯერადი არის ა.

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

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

LCM-ის პოვნის გამოცხადებული წესი თანასწორობიდან გამომდინარეობს LCM(a, b)=a b: GCM(a, b). მართლაც, რიცხვების ნამრავლი ადა ბტოლია რიცხვების გაფართოებაში მონაწილე ყველა ფაქტორის ნამრავლის ადა ბ. თავის მხრივ gcd(a, b)უდრის ყველა უბრალო ფაქტორების ნამრავლს, რომლებიც ერთდროულად გვხვდება რიცხვების გაფართოებაში ადა ბ(რომელიც აღწერილია განყოფილებაში GCD-ის პოვნა რიცხვების მარტივ ფაქტორებად გადანაწილებით).

ავიღოთ მაგალითი. გაგვაგებინე ეს 75=3 5 5და 210=2 3 5 7. შეადგინეთ ამ გაფართოების ყველა ფაქტორის პროდუქტი: 2 3 3 5 5 5 7. ახლა ჩვენ გამოვრიცხავთ ამ პროდუქტიდან ყველა იმ ფაქტორს, რომელიც ასევე არსებობს რაოდენობის გაფართოებაში 75 და რიცხვის გაფართოებაში 210 (ასეთი ფაქტორებია 3 და 5 ), შემდეგ პროდუქტი მიიღებს ფორმას 2 3 5 5 7. ამ ნამრავლის მნიშვნელობა უდრის რიცხვთა უმცირეს საერთო ჯერადს 75 და 210 , ანუ LCM(75, 210)= 2 3 5 5 7=1 050.

მაგალითი.

რიცხვების გაფართოება 441 და 700 მარტივ ფაქტორებად იპოვეთ ამ რიცხვების უმცირესი საერთო ჯერადი.

გამოსავალი.

დავშალოთ რიცხვები 441 და 700 ძირითადი ფაქტორებისთვის:

ვიღებთ 441=3 3 7 7და 700=2 2 5 5 7.

ახლა მოდით შევადგინოთ ყველა ფაქტორი, რომელიც მონაწილეობს ამ რიცხვების გაფართოებაში: 2 2 3 3 5 5 7 7 7. მოდით ამ პროდუქტიდან გამოვრიცხოთ ყველა ფაქტორი, რომელიც ერთდროულად არის ორივე გაფართოებაში (არსებობს მხოლოდ ერთი ასეთი ფაქტორი - ეს არის რიცხვი 7 ): 2 2 3 3 5 5 7 7. Ამგვარად, LCM(441, 700)=2 2 3 3 5 5 7 7 = 44 100.

პასუხი:

LCM(441, 700)= 44 100.

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

მაგალითად, ავიღოთ ყველა ერთი და იგივე რიცხვი 75 და 210 მათი ფაქტორიზაცია შემდეგია: 75=3 5 5და 210=2 3 5 7. მამრავლებისკენ 3 , 5 და 5 რიცხვის დაშლისგან 75 2 და 7 რიცხვის დაშლისგან 210 , ჩვენ ვიღებთ პროდუქტს 2 3 5 5 7, რომლის ღირებულებაც არის NOC(75, 210).

მაგალითი.

იპოვეთ რიცხვების უმცირესი საერთო ჯერადი 84 და 648 .

გამოსავალი.

ჩვენ ჯერ ვიღებთ რიცხვების დაშლას 84 და 648 მთავარ ფაქტორებზე. ჰგვანან 84=2 2 3 7და 648=2 2 2 3 3 3 3 3. მამრავლებისკენ 2 , 2 , 3 და 7 რიცხვის დაშლისგან 84 დაკარგული ფაქტორების დამატება 2 , 3 , 3 და 3 რიცხვის დაშლისგან 648 , ჩვენ ვიღებთ პროდუქტს 2 2 2 3 3 3 3 7, რომელიც უდრის 4 536 . ამრიგად, რიცხვების სასურველი უმცირესი საერთო ჯერადი 84 და 648 უდრის 4 536 .

პასუხი:

LCM(84, 648)=4536.

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

Yandex.RTB R-A-339285-1

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

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

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

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

ჩვენ შეგვიძლია დავასრულოთ გაყოფა როდის rk + 1 = 0, სადაც r k = gcd (a, b).

მაგალითი 1

64 და 48 .

გამოსავალი

შემოვიღოთ აღნიშვნა: a = 64 , b = 48 .

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

ვიღებთ 1-ს და დანარჩენს 16-ს. გამოდის, რომ q 1 = 1, r 1 = 16.

მეორე ნაბიჯი არის გაყოფა 48 16-ით მივიღებთ 3-ს. ანუ q2 = 3, ა r 2 = 0.ამრიგად, რიცხვი 16 არის ყველაზე დიდი საერთო გამყოფი პირობის რიცხვებისთვის.

პასუხი: gcd(64, 48) = 16.

მაგალითი 2

რა არის რიცხვების GCD 111 და 432 ?

გამოსავალი

გაყოფა 432 ზე 111 . ევკლიდეს ალგორითმის მიხედვით ვიღებთ ტოლობების ჯაჭვს 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 .

ამრიგად, რიცხვების უდიდესი საერთო გამყოფი 111 და 432 არის 3.

პასუხი: gcd(111, 432) = 3.

მაგალითი 3

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

გამოსავალი

ჩვენ თანმიმდევრულად გავყოფთ რიცხვებს და მივიღებთ GCD-ს (661 , 113) = 1 . ეს ნიშნავს, რომ 661 და 113 შედარებით მარტივი რიცხვებია. ჩვენ შეგვეძლო ამის გარკვევა, სანამ გამოთვლებს დავიწყებდით, თუ გადავხედავდით მარტივ რიცხვების ცხრილს.

პასუხი: gcd(661, 113) = 1.

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

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

მაგალითი 4

თუ 220 და 600 რიცხვებს დავშლით მარტივ ფაქტორებად, მივიღებთ ორ პროდუქტს: 220 = 2 2 5 11და 600 = 2 2 2 3 5 5. ამ ორ პროდუქტში საერთო ფაქტორები იქნება 2, 2 და 5. ეს ნიშნავს, რომ NOD (220, 600) = 2 2 5 = 20.

მაგალითი 5

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

გამოსავალი

იპოვნეთ რიცხვების ყველა მარტივი ფაქტორი 72 და 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

საერთო მარტივი ფაქტორები ორი რიცხვისთვის: 2, 2, 2 და 3. ეს ნიშნავს, რომ NOD (72, 96) = 2 2 2 3 = 24.

პასუხი: gcd(72, 96) = 24.

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

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

იმისდა მიუხედავად, თუ რამდენი რიცხვი უნდა ვიპოვოთ GCD, ჩვენ მივყვებით იმავე ალგორითმს, რომელიც შედგება ზედიზედ ორი რიცხვის GCD-ის პოვნაში. ეს ალგორითმი ეფუძნება შემდეგი თეორემის გამოყენებას: რამდენიმე რიცხვის GCD a 1, a 2,…, a kრიცხვის ტოლია დ კ, რომელიც გვხვდება გკდ-ის თანმიმდევრულ გამოთვლაში (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 .

მაგალითი 6

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

გამოსავალი

მოდით შემოვიტანოთ აღნიშვნა: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

დავიწყოთ 78 და 294 ნომრების GCD-ის მოძიებით: d2= 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-ზე ნაშთის გარეშე. ეს საშუალებას გვაძლევს მივიღოთ d4= GCD (6 , 36) = 6 .

d4 = 6, ანუ GCD (78 , 294 , 570 , 36) = 6 .

პასუხი:

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

მაგალითი 7

გამოთვალეთ 78, 294, 570 და რიცხვების gcd 36 .

გამოსავალი

მოდით დავშალოთ ეს რიცხვები მარტივ ფაქტორებად: 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .

ოთხივე რიცხვისთვის, საერთო მარტივი ფაქტორები იქნება რიცხვები 2 და 3.

გამოდის, რომ NOD (78, 294, 570, 36) = 2 3 = 6.

პასუხი: gcd(78, 294, 570, 36) = 6.

უარყოფითი რიცხვების gcd-ის პოვნა

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

მაგალითი 8

იპოვეთ უარყოფითი მთელი რიცხვების gcd − 231 და − 140 .

გამოსავალი

გამოთვლების შესასრულებლად ავიღოთ პირობით მოცემული რიცხვების მოდულები. ეს იქნება ნომრები 231 და 140. მოკლედ რომ ვთქვათ: GCD (− 231 , − 140) = GCD (231, 140). ახლა გამოვიყენოთ ევკლიდის ალგორითმი ორი რიცხვის მარტივი ფაქტორების მოსაძებნად: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 და 42 = 7 6. ჩვენ ვიღებთ, რომ gcd (231, 140) = 7 .

და მას შემდეგ, რაც NOD (− 231 , − 140) = GCD (231 , 140) , შემდეგ რიცხვების gcd − 231 და − 140 უდრის 7 .

პასუხი: gcd (− 231, − 140) = 7.

მაგალითი 9

დაადგინეთ სამი რიცხვის გგდ - 585, 81 და − 189 .

გამოსავალი

ზემოაღნიშნულ სიაში უარყოფითი რიცხვები ჩავანაცვლოთ მათით აბსოლუტური ღირებულებები, ვიღებთ GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . შემდეგ ჩვენ ვანაწილებთ ყველა მოცემულ რიცხვს მარტივ ფაქტორებად: 585 = 3 3 5 13, 81 = 3 3 3 3 და 189 = 3 3 3 7. მარტივი ფაქტორები 3 და 3 საერთოა სამი რიცხვისთვის. გამოდის, რომ gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 .

პასუხი: GCD (− 585, 81, − 189) = 9.

თუ შეამჩნევთ შეცდომას ტექსტში, მონიშნეთ იგი და დააჭირეთ Ctrl+Enter