• Introduceți conceptul de „algoritmul lui Euclid”.
• Pentru a învăța cum să găsiți cei mai obișnuiți divizori în diferite moduri matematice.

În timpul orelor

Conceptul de algoritm al lui Euclid

Este unul dintre cei mai vechi matematicieni, care are peste 2000 de ani.

Algoritmul lui Euclid este inventat pentru a găsi cel mai mare factor comun perechi de numere întregi.

Cel mai mare divizor comun

Cel mai mare divizor comun(GCD) este un număr care împarte două numere fără rest și poate fi împărțit fără rest la orice alt divizor al acestor numere.

Cu alte cuvinte, acesta este cel mai mare număr cu care cele două numere, pentru care se caută divizorul comun, pot fi împărțite fără rest.

Algoritm pentru găsirea GCD prin diviziune

Descrierea algoritmului de găsire a celui mai mare divizor comun prin diviziune

Numărul mai mare se împarte la cel mai mic

Dacă este divizibil fără rest, atunci numărul mai mic este cel mai mare divizor comun. Acum trebuie să ieși din ciclu

Dacă există un rest, atunci înlocuiți numărul mai mare cu restul diviziunii

Treci la punctul 1.

Exemplu:

Găsiți cel mai mare coeficient comun de 300 și 180.

300/180 = 1 (restul 120)

180/120 = 1 (restul 60)

120/60 = 2 (restul 0).

Sfârșit: cel mai mare factor comun este 6.

V ciclu„A” sau „b” este restul diviziunii. Când nu există rest (nu știm în „a” el sau „b”, așa că le verificăm pe amândouă conditii), apoi ciclul se termină.

La final este afișată suma lui „a” și „b”, deoarece nu știm în ce variabilă se scrie cel mai mare divizor comun, iar într-una dintre ele, în orice caz, 0, ceea ce nu afectează rezultatul. a sumei.

Algoritm pentru găsirea GCD prin scădere

Descrierea algoritmului de găsire a celui mai mare divizor comun prin scădere

Numărul mai mic se scade din numărul mai mare.

Dacă rezultatul este 0, atunci numerele sunt egale între ele și sunt cel mai mare divizor comun. Ieșirea din buclă

Dacă rezultatul scăderii nu este 0, atunci numărul mai mare este înlocuit cu rezultatul scăderii

Treci la punctul 1.

Exemplu: Găsiți numerele 300 și 180.

Sfârșit: Cel mai comun divizor al 300 și 180 este 60.

Ca o modalitate de a găsi cea mai mare măsură comună a două segmente (metoda scăderii alternante) era cunoscută pitagoreenilor.

Găsirea celei mai mari măsurători comune a două segmente procedați în același mod ca mai sus.

Diviziunea rămasă este înlocuită cu omologul său geometric: mai mic secțiune așezați de cât mai multe ori posibil, iar restul segmentului mai mare (și acesta este restul diviziunii) este așezat pe un segment mai mic.

Dacă segmentele Ași b proporțional, atunci ultimul rest diferit de zero va oferi cea mai mare măsură totală a segmentelor.

Dacă sunt incomensurabile, secvența rezultată de reziduuri diferite de zero va fi infinită.

Exemplu:

Ca segmente luăm latura AB și AC a triunghiului isoscel ABC, în care A = C = 72 °, B = 36 °.

Ca prim rest, obținem segmentul AD (CD-bisectoarea unghiului C) și, după cum este ușor de observat, succesiunea de reziduuri zero va fi infinită.

Aceasta înseamnă că segmentele AB și AC nu sunt comensurabile.

Întrebări

1. Ce este algoritmul lui Euclid?

2. Care este cel mai mare factor comun?

Lista surselor utilizate

1. Lecție pe tema: „Algoritmul lui Euclid”, P. I. Korchevoy, Lutsk

2. Shchetnikov AI Algoritm euclidian și fracții continue. - Novosibirsk: ANT, 2003

3. Kountinho S. Introducere în teoria numerelor. Algoritmul RSA, - M., 2001

4. Kostrikin A.I. Introducere în algebră, - M., 2000

Editat și trimis de profesor Universitatea Națională din Kiev. Taras Şevcenko Soloviev M.S.

A lucrat la lecție

Korchevoy P.I.

Soloviev M.S.

Pune o întrebare despre învăţământul modern, exprimați o idee sau rezolvați o problemă urgentă, puteți la Forum educațional

Algoritmul lui Euclid este o modalitate de a găsi cel mai mare divizor comun (MCD) a două numere întregi. Versiunea originală a algoritmului, când GCD este găsit prin scădere, a fost descoperită de Euclid (sec. III î.Hr.). În zilele noastre, diviziunea este folosită mai des atunci când se calculează GCD prin algoritmul euclidian, deoarece această metodă este mai eficientă.

Calcularea mcd prin diviziune

Cel mai mare divizor comun al unei perechi de numere este cel mai mare număr care împarte integral ambele numere din pereche. Să fie necesar să se calculeze GCD pentru numerele 108 și 72. Algoritmul pentru calcularea diviziunii va fi următorul:

1. Împărțiți numărul mai mare (dividend) la cel mai mic (divizor): 108/72 = 1, restul este 36.
2. Deoarece restul nu a fost egal cu zero, vom face divizorul divizibil, iar restul - divizor: 72/36 = 2, restul este 0.
3. Când restul este zero, atunci divizorul este GCD dorit pentru o pereche de numere date. Adică, GCD (108, 72) = 36. Într-adevăr, 108/36 = 3 și 72/36 = 2.

În acest algoritm împărțirea se repetă până când restul este zero... Când devine asta, GCD este divizorul ultimei diviziuni... De exemplu, trebuie să găsiți GCD (106, 16):

1. 106/16 = 6, restul 10
2. 16/10 = 1, restul 6
3. 10/6 = 1, restul 4
4. 6/4 = 1, restul 2
5. 4/2 = 2, restul 0
6. GCD (106, 16) = 2

Calcularea mcd prin scădere

Când găsiți GCD prin scădere, este necesar să ajungeți la zero. Algoritmul este similar cu metoda împărțirii, doar că aici la fiecare pas următor se scad scăderea și scăderea și diferența față de pasul precedent. În acest caz, numărul mai mic este întotdeauna scăzut din numărul mai mare. Acest tip de algoritm este potrivit doar pentru numere întregi pozitive.

Să fie necesar să se găsească GCD (108, 72):

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

Găsiți 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

Acest algoritm este uneori descris diferit. Scăderea se termină mai devreme, într-un pas în care un număr îl împarte pe celălalt. Adică combină scăderea cu testarea divizibilității. Apoi găsirea GCD pentru 44 și 60 va arăta astfel:

1. 44 împarte 60 complet? Nu. 60 - 44 = 16.
2. 16 împarte complet 44? Nu. 44 - 16 = 28.
3. 16 împarte 28 în total? Nu. 28 - 16 = 12.
4. 12 împarte egal 16? Nu. 16 - 12 = 4.
5. 4 împarte egal 12? Da. Prin urmare, GCD (44, 60) = 4.

Notă, GCD nu este câtul, ci divizorul... Dacă în exemplu împărțim 12 la 4, obținem câtul 3. Dar acesta nu este un GCD.

Dovada algoritmului lui Euclid

Să luăm în considerare faptul că, dacă un număr natural dintr-o pereche îl împarte complet pe celălalt, atunci GCD-ul lor va fi egal cu cel mai mic dintre ele. O poti scrie asa:

dacă a / b este întreg, atunci mcd (a, b) = b. De exemplu, GCD (15, 5) = 5.

Astfel, dacă în final ajungem la o pereche de numere, dintre care unul îl împarte complet pe celălalt, atunci cel mai mic va fi cel mai mare divizor comun pentru ambele. Este o astfel de pereche de numere pe care o caută algoritmul lui Euclid: un număr îl împarte pe celălalt.

Al doilea fapt. Este necesar să se demonstreze că, dacă un număr este mai mare decât celălalt, atunci cel mai mare divizor comun al lor este egal cu cel mai mare divizor comun pentru numărul mai mic al perechii și diferența dintre numerele mai mari și mai mici. Se poate scrie asa:

în cazul în care o< b, то НОД(a, b) = НОД(a, b - a).

Puteți demonstra că GCD (a, b) = GCD (a, b - a) după cum urmează. Fie b - a = c. Dacă orice număr x întreg împarte a și b, atunci va fi, de asemenea, întreg c. La urma urmei, dacă a și b sunt diferiți, atunci divizorul este un număr întreg, dar de un număr diferit de ori. Și dacă scădeți unul din celălalt, atunci divizorul trebuie să se potrivească și de un număr întreg de ori în diferența rezultată.

Dacă scădem în mod constant a și b, atunci mai devreme sau mai târziu vom ajunge la o astfel de valoare a celei mai mici dintre ele, care împarte complet pe cea mai mare. Cel mai mic dintr-o astfel de pereche va fi cel mai mare divizor comun pentru perechea originală numere naturale... Despre asta se referă algoritmul lui Euclid.

Algoritmul lui Euclid pentru găsirea GCD (cel mai mare divizor comun)

Sunt date două numere întregi nenegative și. Este necesar să se găsească cel mai mare divizor comun al acestora, de ex. cel mai mare număr care este un divizor al ambelor și, și. Pe limba engleză„cel mai mare divizor comun” se scrie „cel mai mare divizor comun”, iar desemnarea sa comună este:

(aici simbolul "" denotă divizibilitate, adică "" înseamnă "împarte")

Când unul dintre numere este egal cu zero, iar celălalt este diferit de zero, cel mai mare divizor comun al lor, conform definiției, va fi acest al doilea număr. Când ambele numere sunt zero, rezultatul este nedefinit (orice număr infinit de mare va face), setăm cel mai mare divizor comun la zero în acest caz. Prin urmare, putem vorbi despre o astfel de regulă: dacă unul dintre numere este egal cu zero, atunci cel mai mare divizor comun al lor este egal cu al doilea număr.

Algoritmul lui Euclid, considerată mai jos, rezolvă problema găsirii celui mai mare divizor comun a două numere și pentru.

Acest algoritm a fost descris pentru prima dată în cartea lui Euclid „Începuturi” (aproximativ 300 î.Hr.), deși, foarte probabil, acest algoritm are o origine anterioară.

Algoritm

Algoritmul în sine este extrem de simplu și este descris prin următoarea formulă:

Implementarea

int mcd (int a, int b) (dacă (b == 0) returnează a; altfel returnează mcd (b, a% b);)

Folosind operatorul condițional ternar C++, algoritmul poate fi scris și mai scurt:

int gcd (int a, int b) (întoarce b? gcd (b, a% b): a;)

În cele din urmă, iată o formă nerecursivă a algoritmului:

int gcd (int a, int b) (în timp ce (b) (a% = b; swap (a, b);) return a;)

Dovada corectitudinii

În primul rând, rețineți că cu fiecare iterație a algoritmului euclidian, al doilea argument al său scade strict, prin urmare, deoarece este nenegativ, algoritmul euclidian se termină întotdeauna.

Pentru dovada corectitudinii trebuie să arătăm asta pentru orice>.

Să arătăm că valoarea din stânga egalității este divizibilă cu valoarea reală din dreapta, iar valoarea din dreapta este divizibilă cu valoarea din stânga. Evident, aceasta va însemna că părțile stânga și dreapta coincid, ceea ce va dovedi corectitudinea algoritmului lui Euclid.

Notăm ... Apoi, prin definiție, și.

Dar apoi de aici rezultă:

Deci, amintindu-ne afirmația, obținem sistemul:

Să folosim acum următorul fapt simplu: dacă pentru vreo trei numere: și este satisfăcut, atunci și: este adevărat. În situația noastră, obținem:

Sau, înlocuind definiția sa ca în schimb, obținem:

Deci, am realizat jumătate din demonstrație: am arătat că partea stângă o împarte pe cea dreaptă. A doua jumătate a dovezii este similară.

Ore de lucru

Timpul de rulare al algoritmului este estimat teorema lui Lamé, care stabilește o legătură uimitoare între algoritmul euclidian și succesiunea Fibonacci:

Dacă> și pentru unii, atunci algoritmul lui Euclid va efectua cel mult apeluri recursive.

Folosit pe scară largă în comerțul electronic. De asemenea, algoritmul este utilizat pentru a rezolva ecuații liniare diofantine, la construirea fracțiilor continue, în metoda Sturm. Algoritmul lui Euclid este instrumentul principal pentru demonstrarea teoremelor în teoria numerelor moderne, cum ar fi teorema lui Lagrange asupra sumei a patru pătrate și teorema principală a aritmeticii.

YouTube colegial

1 / 5

✪ Matematică. Numerele naturale: algoritmul lui Euclid. Centrul de învățare online Foxford

✪ Algoritmul lui Euclid

✪ Algoritmul lui Euclid, cale rapidă găsi gcd

✪ Matematică 71. Cel mai mare divizor comun. Algoritmul lui Euclid - Academia de Științe Divertisment

✪ 20 Algoritmul While Loop Euclidean Python

Subtitrări

Istorie

Matematicienii greci antici au numit acest algoritm ἀνθυφαίρεσις sau ἀνταναίρεσις - „scădere reciprocă”. Acest algoritm nu a fost descoperit de Euclid, deoarece este deja menționat în Topeka Aristotel. În „Elementele” lui Euclid este descris de două ori - în cartea a VII-a pentru găsirea celui mai mare divizor comun a două numere naturale și în cartea X pentru găsirea celei mai mari măsuri comune a două mărimi omogene. În ambele cazuri, se oferă o descriere geometrică a algoritmului pentru a găsi „măsura comună” a două segmente.

Descriere

Algoritmul lui Euclid pentru numere întregi

Lasa a (\ displaystyle a)și b (\ displaystyle b)- numere întregi care nu sunt egale cu zero în același timp și o succesiune de numere

a> b> r 1> r 2> r 3> r 4>…> rn (\ displaystyle a> b> r_ (1)> r_ (2)> r_ (3)> r_ (4)> \ \ puncte \ > r_ (n))

determinată de faptul că fiecare r k (\ displaystyle r_ (k))- acesta este restul împărțirii numărului anterior la precedentul, iar penulul este împărțit complet la ultimul, adică:

a = b q 0 + r 1, (\ displaystyle a = bq_ (0) + r_ (1),) b = r 1 q 1 + r 2, (\ displaystyle b = r_ (1) q_ (1) + r_ (2),) r 1 = r 2 q 2 + r 3, (\ displaystyle r_ (1) = r_ (2) q_ (2) + r_ (3),) ⋯ (\ displaystyle \ cdots) r k - 2 = r k - 1 q k - 1 + r k, (\ displaystyle r_ (k-2) = r_ (k-1) q_ (k-1) + r_ (k),) ⋯ (\ displaystyle \ cdots) r n - 2 = r n - 1 q n - 1 + r n, (\ displaystyle r_ (n-2) = r_ (n-1) q_ (n-1) + r_ (n),) r n - 1 = r n q n. (\ displaystyle r_ (n-1) = r_ (n) q_ (n).)

Apoi gcd ( A, b), cel mai mare factor comun Ași b, este egal cu r n, ultimul termen diferit de zero din această secvență.

Existenţă astfel de r 1 , r 2 , ..., r n, adică posibilitatea împărțirii cu rest m pe n pentru orice întreg m si intregi n≠ 0 se dovedește prin inducție pe m.

Corectitudine acest algoritm decurge din următoarele două afirmații:

• Lasa A = b⋅q + r, apoi mcd (a, b) = mcd (b, r).

Dovada

• GCD ( r, 0) = r pentru orice diferit de zero r(deoarece 0 este divizibil cu orice număr întreg, altul decât zero).

Algoritm euclidian geometric

Să fie date două segmente de lungime Ași b... Scădeți pe cel mai mic din segmentul mai mare și înlocuiți segmentul mai mare cu diferența rezultată. Repetăm ​​această operație până când segmentele sunt egale. Dacă se întâmplă acest lucru, atunci segmentele originale sunt comensurabile, iar ultimul segment obținut este cea mai mare măsură comună a acestora. Dacă nu există o măsură generală, atunci procesul este nesfârșit. În această formă, algoritmul este descris de Euclid și este implementat folosind o busolă și o riglă.

Exemplu

Pentru ilustrare, algoritmul lui Euclid va fi folosit pentru a găsi GCD A= 1071 și b= 462. Pentru început, scădem un multiplu de 462 din 1071 până când obținem o diferență mai mică de 462. Trebuie să scădem 462 de două ori, ( q 0 = 2), rămânând cu un rest de 147:

1071 = 2 × 462 + 147.

Apoi scadem un multiplu de 147 din 462 pana obtinem o diferenta mai mica de 147. Trebuie sa scadem 147 ( q 1 = 3), rămânând cu un rest de 21:

462 = 3 × 147 + 21.

Apoi scadem un multiplu de 21 din 147 pana obtinem o diferenta mai mica de 21. Trebuie sa scadem 21 ( q 2 = 7), fără a lăsa rest:

147 = 7 × 21 + 0.

Astfel, succesiunea a> b> r 1 > r 2 > r 3 > … > r n în acest caz particular va arăta astfel:

1071 > 462 > 147 > 21.

Deoarece ultimul rest este zero, algoritmul se termină cu 21 și GCD (1071, 462) = 21.

În formă tabelară, pașii au fost următorii:

Aplicații

Algoritmul euclidian extins și raportul Bezout

Formule pentru r i (\ displaystyle r_ (i)) poate fi rescris astfel:

r 1 = a + b (- q 0) (\ displaystyle r_ (1) = a + b (-q_ (0))) r 2 = b - r 1 q 1 = a (- q 1) + b (1 + q 1 q 0) (\ displaystyle r_ (2) = b-r_ (1) q_ (1) = a (-q_ ( 1)) + b (1 + q_ (1) q_ (0))) ⋮ (\ displaystyle \ vdots) Gcd (a, b) = r n = a s + b t (\ displaystyle (a, b) = r_ (n) = as + bt)

Aici sși tîntreg. Această reprezentare a celui mai mare divizor comun se numește raportul Bezout și numerele sși t- Coeficienții Bezout. Relația Bezout este cheia în demonstrarea lemei lui Euclid și a teoremei principale a aritmeticii.

Fracții continuate

Algoritmul lui Euclid este strâns legat de fracțiile continue. Atitudine A/b poate fi reprezentat ca o fracție continuă:

a b = [q 0; q 1, q 2, ⋯, q n] (\ displaystyle (\ frac (a) (b)) =).

În acest caz, fracția continuă fără ultimul termen este egală cu raportul coeficienților Bezout t/s luate cu semnul minus:

[q 0; q 1, q 2, ⋯, q n - 1] = - t s (\ displaystyle = - (\ frac (t) (s))).

Secvența de egalități care definește algoritmul euclidian poate fi rescrisă sub forma:

ab = q 0 + r 0 bbr 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ rk - 2 rk - 1 = qk + rkrk - 1 ⋮ r N - 2 r N - 1 = q N (\ displaystyle (\ begin (aliniat) (\ frac (a) (b)) & = q_ (0) + (\ frac (r_ (0)) (b)) \\ (\ frac (b) ) (r_ (0))) & = q_ (1) + (\ frac (r_ (1)) (r_ (0))) \\ (\ frac (r_ (0)) (r_ (1))) & = q_ (2) + (\ frac (r_ (2)) (r_ (1))) \\ & () \ \ vdots \\ (\ frac (r_ (k-2)) (r_ (k-1) )) & = q_ (k) + (\ frac (r_ (k)) (r_ (k-1))) \\ & () \ \ vdots \\ (\ frac (r_ (N-2)) (r_ (N-1))) & = q_ (N) \ end (aliniat)))

Ultimul termen din partea dreaptă a unei egalități este întotdeauna egal cu reciproca părții din stânga a următoarei ecuații. Prin urmare, primele două ecuații pot fi combinate sub forma:

ab = q 0 + 1 q 1 + r 1 r 0 (\ displaystyle (\ frac (a) (b)) = q_ (0) + (\ cfrac (1) (q_ (1) + (\ cfrac (r_ () 1)) (r_ (0))))))

A treia egalitate poate fi folosită pentru a înlocui numitorul unei expresii r 1 /r 0, obținem:

ab = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 (\ displaystyle (\ frac (a) (b)) = q_ (0) + (\ cfrac (1) (q_ (1) + (\ cfrac (1) (q_ (2) + (\ cfrac (r_ (2)) (r_ (1))))))))

Ultimul raport al reziduurilor r k /r k−1 poate fi întotdeauna înlocuit folosind următoarea egalitate din succesiune și așa mai departe până la ultima ecuație. Rezultatul este o fracție continuă:

a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [q 0; q 1, q 2,…, q N] (\ displaystyle (\ frac (a) (b)) = q_ (0) + (\ cfrac (1) (q_ (1) + (\ cfrac (1) (q_ (2) + (\ cfrac (1) (\ ddots + (\ cfrac (1) (q_ (N)))))))) =)

Algoritm euclidian generalizat pentru polinoame

Algoritmul euclidian și algoritmul euclidian extins se generalizează în mod natural la inelul de polinoame k[X] dintr-o variabilă peste un câmp arbitrar k, deoarece împărțirea cu rest este definită pentru astfel de polinoame. Când se execută algoritmul euclidian pentru polinoame, similar algoritmului euclidian pentru numere întregi, se obține o succesiune de reziduuri polinomiale (PRS).

Exemplu pentru un inel Z[X]

Fie cont (f) prin definiție GCD-ul coeficienților polinomului f (x) din Z [x] - conţinut polinom. Se numește câtul împărțirii f (x) la cont (f). partea primitivă a polinomului f (x) și se notează prin primpart (f (x)). Aceste definiții vor fi necesare pentru a găsi mcd-ul a două polinoame p 1 (x)și p 2 (x)în inelul Z [x]. Pentru polinoame peste numere întregi, următorul lucru este adevărat:

C o n t ((\ displaystyle cont () NODNOD (c o n t (p 1 (x)), c o n t (p 2 (x))), (\ displaystyle \ (cont (p_ (1) (x)), cont (p_ (2) (x)) \),)

P r i m p a r t ((\ displaystyle primpart () Gcd (p 1 (x), p 2 (x))) = (\ displaystyle \ (p_ (1) (x), p_ (2) (x) \)) =) Gcd (p r i m p a r t (p 1 (x)), p r i m p a r t (p 2 (x))). (\ displaystyle \ (primpart (p_ (1) (x)), primpart (p_ (2) (x)) \).)

Astfel, problema găsirii GCD-ului a două polinoame arbitrare se reduce la problema găsirii GCD-ului polinoamelor primitive.

Să fie două polinoame primitive p 1 (x) și p 2 (x) din Z [x] pentru care relația dintre puterile lor este valabilă: deg (p 1 (x)) = m și deg (p 2 (x)) = n, m> n. Împărțirea polinoamelor cu rest presupune divizibilitatea exactă a coeficientului principal al dividendului cu coeficientul superior al divizorului; în cazul general, împărțirea cu restul este imposibilă. Prin urmare, se introduce un algoritm de pseudo-diviziune, care permite totuși să se obțină o pseudofrecvență și pseudo-reziduală (prem), care aparțin prin ele însele mulțimii polinoamelor peste numere întregi.

Prin pseudo-diviziune înțelegem că împărțirea în sine este precedată de înmulțirea polinomului p 1 (x) (\ displaystyle p_ (1) (x)) pe (l c (p 2 (x))) m - n + 1 (\ displaystyle (lc (p_ (2) (x))) ^ (m-n + 1)), acesta este

L c (p 2 (x)) m - n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x), deg ⁡ (r (x))< deg ⁡ (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}

Unde q (x) (\ displaystyle q (x))și r (x) (\ displaystyle r (x))- pseudofrecventa si respectiv pseudo-reziduala.

Asa de, p 1 (x), p 2 (x) ∈ Z [x] (\ displaystyle p_ (1) (x), p_ (2) (x) \ în Z [x]), și deg ⁡ (p 1) = n 1 ≥ deg ⁡ (p 2) = n 2 (\ displaystyle \ deg (p_ (1)) = n_ (1) \ geq \ deg (p_ (2)) = n_ (2) )... Atunci algoritmul lui Euclid constă din următorii pași:

1. Calculul conținutului GCD:

C: = (\ displaystyle c: =) Gcd (c o n t (p 1), c o n t (p 2)) (\ displaystyle \ (cont (p_ (1)), cont (p_ (2)) \)).

2. Calculul părților primitive:

P 1 ′ (x): = p r i m p a r t (p 1 (x)); (\ displaystyle p_ (1) "(x): = primpart (p_ (1) (x));)

P 2 ′ (x): = p r i m p a r t (p 2 (x)). (\ displaystyle p_ (2) "(x): = primpart (p_ (2) (x)).)

3. Construcția unei secvențe de reziduuri polinomiale:

P 1 ′ (x), (\ displaystyle p_ (1) "(x),)

P 2 ′ (x), (\ displaystyle p_ (2) "(x),)

P 3 (x): = prem (p 1 ′ (x), p 2 ′ (x)), (\ displaystyle p_ (3) (x): = prem (p_ (1) "(x), p_ (2) ) "(X)),)

P 4 (x): = prem (p 2 ′ (x), p 3 (x)), (\ displaystyle p_ (4) (x): = prem (p_ (2) "(x), p_ (3) (X)),)

P 5 (x): = prem (p 3 (x), p 4 (x)), (\ displaystyle p_ (5) (x): = prem (p_ (3) (x), p_ (4) (x): )),)

... ... ... (\ stil de afișare ...)

P h (x): = p r e m (p h - 2 (x), p h - 1 (x)). (\ displaystyle p_ (h) (x): = prem (p_ (h-2) (x), p_ (h-1) (x)).)

Luați în considerare două metode principale pentru a găsi GCD în două moduri principale: folosind algoritmul euclidian și prin factorizarea în factori primi. Să aplicăm ambele metode pentru două, trei sau mai multe numere.

Algoritmul lui Euclid pentru găsirea GCD

Algoritmul lui Euclid facilitează calcularea celui mai mare divizor comun pentru două numere pozitive. Am dat formulările și dovezile algoritmului lui Euclid în secțiunea „Cel mai mare divizor comun: determinant, exemple”.

Esența algoritmului este de a efectua secvențial împărțirea cu un rest, timp în care se obține un număr de egalități de formă:

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

Putem pune capăt diviziunii când r k + 1 = 0, în care r k = mcd (a, b).

Exemplul 1

64 și 48 .

Soluţie

Să introducem notația: a = 64, b = 48.

Pe baza algoritmului euclidian, efectuăm împărțirea 64 pe 48 .

Primim 1 și restul de 16. Se dovedește că q 1 = 1, r 1 = 16.

În a doua etapă, împărțim 48 până la 16, obținem 3. Acesta este q 2 = 3, A r2 = 0. Astfel, numărul 16 este cel mai mare divizor comun pentru numerele din condiție.

Răspuns: GCD (64, 48) = 16.

Exemplul 2

Care este GCD-ul numerelor 111 și 432 ?

Soluţie

Divide 432 pe 111 ... Conform algoritmului lui Euclid, obținem lanțul de egalități 432 = 111 3 + 99, 111 = 99 1 + 12, 99 = 12 8 + 3, 12 = 3 4.

Astfel, cel mai mare divizor comun al numerelor 111 și 432 este 3.

Răspuns: GCD (111, 432) = 3.

Exemplul 3

Aflați cel mai mare numitor comun al lui 661 și 113.

Soluţie

Să efectuăm împărțirea secvențială a numerelor și să obținem mcd (661 , 113) = 1 ... Aceasta înseamnă că 661 și 113 sunt numere coprime. Am putea să ne dăm seama înainte de a începe calculul dacă ne-am uita la tabelul cu numere prime.

Răspuns: GCD (661, 113) = 1.

Găsirea mcd prin factorizarea numerelor în factori primi

Pentru a găsi cel mai mare divizor comun a două numere prin metoda factorizării, este necesar să înmulțim toți factorii primi obținuți prin descompunerea acestor două numere și care le sunt comuni.

Exemplul 4

Dacă factorăm numerele 220 și 600 în factori primi, obținem două produse: 220 = 2 2 5 11și 600 = 2 2 2 3 5 5... Factorii comuni în aceste două produse vor fi 2, 2 și 5. Aceasta înseamnă că GCD (220, 600) = 2 2 5 = 20.

Exemplul 5

Găsiți cel mai mare divizor comun al numerelor 72 și 96 .

Soluţie

Găsiți toți factorii primi ai numerelor 72 și 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

Factorii primi comuni a două numere sunt 2, 2, 2 și 3. Aceasta înseamnă că GCD (72, 96) = 2 2 2 3 = 24.

Răspuns: GCD (72, 96) = 24.

Regula pentru găsirea celui mai mare divizor comun a două numere se bazează pe proprietățile celui mai mare divizor comun, conform cărora GCD (ma 1, mb 1) = m GCD (a 1, b 1), unde m este orice număr întreg pozitiv .

Găsirea GCD a trei sau mai multe numere

Indiferent de numărul de numere pentru care trebuie să găsim GCD-ul, vom acționa după același algoritm, care constă în găsirea secvenţială a GCD-ului a două numere. Acest algoritm se bazează pe aplicarea următoarei teoreme: GCD a mai multor numere a 1, a 2,…, a k egală cu numărul d k, care se găsește în calculul secvenţial al 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.

Exemplul 6

Găsiți cel mai mare divisor comun pentru patru numere 78, 294, 570 și 36 .

Soluţie

Să introducem notația: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Să începem prin a găsi MCD-ul numerelor 78 și 294: d 2 = Gcd (78 , 294) = 6 .

Acum să începem să găsim d 3 = mcd (d 2, a 3) = mcd (6, 570). Conform algoritmului lui Euclid 570 = 6 · 95.Înseamnă că d 3 = Gcd (6 , 570) = 6 .

Aflați d 4 = mcd (d 3, a 4) = mcd (6, 36). 36 este divizibil cu 6 fără rest. Acest lucru ne permite să primim d 4 = Gcd (6 , 36) = 6 .

d 4 = 6, adică gcd (78 , 294 , 570 , 36) = 6 .

Răspuns:

Acum să ne uităm la un alt mod de a calcula GCD pentru acele numere și mai multe. Putem găsi GCD înmulțind toți factorii primi comuni ai numerelor.

Exemplul 7

Calculați mcd-ul numerelor 78, 294, 570 și 36 .

Soluţie

Să descompunăm aceste numere în factori primi: 78 = 2 · 3 · 13, 294 = 2 · 3 · 7 · 7, 570 = 2 · 3 · 5 · 19, 36 = 2 · 2 · 3 · 3.

Pentru toate cele patru numere, factorii primi comuni sunt 2 și 3.

Se pare că GCD (78, 294, 570, 36) = 2 3 = 6.

Răspuns: GCD (78, 294, 570, 36) = 6.

Găsirea mcd pentru numere negative

Dacă avem de-a face cu numere negative, atunci putem folosi valorile absolute ale acestor numere pentru a găsi cel mai mare divizor comun. Putem face acest lucru cunoscând proprietatea numerelor cu semne opuse: numerele nși - n au aceiași divizori.

Exemplul 8

Găsiți mcd-ul numerelor întregi negative − 231 și − 140 .

Soluţie

Pentru a efectua calcule, luați modulele numerelor date în condiție. Acestea vor fi numerele 231 și 140. Să-l scriem pe scurt: GCD (− 231 , − 140) = GCD (231, 140). Acum vom aplica algoritmul lui Euclid pentru a găsi factori primi ai două numere: 231 = 140 · 1 + 91; 140 = 91 * 1 + 49; 91 = 49 * 1 + 42; 49 = 42 1 + 7 și 42 = 7 6... Obținem că mcd (231, 140) = 7 .

Și de când GCD (− 231 , − 140) = Gcd (231 , 140) , apoi numerele gcd − 231 și − 140 este egal cu 7 .

Răspuns: GCD (- 231, - 140) = 7.

Exemplul 9

Determinați MCD a trei numere - 585, 81 și − 189 .

Soluţie

Înlocuim numerele negative din lista de mai sus cu valorile lor absolute, obținem GCD (− 585 , 81 , − 189) = Gcd (585 , 81 , 189) ... Apoi descompunem toate aceste numere în factori primi: 585 = 3 3 5 13, 81 = 3 3 3 3 și 189 = 3 3 3 7... Cele trei numere au în comun factorii primi 3 și 3. Se pare că GCD (585, 81, 189) = GCD (- 585, 81, - 189) = 9.

Răspuns: GCD (- 585, 81, - 189) = 9.

Dacă observați o eroare în text, vă rugăm să o selectați și să apăsați Ctrl + Enter