სტატიები

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


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

[lem1] თუ (a ) და (b ) ორი მთელი რიცხვია და (a = bq + r ) სადაც ასევე (q ) და (r ) მთელი რიცხვია, მაშინ ((a, ბ) = (რ, ბ) ).

გაითვალისწინეთ, რომ მე –8 თეორემის მიხედვით გვაქვს ((bq + r, b) = (b, r) ).

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

მოდით (a = r_0 ) და (b = r_1 ) იყოს ორი დადებითი მთელი რიცხვი, სადაც (a geq b ). თუ განყოფილების ალგორითმს მივმართავთ თანმიმდევრულად, რომ მივიღოთ [r_j = r_ {j + 1} q_ {j + 1} + r_ {j + 2} mbox {სადაც} 0 leq r_ {j + 2 }

დაყოფის ალგორითმის გამოყენებით, ვხედავთ, რომ [ {{შეესაბამება} r_0 & = & r_1q_1 + r_2 0 leq r_2

ჩვენ ვიხილავთ (4147 ) და (10672 ) უდიდეს საერთო გამყოფს:

გაითვალისწინეთ, რომ [ დაიწყოს {გასწორება} 10672 & = & 4147 cdot 2 + 2378, 4147 & = & 2378 cdot 1 + 1769, 2378 & = & 1769 cdot 1 + 609, 1769 & = & 609 cdot 2 +551 , 609 & = & 551 cdot 1 + 58, 551 & = & 58 cdot 9+ 29, 58 & = & 29 cdot 2, დასრულება {გასწორება} ] მაშასადამე ((4147,10672) = 29. )

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

გამოხატეთ 29 როგორც (4147 ) და (10672 ) ხაზოვანი კომბინაცია:

[ დაიწყოს {გასწორება} 29 & = & 551-9 cdot 58, & = & 551-9 (609-551 cdot 1), & = & 10.551-9.609, & = & 10 cdot (1769-609 cdot 2) -9 cdot 609, & = & 10 cdot 1769-29 cdot 609, & = & 10 cdot 1769-29 (2378-1769 cdot 1), & = & 39 cdot 1769-29 cdot 2378, & = & 39 (4147-2378 cdot 1) -29 cdot 2378, & = & 39 cdot 4147-68 cdot 2378, & = & 39 cdot 4147-68 (10672-4147 cdot 2), & = & 175 cdot 4147-68 cdot 10672, დასრულება {გასწორებული} ]

შედეგად, ჩვენ ვხედავთ, რომ (29 = 175 cdot 4147-68 cdot 10672 ).

Სავარჯიშოები

  1. გამოიყენეთ ევკლიდეს ალგორითმი, რომ იპოვოთ უდიდესი საერთო გამყოფი 412 და 32 და გამოხატოთ ის ორი მთელი რიცხვის მიხედვით.
  2. გამოიყენეთ ევკლიდეს ალგორითმი, რომ იპოვოთ უდიდესი საერთო გამყოფი 780 და 150 და გამოხატოთ ის ორი მთელი რიცხვის მიხედვით.
  3. იპოვნეთ (70,98, 108 ) - ის უდიდესი საერთო გამყოფი.
  4. მოდით (a ) და (b ) ორი პოზიტიური კი მთელი რიცხვი იყოს. დაამტკიცეთ, რომ ((a, b) = 2 (a / 2, b / 2). )
  5. აჩვენეთ, რომ თუ (a ) და (b ) პოზიტიური მთელი რიცხვია, სადაც (a ) არის ლუწი და (b ) უცნაურია, მაშინ ((a, b) = (a / 2, b) . )

MAT 112 ძველი და თანამედროვე მათემატიკა

ჩვენ ვაყალიბებთ ალგორითმს უდიდესი საერთო გამყოფების გამოსათვლელად, რომელიც მიჰყვება სტრატეგიას, რომელიც ჩვენ გამოვიყენეთ მაგალითში 4.2.8. როგორც მაგალითში, ჩვენ განმეორებით ვიყენებთ თეორემას 4.2.7 3. 4 ( gcd (a, b) ) გამოთვლის შესამცირებლად ( gcd (a fmod b, b) ტექსტზე <.> ) ეს ამცირებს რიცხვებს, რომელთა გამოანგარიშებასაც ჩვენ ყველაზე დიდ საერთო გამყოფად ვთვლით თითოეულ ნაბიჯზე, სანამ დარჩენილი (a fmod b ) ნულოვანია.

ალგორითმს ეწოდა ბერძენი მათემატიკოსის ევკლიდეს სახელი, რომელმაც პირველად აღწერა ეს მისი მე -7 წიგნში ელემენტები (ძვ.წ. დაახლოებით 300 წელი) [5]. ალგორითმის წარმოდგენის გასამარტივებლად, მხოლოდ ბუნებრივ რიცხვებს (პოზიტიურ მთელ რიცხვებს) ვუშვებთ.

დიაგრამა 4.3.1-ში მოცემულ ვიდეოში ჩვენ წარმოგიდგენთ ალგორითმს და ვიყენებთ მას ყველაზე დიდი საერთო გამყოფების მოსაძებნად.

ჩვენ ვაყალიბებთ ევკლიდეს ალგორითმს ჩვენი ალგორითმის ფორმატში.

ალგორითმი 4.3.2. ევკლიდური ალგორითმი.

ორი ბუნებრივი რიცხვი (a ) და (b ) ერთად (a & gtb )

(A ) და (b ) ყველაზე დიდი საერთო გამყოფი ( gcd (a, b) )

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

მაგალითი 4.3.3. (612 ) და (56 ) უდიდესი საერთო გამყოფი.

ჩვენ ვანგარიშებთ (612 ) და (56 ) უდიდეს საერთო გამყოფს ალგორითმით 4.3.2.

როგორც (r = 52 ) განცხადება (r = 0 ) არასწორია. ასე რომ, ჩვენ გავაგრძელებთ პუნქტს 1 შემდეგით:

როგორც (r = 4 ) განცხადება (r = 0 ) არასწორია. ასე რომ, ჩვენ გავაგრძელებთ პუნქტს 1 შემდეგით:

როგორც (r = 0 ) განცხადება (r = 0 ) არასწორია. ასე რომ, ჩვენ გავაგრძელებთ 1 პუნქტს

ჩვენ ვაბრუნებთ (a ) მნიშვნელობას, რომელიც არის (4 ტექსტი <.> )

ჩვენ დავადგინეთ, რომ (612 ) და (56 ) უდიდესი საერთო გამყოფია (4 ტექსტი <.> )

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

მაგალითი 4.3.4. (612 ) და (56 ) კომპაქტის უდიდესი საერთო გამყოფი.

ჩვენ ვანგარიშებთ (612 ) და (56 ) უდიდეს საერთო გამყოფს ალგორითმით 4.3.2. ცხრილში მოცემულია ცვლადების მნიშვნელობები მარყუჟის თითოეულ გამეორებაში 1 ნაბიჯის ბოლოს.

ნაბიჯი (r ) (a ) (ბ )
შეყვანა (612) (56)
(1) (612 fmod 56 = 52 ) (56) (52)
(1) (56 fmod 52 = 4 ) (52) (4)
(1) (52 fmod 4 = 0 ) (4) (0)
გამომავალი 4

ამრიგად, გამომავალი არის ( gcd (612,56) = 4 ტექსტი <.> )

4.3.5 მაგალითის ინტერაქტიულ ალგორითმში დააჭირეთ ევკლიდეს ალგორითმის ნაბიჯებს, რათა ნახოთ თუ როგორ იცვლება ცვლადების მნიშვნელობები თითოეულ ნაბიჯზე.

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

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

გამშვები პუნქტი 4.3.6. ევკლიდური ალგორითმი.

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

თეორემა 4.3.7.

მოდით, იყოს () ბუნებრივი რიცხვი. შემდეგ ( gcd (n, n + 1) = 1 ტექსტი <.> )

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

მოდით, იყოს () ბუნებრივი რიცხვი. ჩვენ გამოვთვლით ( gcd (n + 1, n) ) ევკლიდეს ალგორითმის გამოყენებით. ალგორითმით 4.3.2. ცხრილში მოცემულია ცვლადების მნიშვნელობები მარყუჟის თითოეულ გამეორებაში (1) ნაბიჯის შემდეგ.

ნაბიჯი (r ) (a ) (ბ )
შეყვანა (n + 1 ) (n )
(1) ((n + 1) fmod n = 1 ) (n ) (1)
(1) (n fmod 1 = 0 ) (1) (0)
გამომავალი 1

ამრიგად, ( gcd (n + 1, n) = 1 ტექსტი <,> ) და დავასკვნათ, რომ (n + 1 ) და (n ) კოპირებაა.

თეორემის მტკიცებულებას ილუსტრირებას ვაძლევთ რიცხვითი მაგალითით.

მაგალითი 4.3.8. (238 ) და (237 ) არის საავტორო უფლებები.

ჩვენ ვანგარიშებთ (238 ) და (237 ) უდიდეს საერთო გამყოფს ალგორითმით 4.3.2. ცხრილში მოცემულია ცვლადების მნიშვნელობები მარყუჟის თითოეულ გამეორებაში (1) ნაბიჯის შემდეგ.

ნაბიჯი (r ) (a ) (ბ )
შეყვანა (238) (237)
(1) (238 fmod 237 = 1 ) (237) (1)
(1) (237 fmod 1 = 0 ) (1) (0)
გამომავალი (1)

ამრიგად, გამომავალი არის ( gcd (238,237) = 1 ტექსტი <.> )

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


პოლინომების ფესვების რიცხვითი მეთოდები, ნაწილი I

მაგალითი 1

აიღეთ f ˜ 2 = 1 4 p ˜ ′ და შეასრულეთ EA float-point არითმეტიკაში, გამოთვალეთ შეცდომის საზღვრები L.H.S. 2.37-დან როგორც ჩვენ მივდივართ. შედეგები არის

რადგან ჩვენს პოლინომს აქვს სიზუსტის დონე .5 × 10 −7, ჩვენ, როგორც ჩანს, გვაქვს gcd f f 3 ხარისხის 2.

თანმიმდევრობა P i = g c d (p i - 1, p ′ i - 1), რომელიც აღწერილია მე –4 ნაწილში, ახლა შეიცვლება

სადაც α-gcd ვგულისხმობთ უახლოეს gcd- ს α სიზუსტის დონეზე.

ჰრიბერნიგი გვიჩვენებს, რომ ”For | ζ | & lt 1, თუ (x - ζ) –1 არის α g და p ˜ an α-gcd ფაქტორი , შემდეგ p ˜-ს აქვს ნულოვანი კ-კასეტური ζ ζ სიზუსტის დონეზე 3α ”

დავუშვათ, რომ 2.41-ის გამოყენების შემდეგ და შემდგომი გამოთვლის შემდეგ Q და Q ˜ j როგორც მე -4 წამში გვაქვს

და შეამოწმეთ r ˜ j ზომა . თუ ‖ r ˜ j ‖ ≈ α, (j = 1,…, მ), მაშინ ჩვენ ვიღებთ 2.42-ს p z 1-ის ნულების მართებულ დაჯგუფებად მტევანებად სიზუსტის დონეზე α. მაგრამ თუ ‖ r ˜ j ‖ & gt & gt (& lt & lt) α ძალიან ცოტა (ძალიან ბევრი) მტევანი გვაქვს და უნდა შევამციროთ (ავწიოთ) ხარისხი P ˜ l , ანუ ჩვენ უნდა გადავდოთ მინიმუმ ერთი ნაბიჯით მეტი (ნაკლები) სტაბილიზირებულ EA– ში, რომელიც წარმოქმნის P ˜ l

როგორც სტანდარტული პროცედურა, იმ შემთხვევაში, თუ ზოგიერთ Q ˜ ს აქვს ხარისხი & gt 1, მათი სავარაუდო ნულები უნდა მოიძებნოს როგორც რამდენიმე i- კლასტერის ცენტრი, რომელსაც ისინი წარმოადგენენ. ეს ნულები კარგად იქნება გამიჯნული განსაზღვრული სიზუსტის დონეზე (წინააღმდეგ შემთხვევაში, ისინი ჩაითვლება როგორც ერთი კლასტერი), და მათი პოვნა შედარებით მარტივი უნდა იყოს.


პრეტენზია მცდარია, თუ $ K $ არ არის ველი:

აიღეთ $ P = 2 $ და $ Q = 2X $ $ mathbb Z [X] $ - ში. თუ $ AP + BQ = 1 $, მაშინ $ 2A (0) = 1 $, რაც არ შეიძლება მოხდეს $ mathbb Z $.

პრეტენზია მცდარია, თუ $ K $ არ არის ალგებრულად დახურული ველი:

აიღეთ $ P = X ^ 2 + 1 $ და $ Q = X (X ^ 2 + 1) $ $ mathbb R [X] $. თუ $ AP + BQ = 1 $ მაშინ $ (A + BX) (X ^ 2 + 1) = 1 $, რაც არ შეიძლება მოხდეს $ mathbb R [X] $ - ში, რადგან $ X ^ 2 + 1 $ არ არის ერთეული .

პრეტენზია მართალია, თუ $ K $ არის ალგებრული ნიშნით დახურული ველი.

ამ შემთხვევაში $ P $ და $ Q $ საერთო ფესვები არ აქვთ iff $ gcd (P, Q) = 1 $, რადგან $ K [X] $ - ში შეუმცირებელი რიცხვები ზუსტად $ 1 $ -ის პოლინომია, როდესაც $ K $ ალგებრულად დახურული ველია. შემდეგ პრეტენზია გამომდინარეობს გაფართოებული ევკლიდეს ალგორითმიდან.


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

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

ჯოზეფ მალკევიჩი
მათემატიკისა და კომპიუტერული სწავლების განყოფილება
იორკის კოლეჯი (CUNY)
იამაიკა, ნიუ იორკი 11451


თუ d არის ორი (პოზიტიური) a და b მთელი რიცხვების უდიდესი საერთო გამყოფი, მაშინ d დაყოფს დარჩენილ r- ს, რომელიც a და b- ს უფრო მცირეზე უფრო დიდზე დაყოფის შედეგია.

24 და 16-ის უდიდესი საერთო გამყოფი არის 8.

24 = 1 (16) + 8. მაშასადამე, დანარჩენი, როდესაც 24 იყოფა 16-ზე, არის 8, რომელიც იყოფა 8-ზე.

100 და 60-ის უდიდესი საერთო გამყოფი არის 20.

100 = 1 (60) + 40. დანარჩენი 40, იყოფა 20-ზე.

ზემოთ მოყვანილი ფაქტი წარმოადგენს ევკლიდეს ალგორითმის სახელწოდების საფუძველს ორი რიცხვის უდიდესი საერთო გამყოფი პოვნისთვის. ალგორითმს ეწოდა იგივე მათემატიკოსი ევკლიდე, რომელიც ცნობილია გეომეტრიაში მუშაობით. ამ ალგორითმის ხიბლი იმაშია, რომ იგი ვერ პოულობს უდიდეს საერთო გამყოფს ფაქტორიზაციის მნიშვნელობად პირველ რიგში. დიდი რაოდენობის ფაქტორიზაცია, როგორც ჩანს, ძალიან მძიმე პრობლემაა. ამჟამად ცნობილი არ არის, თუ რა არის ფაქტორინგის ზუსტი გამოთვლითი სირთულე, მაგრამ ერთ – ერთი ყველაზე ხშირად გამოყენებული კრიპტოგრაფიული ალგორითმი (მაგ. RSA, კომპიუტერული მეცნიერების სახელით რონალდ რივესტი, ადი შამირი და ლეონარდ ადელმანი, რომლებმაც შეიმუშავეს 1978 წელს გამოქვეყნებული მეთოდი სანამ ისინი იყვნენ MIT– ის სტუდენტები) მისი უსაფრთხოება დამოკიდებულია იმაზე, რომ დიდი რაოდენობით ფაქტორირება ძალიან რთულია.

მოცემულია a და b, გაყოფა პატარა და უფრო დიდი და მიიღე კოეფიციენტი q და ნარჩენი r.

ვთქვათ, b უფრო დიდია, ვიდრე a გვაქვს:

b = q (a) + r. ახლა b- სა და a- ს უდიდესი საერთო გამყოფი იგივეა, რაც a და r- ის უდიდესი საერთო გამყოფი.

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

იპოვნეთ 36 – ის და 10 – ის უდიდესი საერთო გამყოფი.

ნულოვანი უკანასკნელი დარჩენილია 2, და შესაბამისად, 10 და 36-ის უდიდესი საერთო გამყოფი არის 2.

თუ d არის a და b– ის უდიდესი საერთო გამყოფი, d შეიძლება დაიწეროს სახით:


სადაც x და y არის მთელი რიცხვი.

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

ზოგიერთ x და y რიცხვებზე.

მოდით ვიპოვოთ მნიშვნელობები x და y მაგალითისთვის 3. ამ მაგალითში ვნახეთ, რომ 36 და 10 – ის უდიდესი საერთო გამყოფი არის 2.


(4) განტოლებიდან ვხედავთ, რომ 36-ის და 10-ის უდიდესი საერთო გამყოფი არის 2 და ეს:

(3) განტოლებიდან ვიცით, რომ 4 = 1 (10) - 1 (6), ასე რომ, ჩვენ შეგვიძლია შევცვალოთ 4 მნიშვნელობა განტოლებაში (5) 1 (10) - 1 (6) -ით, რომ მივიღოთ:

2 = (1)(6) - 1 (1(10) - 1(6)) = (1)(6) -1(10) + 1(6) = 2(6) - 1 (10). (6)

(2) განტოლებიდან ვიცით, რომ 6 = 1 (36) - 3 (10), ასე რომ, ჩვენ შეგვიძლია შეცვალოთ 6 მნიშვნელობა განტოლებაში (6) 1-ით (36) - 3 (10), რომ მივიღოთ:

2 = 2(1(36) - 3(10)) -1(10) = 2(36) - 6(10) - 1(10) = 2(36) - 7(10).

ამრიგად, x- ის მნიშვნელობები, რომელსაც ჩვენ ვეძებთ არის 2, ხოლო y- ის მნიშვნელობა არის -7, და საკმარისია, ამ მნიშვნელობებით გვაქვს 2 = 36x + 10y.

ორი მთელი რიცხვის gcd- ის საპოვნელად გამოყენებული ნაბიჯებით უკან თვალის მიდევნების ეს მეთოდი ყოველთვის შეიძლება გამოყენებულ იქნას 1 და თეორემაში x და y მთელი რიცხვების მნიშვნელობების დასადგენად.

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

ვთქვათ, რომ a და p შედარებით პირველყოფილია, ჩვენ შეგვიძლია ვიპოვოთ ორი მთელი s და t ისეთი, რომ + pt = 1. თუ ამ შესაბამისობის მოდულს ვიღებთ, გვაქვს შემდეგი:

ამრიგად, თუ x დავაყენეთ bs მნიშვნელობას, x -ისთვის ვიპოვნეთ მნიშვნელობა, რომელიც ხსნის ზემოთ შესაბამისობას (*).

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

დავუშვათ, ვინმეს სურს გადაჭრას კონგრესმენობა:

როგორც პირველი ნაბიჯი, ევკლიდეს ალგორითმის გამოყენებით იპოვნეთ 23-ე და 11-ე უდიდესი უდიდესი გამყოფი:

11 = 1 (11) + 0, ასე რომ, gcd არის 1.

ზემოთ მოცემული განტოლებიდან ვხედავთ, რომ 1 = (1) (23) + (-2) 11. Modulo 23 ამ განტოლებებით მოცემულია (-2) (11) & # 8801 1 mod 23. ამრიგად, x = -2 ხსნის შესაბამისობას. მას შემდეგ, რაც გვსურს პასუხის დაწერა 0-დან 22-ის მნიშვნელობით შევძლოთ, ვხედავთ, რომ -2 & # 8801 21 mod 23, ამიტომ x = 21 არის გამოსავალი.

ახლა გაითვალისწინეთ შესაბამისობა:

როგორც პირველი ნაბიჯი, ჩვენ მოვაგვარებთ შესაბამისობას: 16x & # 8801 1 mod 29

ასე რომ, შეგვიძლია დავწეროთ, რომ 1 = 1 (13) + (-4) (3).

ამ განტოლების ჩანაცვლება იმ ფაქტის გამოყენებით, რომ (3), 3 = 16 -1 (13) –დან მივიღებთ:

1 = 1(13) + (-4)(16-1(13)) = 5(13) + (-4)(16) (5)

ახლა (2) -ის გამოყენებით (საიდანაც ვიცით, რომ 13 = 29 -1 (16)) შეგვიძლია ჩავანაცვლოთ 13-ში (5):

ეს ბოლო განტოლების მოდული 29 იძლევა:

X- ის მნიშვნელობა, რომელიც ჩვენ ვეძებთ არის -9, რომელიც არის შესატყვისი მოდული 29-დან 20-მდე.

მას შემდეგ, რაც ახლა ვიცით, რომ 16 (20) არის 1 მოდულის 29 თანხვედრა, შეგვიძლია გავამრავლოთ ამ თანხვედრის ორივე მხარე 5-ზე, რომ მივიღოთ, რომ 100 (16) არის 5 მოდულის 29-სთან შესაბამისობა. 13 არის იმ კონგრუენტის გადაწყვეტა, რომლის გადაწყვეტაც გვინდოდა:

თქვენ უნდა დაადასტუროთ, რომ 16 (13) - 5 ნამდვილად ტოვებს ნულის ნარჩენს, როდესაც გაყოფილია 29-ზე.

ზემოთ მოცემული მეთოდების გაფართოება შესაძლებელია იმ კონგრუენციების გადასაჭრელად, სადაც p ასევე არაა პრემიერი. მთავარ მოდულთან მუშაობის უპირატესობა ის არის, რომ სანამ in (*) არ არის p- ს ჯერადი, ჩვენ ყოველთვის შეგვიძლია ვიპოვოთ კონგრუენციის უნიკალური გამოსავალი x მნიშვნელობით, რომელსაც აქვს მნიშვნელობა 0-დან (p-1) .


მათემატიკის 321 კლასის შენიშვნები

შემდეგ ( gcd (a, b) = r_n text <,> ) ბოლო ნულოვანი ნარჩენი.

მაგალითი 3.3.7.

აქ მოცემულია სრულად შემუშავებული მაგალითი, რომელიც აჩვენებს თუ როგორ უნდა აწარმოოთ ალგორითმი ( gcd (7592, 5913)

ევკლიდეს ალგორითმის მიხედვით, უკანასკნელი არა ნულოვანი ნაშთი არის gcd და ა.შ. ( gcd (7592, 5913) = 73 ტექსტი <.> )

მაგალითი 3.3.8.
წინადადება 3.3.9. ბეზუტის ლემა.

თუ (a და b ) დადებითი მთელი რიცხვია, მაშინ არსებობს მთელი რიცხვები (s და t ) ისეთი, რომ (< gcd (a, b) = as + bt> )

განმარტება 3.3.10.

ჩვენ ვუწოდებთ (s და t ) თეორემაში ზემოთ მოცემულ თეორემაში (a და b text <.> )

მაგალითი 3.3.11. უკანა ქვესათაური.

ევკლიდეს ალგორითმის შეცვლა შეგვიძლია, რომ ვიპოვოთ Bézout კოეფიციენტები, პროცესს რომელსაც ჩვენ დავარქმევთ. ჩვენ გადავწყვეტთ თითოეულ განტოლებას ევკლიდეს ალგორითმში დანარჩენი ნაწილისთვის და განმეორებით ჩავანაცვლებთ და გავაერთიანებთ მსგავს ტერმინებს მანამ, სანამ არ მივაღწევთ ორიგინალ ორი რიცხვის როგორც gcd- ს, ამ შემთხვევაში, (73 = 7592s + 5913t )

ჩანაცვლება და მსგავსი ტერმინების შერწყმა:

მაგალითი 3.3.12.

გამოხატეთ 168 და 525 gcd, როგორც ამ რიცხვების წრფივი კომბინაცია.

მაგალითი 3.3.13.
  1. გამოიყენეთ ევკლიდეს ალგორითმი ( gcd (4147, 10672) ტექსტის მოსაძებნად. <.> )
  2. გამოიყენეთ უკანა ჩანაცვლება (ევკლიდეს ალგორითმის ნაბიჯების გადახედვა) 4147 და 10672 – ის უდიდესი საერთო გამყოფი დასაწერად, როგორც ამ რიცხვების წრფივი კომბინაცია.

სავარჯიშოები 3.3.1 სავარჯიშოები

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

  1. ( displaystyle gcd (36, 48) )
  2. ( displaystyle gcd (21, 724) )
  3. ( displaystyle gcd (60, 97) )
  4. ( displaystyle gcd (5, 26) )

გამოიყენეთ ნებისმიერი მეთოდი, რომ იპოვოთ 412 და 32-ის უდიდესი საერთო გამყოფი.

( gcd (412, 32) = 4 ტექსტი <.> ) ჩვენ შეგვიძლია მისი სწორხაზოვანი კომბინაციით შევასწოროთ: (4 = 412 (-1) + 32 (13) )

გამოიყენეთ ნებისმიერი მეთოდი 780 და 150 – ზე უდიდესი საერთო გამყოფი იპოვოთ.

( gcd (780, 150) = 30 text <.> ) gcd შეგვიძლია მოვაწესრიგოთ როგორც ხაზოვანი კომბინაცია (30 = 780 (1) + 150 (-5) )


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

. .

გადაჭრით მეორედან ბოლო განტოლების გამოყენებით და მივიღებთ:

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

ეკვ 4         

ახლა მოდით გადავწყვიტოთ იგივენაირად:

ეკვ 5         

შემცვლელი ეკვ 5 შევიდა ეკვ 4 :

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


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


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

ჩამოტვირთეთ ვიდეო iTunes U ან ინტერნეტ არქივიდან.

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

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

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

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

დარჩენილი ლემა ახლა მშვენივრად გვაძლევს GCD– ს გამოთვლას. და აი მაგალითი. დავუშვათ, რომ მინდა გამოთვალოს GCD 899 და 493. A არის 899, b არის 493. ისე, ასე რომ, მინდა ეს GCD, 899 493. ასე რომ, დანარჩენი ლემას მიხედვით, თუ 899 გავყოფ 493-ზე, მივიღებ 1-ის კოეფიციენტი, ხოლო დანარჩენი 406. ასე რომ, ეს ნიშნავს, რომ 899 და 493 აქვს იგივე GCD, როგორც 493 და 406. ეს არის თავდაპირველი რიცხვი b, ხოლო ახალი ნაშთი 406.

ახლა მე შემიძლია 493 გავყო 406-ზე. მივიღებ ნულის კოეფიციენტს, ხოლო დანარჩენს 87. ასე რომ, 406 და 87 აქვს იგივე GCD. 406-ის გაყოფაზე 87-ზე მე ვხვდები, რომ 87-სა და 58-ს აქვს იგივე GCD. 87-ის გაყოფა 58-ზე, მივიღებ რომ 58 და 29 აქვს იგივე GCD. ახლა კი გავიმარჯვებ, რადგან შეხედე, როცა 58-ს გავყოფ 29-ზე, მივიღებ ნარჩენის 0.-ს და GCD ნებისმიერი და 0 არის ეს. 29 და 0 GCD არის 0. ვფიქრობ, ერთადერთი გამონაკლისი არის 0 და 0 GCD, რომელიც არ არის განსაზღვრული. თუ ეს არ არის 0, მაშინ x და 0 GCD არის x.

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

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

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

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

სხვა სიტყვებით რომ ვთქვათ, ეს განტოლება, x და y GCD ამჟამინდელ მდგომარეობაში ტოლია a და b GCD, a და b GCD, რომლითაც ჩვენ დავიწყეთ, არის შენარჩუნებული მდგომარეობის ინვარიანტი. Xy მდგომარეობის p, თვისება, რომლის x და y GCD არის ორიგინალი GCD, არის შენარჩუნებული სახელმწიფო მანქანის ინვარიანტი. უფრო მეტიც, p დაწყება ტრივიალურად არის მართალი, რადგან დასაწყისში, x და y ტოლია b. X და y p უბრალოდ ვამბობთ, რომ a და b GCD ტოლია a და b GCD.

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

აბა, რატომ არის ეს? შეხედეთ შეწყვეტას, რაც ვიცით y არის 0. ამ პროცედურის გაჩერების ერთადერთი გზაა, რადგან წინააღმდეგ შემთხვევაში, გარდამავალი წესი გამოიყენება. ეს ნიშნავს, რომ როდესაც y უდრის 0 – ს შეწყვეტისას, ჩვენ გვაქვს ის, რომ რადგან y არის 0, x და y GCD ტოლია x და 0. GCD და ეს უდრის x –ს, თუ ჩავთვლით, რომ x არის დადებითი , ან არა 0.z

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

გაითვალისწინეთ, რომ ყოველი გადასვლისას, ჩვენ x- ს ვიცვლით y- ით, ხოლო y- ზე დარჩენილი x -ით გაყოფილი y- ზე. მოდით, უბრალოდ ჩავთვალოთ, რომ [? დაწყვილებები,?] y რომ x უფრო დიდია. ამრიგად, არსებობს ორი შემთხვევა, თუ რატომ ხდება ეს რიცხვების სწრაფად პატარება. პირველი შემთხვევა არის ვარაუდი, რომ y ნაკლებია x– ზე 2 – ზე, ან ნაკლებია ან ტოლია x– ზე 2 – ზე, რადგან ამ ეტაპზე x– ს შეცვლით y– ით, ეს ნიშნავს რომ შეცვლით x– ს რაღაც ნახევარზე ნაკლები x. ამ ეტაპზე x განახევრდება.

თუ y დიდია? კარგია, თუ y მეტია x– ზე 2 – ზე, მაშინ x დარჩენილი ნაწილი გაყოფილი y –ზე არის x გამოკლებული y. ეს იქნება x– ზე ნაკლები 2 – ზე. მაგრამ ეს იქნება y– ის მნიშვნელობა შემდეგი ნაბიჯის შემდეგ. ასე რომ, y განახევრდება ან ამ ეტაპზე, ან შემდეგ ეტაპზე, როდესაც ის შეიცვლება x და y დარჩენილით. წმინდა შედეგია ის, რომ y ის იჭრება შუაზე, ან კიდევ უფრო მცირე, ყოველ მეორე ეტაპზე, რაც ნიშნავს, რომ ეს პროცედურა ვერ გაგრძელდება ორჯერ მეტი შესვლისას, ვიდრე y საწყისი საწყისი მნიშვნელობის 2 ფუძისა, რაც არის b ნაბიჯების რაოდენობა, რადგან ამდენი ნაწილის გაკეთება შეგიძლიათ 0-ზე დარტყმის დაწყებამდე.

ჩვენ ახლახანს ვაჩვენეთ, რომ ეს პროცედურა იკავებს ლოგარითმული ნაბიჯების რაოდენობას, რაც იგივეა, რომ თქვა, რომ ეს არის b სიგრძის ორობითი და კიდევ უფრო ნაკლები ნაბიჯები, ვიდრე b სიგრძის ათობითი. GCD ალგორითმი მართლაც ძალიან ეფექტურია.


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

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

ფინალურ ეტაპზე, როდესაც r = 0, ვხედავთ, რომ "საბოლოო b" - მ უნდა გაყო a საბოლოო. გადადით უკან განტოლებების სიმების გასწვრივ (a = q& middotb + r), და ნახავთ, რომ თითოეულ ნაბიჯზე "საბოლოო b" ყოფს განტოლების თითოეულ ნაწილს. ამიტომ "საბოლოო b" უნდა იყოს a და b საწყისი საწყისი დაყოფა.

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

  • 210 გაყავით 45-ზე და მიიღეთ შედეგი 4 დარჩენილი 30-ით, ასე რომ 210 = 4& middot45+30.
    30=1& middot210-4& middot45.
  • 45 გაყო 30-ზე და მიიღე შედეგი 1 დარჩენილი 15-ით, ასე რომ 45 = 1& middot30+15.
    15=45-1& middot30 = 45-1 & საშუალო(1& middot210-4& middot45)=-1& middot210+5& middot45

ევკლიდეს გაფართოებულ ალგორითმს ძალიან მნიშვნელოვანი გამოყენება აქვს: მულტიპლიკაციური ინვერსიების პოვნა mod mod. აარჩიეთ მარტივი, P: 97-ზე. მე ვიცი 97 არის მარტივი, რადგან 2 და 3 და 5 და 7 და 11ც კი არ არის 97-ის ფაქტორი, და მე მხოლოდ პრომენების მიხედვით უნდა დავამოწმო დაყოფა 97 კვადრატულ ფესვამდე.

  • 97=4& middot20+17
  • 20=1& middot17+3
  • 17=5& middot3+2
  • 3=1& middot2+1
  • 17=1& middot97-4& middot20
  • 20-1& middot17 = 3 ასე 3 =1& middot20-1& middot17=1& middot20-(1& middot97-4& middot20)= -1& middot97+5& middot20
  • 17=5& middot3 + 2 ისე 2 =17-5& middot3=(1& middot97-4& middot20)-5(-1& middot97+5& middot20)= 6& middot97-29& middot20
  • 1 =3-2=(-1& middot97+5& middot20)-(6& middot97-29& middot20)= -7& middot97+34& middot20

ვარჯიში
იპოვნეთ 60 mod 97-ის გამრავლების ინვერსია ხელით. როგორც კლასში აღვნიშნე, ამ გამოთვლების მხოლოდ ერთის გაკეთება "ხელით" საკმარისია. აქ მოცემულია პასუხის ბმული.

გაფართოებული ევკლიდეს ალგორითმი მარტივად ხორციელდება კომპიუტერზე და საჭირო მეხსიერების რაოდენობა არ არის დიდი. ალგორითმი მუშაობს ძალიან სწრაფი. მაგალითად, მე ახლა ვაწარმოებ ასლის ასლს ნეკერჩხალი კომპიუტერში სხვა ფანჯარაში, რომელიც არც ძალიან სწრაფია და არც ბევრი მეხსიერება აქვს. მე ახლახანს ავირჩიე 100 ათობითი ციფრი, P და აღმოვაჩინე 50 ათობითი რიცხვის mod P.- ის გამრავლების ინვერსია. სისტემა დააბრუნა 0.00, როგორც გამოყენებული დროის რაოდენობა. ეს გამოთვლა გამოყენებულია 0,01 წამზე ნაკლებ დროზე!


Უყურე ვიდეოს: პროგრამული უზრუნველყოფის ინჟინერია, ლექცია 3 (დეკემბერი 2021).