ყველაზე დიდი მძინარე

ვისენია 2

როდესაც ნატურალური რიცხვი a იყოფა ნატურალურ რიცხვზე $b$, $b$-ს ეწოდება $a$ რიცხვის გამყოფი, ხოლო $a$ რიცხვს ეწოდება $b$ რიცხვის ჯერადი.

დაე, $a$ და $b$ იყოს ნატურალური რიცხვები. რიცხვს $c$ ეწოდება საძილე ნომერი i $a$-ისთვის და $b$-ისთვის.

არ არსებობს $a$ და $b$ რიცხვები, მხოლოდ ამ რიცხვებიდან არ შეიძლება იყოს $a$-ზე მეტი. ამ ინვესტორებს შორის არის ყველაზე დიდი, რომელსაც უწოდებენ $a$ და $b$ ინვესტორთა უდიდეს რაოდენობას და ამ მიზნით, vikory ჩანაწერები:

$gcd\(a;b)\ან\D\(a;b)$

ორ რიცხვს შორის ყველაზე დიდი გაყოფის გასარკვევად, საჭიროა:

1. შეიტყვეთ მეტი crotz 2-ზე ნაპოვნი ნომრებიდან. იპოვეთ ნომერი და ის იქნება ყველაზე დიდი მოძებნილი საძილე.

კონდახი 1

იპოვეთ რიცხვების gcd $121$ და $132.$

$242=2\cdot 11\cdot 11$

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

აირჩიეთ ნომრები, რომლებიც უნდა შეიყვანოთ ნომრების ჩამოყალიბებამდე

$242=2\cdot 11\cdot 11$

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

შეიტყვეთ მეტი crotz 2-ზე ნაპოვნი ნომრებიდან. იპოვეთ ნომერი და ის იქნება ყველაზე დიდი მოძებნილი საძილე.

$GCD=2\cdot 11=22$

კონდახი 2

იპოვეთ მონომილების gcd $63$ და $81$.

ჩვენ ყველაფერი გვეცოდინება წარმოდგენილი ალგორითმის შესახებ. ვისთვის:

მოდით დავშალოთ რიცხვები მარტივ მამრავლებად

$63=3\cdot 3\cdot 7$

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

აირჩიეთ ნომრები, რომლებიც უნდა შეიყვანოთ ნომრების ჩამოყალიბებამდე

$63=3\cdot 3\cdot 7$

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

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

$GCD=3\cdot 3=9$

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

კონდახი 3

იპოვეთ რიცხვების gcd $48$ და $60$.

გადაწყვეტილება:

ჩვენ ვიცით რიცხვი $48$: $\მარცხნივ\((\rm 1,2,3.4.6,8,12,16,24,48)\მარჯვნივ\)$

ახლა ჩვენ ვიცით რიცხვები $60$:$\ \მარცხნივ\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\მარჯვნივ\)$

ჩვენ ვიცით განსხვავება ამ სიმრავლეს შორის: $ \ მარცხენა \ (( \ rm 1,2,3,4,6,12) \ მარჯვენა \) $ - ეს ნიშნავს სხვადასხვა რიცხვების რაოდენობას $ 48 $ და $ 60 $. ამ სიმრავლის ყველაზე დიდი ელემენტი იქნება რიცხვი $12$. ეს ნიშნავს, რომ რიცხვების უდიდესი კომბინაცია $48$ და $60$ იქნება $12$.

ვაზნაჩენნაია NOC

Vicenzennya 3

ნატურალური რიცხვების ზაგალნიმი ნამრავლი$a$ და $b$ არის ბუნებრივი რიცხვი, რომელიც არის $a$ და $b$-ის ჯერადი.

რიცხვებს, რომლებიც შაბათ-კვირას იყოფა გადაჭარბების გარეშე, რიცხვების ჯერადი ეწოდება.

ჰალალის ჯერადებიდან უმცირესს ეწოდება უმცირესი ჰალალის ჯერადი და დასახელდება LOC$(a;b)$ ან K$(a;b).$

იმისათვის, რომ იცოდეთ ორი რიცხვის LCM, თქვენ უნდა:

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

კონდახი 4

იცოდეთ $99$ და $77$ ნომრების LCM.

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

დაყავით რიცხვები მარტივ მამრავლებად

$99=3\cdot 3\cdot 11$

Vipisati მამრავლები, რა უნდა შევიდეს საწყობამდე ჯერ

დაამატეთ მათ მრავლობითი, მაგალითად, სხვის საწყობში შესვლა და პირველის საწყობში არ წასვლა

შეიტყვეთ რუკაზე ნაპოვნი მეტი რიცხვი 2. იპოვეთ რიცხვი i იქნება რიცხვის უმცირესი ჯერადი

$NOK=3cdot 3cdot 11cdot 7=693$

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

მტკიცედ, რა საფუძველზეა ევკლიდეს ალგორითმი:

ვინაიდან $a$ და $b$ ნატურალური რიცხვებია და $a\vdots b$, მაშინ $D(a;b)=b$

ვინაიდან $a$ და $b$ ნატურალური რიცხვებია, ასეა $b

$D(a;b)= D(a-b;b)$-ის გამოთვლით, შეგიძლიათ თანმიმდევრულად შეცვალოთ ეს რიცხვები, სანამ არ მიაღწევთ რიცხვების წყვილს ისე, რომ ერთი მათგანი იყოფა მეორეზე. ამ რიცხვებიდან ყველაზე პატარა იქნება ყველაზე დიდი შესატყვისი ნომრებისთვის $a$ და $b$.

NOD და NOC-ის ძალა

1. თუ $a$ და $b$ რიცხვების რომელიმე ჯერადი იყოფა K$(a;b)$-ზე
2. თუ $a\vdots b$, მაშინ $(a;b)=a$

თუ K$(a;b)=k$ და $m$ ნატურალური რიცხვია, მაშინ K$(am;bm)=km$

თუ $d$ არის $a$-ისა და $b$-ის საბოლოო დილატორი, მაშინ K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

თუ $a\vdots c$ i $b\vdots c$, მაშინ $\frac(ab)(c)$ არის $a$ და $b$ რიცხვების ჯერადი.

ნებისმიერი ნატურალური რიცხვისთვის $a$ და $b$ გამოითვლება თანასწორობა

$D(a;b)\cdot ადრე(a;b)=ab$

$a$ და $b$ რიცხვების ნათესავი არის თუ არა $D(a;b)$ რიცხვის თანატოლი

1.1 ევკლიდეს ალგორითმის განმარტება

როგორც კი რობოტი კარგად არის აგებული, ევკლიდეს ალგორითმი ბევრად მეტს იძლევა, მაგრამ, როგორც ჩანს, დასაწყისი შეიძლება წაიშალოს. ამ გამოკვლევიდან ირკვევა, მაგალითად, რომ მოვალეთა მთლიანობა i b მსგავსია მოვალეთა მთლიანობისა (a, b). ასევე არსებობს პრაქტიკული გზა, რომ ვიპოვოთ u და v რიცხვები Z-დან (ან, მე-2 პუნქტის თეორემის მიხედვით) ისე, რომ

r n = au + bv = (a, b).

სინამდვილეში, ეჭვიანობის ლანგარიდან შეგვიძლია ვთქვათ:

r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n =...

(მოდით, ვიაროთ გზაზე ქვემოდან ზევით, კანიდან განვსაზღვროთ ჭარბი რაოდენობა და წარმოვადგინოთ ის ვირუსში, რომელიც აქამდე ყველაზე მაღალია)

Au + bv = (a, b).

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

უპირველეს ყოვლისა, მას აბრალებდნენ ძველი ვაჭრების კომერციულ პრაქტიკას, როდესაც საჭირო იყო მთელი რიცხვების სხვადასხვა რაოდენობის თვალყურის დევნება. მაგალითად, როგორ ვაფასებთ ნომრებს 3703700 და 1234567 და 22962965 და 7654321 ნომრებს? სრულიად ბუნებრივი იყო იმის გარკვევა, თუ რამდენჯერ ნაკლები თანხაა ჩადებული მეტში. ადვილია იმის გადამოწმება, რომ 3703700 = 2 · 1234567 + 1234566, და 22962965 = 3 · 7654321 + 2. ახლა გასაგებია, რომ 3703700-დან 1234567-ის თანაფარდობა 5-ზე ნაკლებია, ვიდრე თანაფარდობა.

2,99999919 <= 3, 000000261,

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

თუ გექნებოდათ შესაძლებლობა, გაათანაბროთ რიცხვების მიმდებარე ცხრილები, მაგალითად, i, მაშინ გამოთვლები დაიკეცებოდა:

71755875 = 61735500 + 10020375;

61735500 = 6 10020375 + 1613250;

10020375 = 6 1613250 + 340875;

1613250 = 4 340875 + 249750;

340875 = 249750 + 91125;

249750 = 2 91125 + 67500;

91125 = 67500 + 23625;

67500 = 2 23625 + 20250;

23625 = 20250 + 3375;

20250 = 6 3375.

ევკლიდეს ალგორითმი აქ საშუალებას გაძლევთ გამოთვალოთ 71755875 და 61735500 რიცხვების GCD, უდრის 3375, და აჩვენებს 71755875-დან 61735500 ლანცუგის წილადების თანაფარდობის განაწილებას:

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

წილადის ტოლია, თანამედროვე მათემატიკაში მას უწოდებენ „ქვემდებარე წილადს“, გაფართოებულ მიმართებას b = ლანცუგიურ (ან შეუწყვეტელ) წილადად.

მივხვდი რომ

b = 1 +< 1 + и б=1 + > 1+ = ,

ფრაგმენტები

რემონტი III საუკუნეში განხორციელდა. ძვ.წ არისტარქ სამოსკი ტრაქტატში "თვესა და მზის ამოსვლასა და ამოსვლის შესახებ".

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

ალგორითმები მდიდარი ტერმინებით

ევკლიდეს ალგორითმი არის მეთოდი ორი მთელი რიცხვისთვის ყველაზე დიდი ტერმინის, ასევე ერთი ცვლადის ორი მრავალჯერადი წევრის საპოვნელად...

ერთ-ერთი უახლესი მათემატიკური ალგორითმი არის ევკლიდის ალგორითმი ორი დადებითი რიცხვის უდიდესი დანამატის მოსაძებნად. იოგოს ღერძი უმარტივეს ფორმაში. მიეცით ორი მთელი რიცხვი. რა სუნია...

ევკლიდეს ალგორითმის ანალიზი ევკლიდეს რგოლებში

ჯერ ევკლიდეს ალგორითმის გაანალიზებამდე გადავხედავთ ფიბონაჩის რიცხვებს. ფიბონაჩის მიმდევრობის არსი ის არის, რომ 1.1-დან დაწყებული, შემდეგი რიცხვი გამოდის წინა ორიდან. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ……

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

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

გაუსის მთელი რიცხვების რგოლი

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

ზალიშკოვის კლასის სისტემის მათემატიკური ჩასაფრები

მოდით შევხედოთ კონდახს. მოდით r = 6. მაშინ არის ექვსი კლასი მთელი რიცხვების სიმრავლის გაყოფის მოდულო 6: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; სადაც r ნიშნავს 6-ზე მთელი რიცხვის გაყოფის ნამეტს...

კლასგარეშე აქტივობებში მდიდარი კიდურების მომზადების მეთოდოლოგია უფროს საშუალო სკოლაში შუქის მიღმა სკოლა

დაე, მდიდარი წევრების ბეჭედი გაიაროს. მნიშვნელობა 1: თუ არის მდიდარი წევრი, მაშინ ჭარბი ტოლია ნულის, მაშინ მას უწოდებენ მდიდარი ტერმინის წარმოებულს და აღინიშნება: ()...

ყოველდღიური მათემატიკის განვითარებისა და სტრუქტურის ძირითადი ეტაპები

III საუკუნეში ალექსანდრიაში გამოჩნდა ევკლიდეს წიგნი ამავე სახელწოდებით, თარგმანში „კობი“. ლათინური სახელწოდება "კობი" მსგავსია ტერმინი "ელემენტარული გეომეტრია". ნუ აინტერესებთ ამათ...

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

ეკონომიკის დისკრეტული მათემატიკის მეთოდების დამკვიდრება.

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

ცნების „სივრცე“ და არაევკლიდური გეომეტრიის შემუშავება

რაციონალური ვირუსების ინტეგრაციის სპეციალური მეთოდები

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

ჭარბი თეორია

ჭარბი თეორია

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

ჭარბი თეორია

იაკჩო (ა, ბ) = დ...

გთხოვთ, არ დაგავიწყდეთ წრფივი დიოფანტინის განტოლების შექმნა: ax + by = c, de a, b, c Z; a და b არ არის ნულები. შევეცადოთ გაქრობა, გაოცებული ცენტრით. მოდით (a, b) = d. Todi a = a 1 d; b = b 1 d და განტოლება ასე გამოიყურება: a 1 d x + b 1 d y y = c, მაშინ. d·(a 1 x + b 1 y) = c... Qia სტატია შესახებყველაზე დიდი საძილე მარაგის პოვნა (NDD)

ორი ან მეტი ნომერი. მოდით შევხედოთ ევკლიდეს ალგორითმს, რომელიც საშუალებას გაძლევთ იპოვოთ ორი რიცხვის 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 რიცხვების დაშლაში. Otzhe, gcd (220, 600) = 2 2 5 = 20.

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

მოდით შევხედოთ GCD ცოდნის კონდახს აღნიშნული წესის უკან.

კონდახი.

იპოვეთ 72 და 96 რიცხვების უდიდესი რაოდენობა.

გადაწყვეტილება.

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

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

ტობტო, 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-ის პოვნის დადგენილი წესის ვალიდობა ემყარება ყველაზე დიდი საერთო მოვალის სიძლიერეს, რაც ადასტურებს, რომ GCD(m a 1, m b 1)=m GCD(a 1, b 1), სადაც m არის მთელი დამატებითი რიცხვი.

სამი ან მეტი რიცხვის gcd-ის მნიშვნელობა

სამი ან მეტი რიცხვის უდიდესი ნაწილის აღმოჩენა შეიძლება შემცირდეს ორი რიცხვის gcd-ის თანმიმდევრულ აღმოჩენამდე. ჩვენ დავინტერესდით ეს NOD-ის ხელისუფლების გავლენით. იქ ჩამოვაყალიბეთ და დავასრულეთ თეორემა: რიცხვების უდიდესი ფარული მნიშვნელობა a 1 , a 2 , ..., ak მსგავსია 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-ის პოვნის პროცესი, გადავხედოთ გამოსავალს მაგალითში.

მოდით შევხედოთ GCD ცოდნის კონდახს აღნიშნული წესის უკან.

იპოვეთ რიცხვების უდიდესი რაოდენობა 78, 294, 570 და 36.

იპოვეთ 72 და 96 რიცხვების უდიდესი რაოდენობა.

ამ შემთხვევაში 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

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

ახლა ის რაოდენობრივად არის განსაზღვრული d 3 = GCD (d 2 , a 3) = GCD (6, 570). კიდევ ერთხელ, ევკლიდეს ალგორითმი ჩერდება: 570 = 6 95, შემდეგ, d 3 = gcd (6, 570) = 6.

ძალიან ბევრია დასათვლელი d 4 = GCD (d 3 , a 4) = GCD (6, 36). 36-ის ფრაგმენტები იყოფა 6-ზე, შემდეგ d 4 = gcd (6, 36) = 6.

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

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

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

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

მოდით შევხედოთ GCD ცოდნის კონდახს აღნიშნული წესის უკან.

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

იპოვეთ 72 და 96 რიცხვების უდიდესი რაოდენობა.

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.

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

GCD-ის გაანგარიშება ნახევრად

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

1. გაყავით მეტი (გამყოფი) ნაკლებზე (გამყოფი): 108 / 72 = 1, ჭარბი 36.
2. ჭარბი ნარჩენები ნულს არ აღწევს, შემდეგ ნამეტს ვყოფთ მოვალედ, ნამეტს კი მოვალედ: 72 / 36 = 2, ჭარბი 0.
3. თუ ჭარბი ტოლია ნულის, ინვესტორი ეძებს GCD-ს მოცემული რიცხვების წყვილისთვის. შემდეგ GCD(108, 72) = 36. მართალია, 108/36 = 3 და 72/36 = 2.

ვისი ალგორითმი? გაყოფა მეორდება მანამ, სანამ ჭარბი არ გახდება ნულის ტოლი. თუ ასე დარჩები, GODOM არის დარჩენილი ქვეველის მეწილე. მაგალითად, თქვენ უნდა იცოდეთ GCD(106, 16):

1. 106/16 = 6, ჭარბი 10
2. 16/10 = 1, ჭარბი 6
3. 10/6 = 1, ჭარბი 4
4. 6/4 = 1, ჭარბი 2
5. 4/2 = 2, ჭარბი 0
6. gcd(106, 16) = 2

ხელფასების NID-ის გაანგარიშება

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

შეგვატყობინეთ GCD (108, 72):

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

ცნობილი GCD(44, 60):

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

ეს ალგორითმი ზოგჯერ სხვაგვარად არის აღწერილი. მნიშვნელოვანია დასრულება უფრო ადრე, მოკლე მხარეს, თუ ერთი რიცხვი მთლიანად იყოფა მეორეზე. თარიღის შერწყმა დილიგენციის შემოწმებასთან. შემდეგ GCD-ის ხელახალი ფორმირება 44 და 60-ისთვის ასე გამოიყურება:

1. რატომ გავყოთ 44 60-ზე? არა. 60 - 44 = 16.
2. როგორ გავყოთ 16 44-ზე? არა. 44 - 16 = 28.
3. როგორ გავყოთ 16 28-ზე? არა. 28 - 16 = 12.
4. როგორ გავყოთ 12 16-ზე? არა. 16 - 12 = 4.
5. როგორ გავყოთ 4 12-მდე? Ისე. Otzhe, gcd(44, 60) = 4.

დააბრუნე პატივისცემა ღმერთი არ არის პირადი, არამედ პირადი. თუ კონდახზე 12-ს გავყოფთ 4-ზე, გამოვაკლებთ 3-ს. ეს არ არის GCD.

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

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

თუ a/b სრულია, მაშინ gcd(a, b) = b. მაგალითად, gcd(15, 5) = 5.

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

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

იაკშო ა< b, то НОД(a, b) = НОД(a, b - a).

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

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

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

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

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

1. მეტი იყოფა ნაკლებზე.
2. თუ გაყოფთ ზედმეტის გარეშე, მაშინ ნაკლები და є GCD (ციკლის დატოვების შემდეგ).
3. თუ არის ჭარბი, მაშინ მეტი იცვლება ჭარბი ქვემოდან.
4. გადავიდეთ 1 პუნქტზე.

კონდახი:
იპოვეთ gcd 30 და 18-ისთვის.
30/18 = 1 (12 დამატებითი)
18/12 = 1 (6-ზე მეტი)
12/6 = 2 (ზედმეტი 0)
კინეტები: GCD – tsedelnik 6.
GCD(30, 18) = 6

a = 50 b = 130 ხოლო a != 0 და b != 0 : თუ a > b: a = a % b სხვა: b = b % ბეჭდვა (a + b)

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

ალგორითმი NID მონაცემების მოსაძებნად

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

კონდახი:
იპოვეთ gcd 30 და 18-ისთვის.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
დასასრული: GCD - არ იცვლება ან ჩნდება.
GCD(30, 18) = 6

a = 50 b = 130 ხოლო a != b: თუ a > b: a = a - b სხვა : b = b - ბეჭდვა (a)