Folosit pe scară largă în comerțul electronic. Algoritmul este folosit și în rezolvarea ecuațiilor liniare Diofantine, în construirea de fracții continue și î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 fundamentală a aritmeticii.

YouTube enciclopedic

1 / 5

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

✪Algoritm euclidian

✪ algoritm euclidian, cale rapidă găsi gcd

✪ Matematică 71. Cel mai bun divizor comun. Algoritmul lui Euclid - Academia de Științe a Divertismentului

✪ 20 while loop algoritmul euclidian Python

Subtitrări

Poveste

Matematicienii greci antici au numit acest algoritm ἀνθυφαίρεσις sau ἀνταναίρεσις - „scădere reciprocă”. Acest algoritm nu a fost descoperit de Euclid, deoarece a fost 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 al doi numere naturale iar î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 găsirea „măsurii comune” a două segmente.

Descriere

Algoritmul lui Euclid pentru numere întregi

Lasă 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 > … > r n (\displaystyle a>b>r_(1)>r_(2)>r_(3)>r_(4)>\ \dots \ >r_(n))

determinată de faptul că fiecare r k (\displaystyle r_(k))- acesta este restul împărțirii numărului anterior la cel anterior, iar penultimul 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(, o b Apoi GCD(Şi o), cel mai mare divizor comun , este egal n, ultimul termen diferit de zero al acestei secvențe.

Existenţă astfel de , este egal 1 , , este egal 2 , ..., , este egal n, adică posibilitatea împărțirii cu rest m pe n pentru orice număr întreg m si intregul n≠ 0, se poate dovedi prin inductie pe m.

Corectitudine Acest algoritm rezultă din următoarele două afirmații:

• Lasă Apoi GCD( = o⋅q + , este egal, apoi mcd (a, b) = mcd (b, r).

Dovada

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

Algoritm euclidian geometric

Să fie date două segmente de lungime Apoi GCD(Şi o. Scădeți segmentul 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 rezultat 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 a fost descris de Euclid și este implementat folosind o busolă și o riglă.

Exemplu

Pentru a ilustra, algoritmul euclidian va fi folosit pentru a găsi mcd Apoi GCD(= 1071 și o= 462. Mai întâi, 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), lăsând un rest de 147:

1071 = 2 × 462 + 147.

Apoi scădem multiplii lui 147 din 462 până când obținem o diferență mai mică de 147. Trebuie să scădem 147 de trei ori ( q 1 = 3), lăsând un rest de 21:

462 = 3 × 147 + 21.

Apoi scădem multiplii lui 21 din 147 până când diferența este mai mică de 21. Trebuie să scădem 21 de șapte ori ( q 2 = 7), fără a lăsa rest:

147 = 7 × 21 + 0.

Astfel secvența a > b > , este egal 1 > , este egal 2 > , este egal 3 > … > , este egal n în acest caz particular va arăta astfel:

1071 > 462 > 147 > 21.

De la ultimul rest egal cu zero, algoritmul se termină cu numărul 21 și mcd(1071, 462) = 21.

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

Aplicații

Algoritmul euclidian extins și relația lui 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 relația Bezout și numerele sŞi t- Coeficienții Bezout. Relația lui Bezout este cheia pentru demonstrarea lemei lui Euclid și a teoremei fundamentale a aritmeticii.

Fracții continuate

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

a b = [ q 0 ;.

q 1 , q 2 , ⋯ , q n ] (\displaystyle (\frac (a)(b))=) t/sÎn acest caz, fracția continuă fără ultimul termen este egală cu raportul coeficienților Bezout

, luat 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:

a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k − 2 r k − 1 = q k + r k r k − 1 ⋮ r N − 2 r N − 2 r 1 = q N (\displaystyle (\begin(aligned)(\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 ecuației este întotdeauna egal cu inversul părții stângi a următoarei ecuații. Prin urmare, primele două ecuații pot fi combinate sub forma: , este egal 1 /, este egal a b = 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 expresiei

0, obținem: , este egal a b = 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)))))))) /, este egal a b = 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 rezidual

k

−1 poate fi întotdeauna înlocuit folosind următoarea ecuație 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 ; a b = 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))))))))[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 a b = 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)))))))) Algoritmul euclidian și algoritmul euclidian extins se generalizează în mod natural la inelul de polinoame

x ] dintr-o variabilă peste un câmp arbitrar[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))))))))=)]

, deoarece pentru astfel de polinoame este definită operația de împărțire cu rest. Rularea algoritmului euclidian pentru polinoame într-un mod similar cu algoritmul euclidian pentru numere întregi produce o secvență de rest polinomial (PRS). Exemplu pentru un inel Z Fie cont(f) prin definiție mcd-ul coeficienților polinomului f(x) din Z[x] - polinom f(x) și se notează prin primpart(f(x)). Aceste definiții vor fi necesare pentru a găsi mcd-ul a două polinoame p1(x)Şi p2(x)în inelul Z[x]. Pentru polinoame peste numere întregi, 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 celui mai mare coeficient al dividendului cu cel mai mare coeficient al divizorului în cazul general, împărțirea cu rest nu poate fi efectuată. Prin urmare, este introdus un algoritm de pseudo-diviziune, care permite totuși să se obțină un pseudo-cot și un pseudo-restu (prem), care vor aparține ele însele mulțimii polinoamelor peste numere întregi. Prin pseudo-diviziune înțelegem că împărțirea în sine este precedată de înmulțirea unui polinom pe p 1 (x) (\displaystyle p_(1)(x))(l c (p 2 (x))) m - n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1))

, adică< 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)),}

L c (p 2 (x)) m − n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x) , deg ⁡ (r (x)) UndeŞi q (x) (\displaystyle q(x)) r (x) (\displaystyle r(x))

- pseudo-cot și, respectiv, pseudo-restul. Aşa, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1)(x),p_(2)(x)\in 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) )

. Apoi algoritmul euclidian constă din următorii pași:

1. Calculul conținutului GCD: GCD C:= (\displaystyle c:=).

( 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)).)

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

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

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

.

.

• .
• (\displaystyle ...)

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)).)

Introduceți conceptul de „algoritm euclidian”.

Învață să găsești cei mai obișnuiți divizori folosind diferite metode matematice. Progresul lecției Conceptul de algoritm euclidian

Este una dintre cele mai vechi matematice, care are peste 2000 de ani.

Algoritmul Euclid a fost inventat pentru a găsi cel mai mare divizor 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 este el însuși divizibil fără rest cu orice alt divizor al acestor numere.

Cu alte cuvinte, acesta este cel mai mare număr cu care două numere pentru care poate fi găsit un divizor 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 numărul mai mic

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

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 divizor comun pentru 300 și 180. 300/180 = 1 (restul 120)

180/120 = 1 (restul 60) 120/60 = 2 (restul 0). Sfârşit: Cel mai mare divizor comun este 6.ÎN

ciclu

„a” sau „b” fixează restul diviziunii. Când nu există rest (nu știm dacă este în „a” sau „b”, așa că le verificăm pe ambele

conditii

), apoi ciclul se termină.

La sfârșit, este afișată suma „a” și „b”, deoarece nu știm care variabilă conține cel mai mare divizor comun și, în orice caz, una dintre ele conține 0, ceea ce nu afectează rezultatul sumei.

Algoritm pentru găsirea GCD prin scădere

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

Dacă este divizibil fără rest, atunci numărul mai mic este cel mai mare divizor comun. Acum trebuie să ieși Descrierea algoritmului de găsire a celui mai mare divizor comun prin scădere

Găsiți cel mai mare divizor comun pentru 300 și 180. 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șiți din buclă

Dacă rezultatul scăderii nu este 0, atunci numărul mai mare este înlocuit cu rezultatul scăderii Găsiți numerele 300 și 180. procedați în aceleași moduri ca mai sus.

Operația de împărțire cu un rest este înlocuită cu omologul său geometric: mai puțin segment o amână pe cel mai mare de câte ori posibil, iar restul segmentului mai mare (și acesta este restul diviziunii) este amânat pe segmentul mai mic.

Dacă segmentele Apoi GCD(Şi o proporțional, atunci ultimul rest diferit de zero va oferi cea mai mare măsură comună a segmentelor.

Dacă sunt incomensurabile, succesiunea rezultată de reziduuri non-nule va fi infinită.

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

Ca segmente luăm laturile AB și AC ale unui triunghi isoscel ABC, în care A=C = 72°, B= 36°.

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

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

Întrebări

1. Ce este algoritmul euclidian?

2. Care este cel mai mare divizor comun?

Lista surselor utilizate

1. Lecție pe tema: „Algoritmul euclidian”, P. I. Korchevoy, Luțk

2. Shchetnikov A.I. Algoritmul euclidian și fracțiile continuate. - Novosibirsk: ANT, 2003.

3. Countinho 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 numită după. Taras Şevcenko Solovyov M. S.

Am lucrat la lecție

Korchevoy P.I.

Soloviev M. S.

Puteți pune o întrebare despre educația modernă, puteți exprima o idee sau rezolva o problemă presantă la Forum educațional

1.1 Aplicarea algoritmului euclidian

Ca orice lucru bine făcut, algoritmul euclidian produce mult mai mult decât era de așteptat inițial. Din examinarea sa reiese clar, de exemplu, că mulțimea divizorilor a și b coincide cu mulțimea divizorilor (a, b). El oferă, de asemenea, o modalitate practică de a găsi numerele u și v din Z (sau, dacă preferați, din teorema de la punctul 2), astfel încât

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

Într-adevăr, din lanțul de egalități avem:

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

(Mergem de-a lungul lanțului de egalități de jos în sus, exprimând restul din fiecare egalitate următoare și substituind-o în expresia obținută în acest moment)

Au + bv = (a, b).

Fără îndoială, procedura descrisă de Euclid pentru determinarea măsurii comune a două mărimi în raport cu numerele (și măsura comună a două numere naturale, evident, este cel mai mare divizor comun al acestora) a fost inventată cu mult înaintea lui Euclid. Vechii matematicieni chinezi au găsit și GCD în același mod. Și doar faptul că această procedură a devenit cunoscută în Renaștere tocmai din „Principii” i-a dat numele de „algoritm euclidian”.

Cel mai probabil, a apărut din practica comercială a comercianților antici, când aveau nevoie să compare diferite rapoarte de numere întregi. Cum, de exemplu, putem compara rapoartele numerelor 3703700 și 1234567 și ale numerelor 22962965 și 7654321? Era destul de firesc să încercăm să afli de câte ori se încadrează un număr mai mic într-un număr mai mare. Este ușor de verificat că 3703700 = 2 1234567 + 1234566 și 22962965 = 3 7654321 + 2. Acum este clar că raportul de 3703700 la 1234567 este mai mic decât raportul de 245296, așa cum scriem acum 2454321 + 2.

2,99999919 <= 3, 000000261,

Calculatoare antice explicate într-o frază lungă.

Dacă ar trebui să comparăm rapoarte mai apropiate ale numerelor, de exemplu, și, atunci calculele ar fi mai complexe:

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.

Algoritmul euclidian ne permite să determinăm mcd-ul numerelor 71755875 și 61735500, care este egal cu 3375 și corespunde expansiunii raportului 71755875 la 61735500 într-o fracție continuă:

Algoritmul Euclid se dovedește a fi echivalent cu procedura modernă de descompunere a unui număr într-o fracție continuă și, în plus, vă permite să „rotunjiți” rapoartele numerelor, de exemplu. înlocuiți o fracție cu un numitor mare cu o fracție foarte apropiată cu un numitor mai mic. De fapt, expresia

egală cu o fracție, în matematica modernă se numește „fracție adecvată” a descompunerii relației b = într-o fracție continuă (sau continuă).

Este clar că

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

deoarece

Comparația de mai sus a fost făcută în secolul al III-lea. î.Hr Aristarh din Samos în tratatul său „Despre distanța și dimensiunea Lunii și a Soarelui”.

Se știe acum că fracțiile adecvate ale expansiunii continue a fracțiunii oricărui număr (rațional sau irațional) sunt cele mai bune aproximări raționale ale acelui număr.

Algoritmi cu polinoame

Algoritmul lui Euclid este o metodă pentru găsirea celui mai mare divizor comun a două numere întregi, precum și a două polinoame ale aceleiași variabile...

Unul dintre cei mai vechi algoritmi matematici este algoritmul Euclid pentru găsirea celui mai mare divizor comun a două numere pozitive. Iată forma sa cea mai simplă. Să fie date două numere întregi. Daca sunt egali...

Analiza algoritmului euclidian în inele euclidiene

Înainte de a începe să analizăm algoritmul euclidian, să luăm în considerare numerele Fibonacci. Esența șirului Fibonacci este că pornind de la 1.1, următorul număr se obține prin adunarea celor două anterioare. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ......

Istoria formării conceptului de „algoritm”. Cei mai faimoși algoritmi din istoria matematicii

Algoritmul euclidian este o metodă universală care vă permite să calculați cel mai mare divizor comun a două numere întregi pozitive. Descrierea algoritmului de găsire a GCD prin diviziune: 1. Împărțiți numărul mai mare la cel mai mic 2. Dacă este împărțit fără rest...

Inel întreg gaussian

Folosim definiția obișnuită a celui mai mare divizor comun pentru inele. MCD a două numere gaussiene este divizorul lor comun care este divizibil cu orice alt divizor comun. Ca în multe numere întregi...

Fundamentele matematice ale sistemului de clase reziduale

Să ne uităm la un exemplu. Fie p = 6. Atunci avem șase clase de partiție a mulțimii de întregi modulo 6: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; unde r desemnează restul la împărțirea unui număr întreg la 6...

Metode de studiere a polinoamelor la clasele opționale din gimnaziu

Fie inelul de polinoame să se termine. Definiția 1: Fie și, dacă există un polinom, atunci restul diviziunii este zero, atunci se numește divizor al polinomului și se notează: ()...

Principalele etape de formare și structurare a matematicii moderne

În secolul al III-lea î.Hr., o carte a lui Euclid cu același nume a apărut în Alexandria, în traducerea rusă a „Principiilor”. Termenul „geometrie elementară” provine de la numele latin „Începuturi”. În ciuda...

Pe teritoriul unui anumit oraș N există fabrici și magazine cărora li se aprovizionează produsele din aceste fabrici. Ca urmare a dezvoltării, au fost identificate posibile rute de stabilire a comunicațiilor și a fost estimat costul creării acestora pentru fiecare rută...

Aplicarea metodelor matematice discrete în economie

O companie angajată în transportul de mărfuri perisabile trebuie să livreze mărfuri de la Suifenhe la Khabarovsk și există mai multe rute de-a lungul cărora se poate face livrarea. Distanța dintre Suifenhe și City 2 este de 15 km...

Dezvoltarea conceptului de „Spațiu” și geometrie non-euclidiană

Metode speciale de integrare a expresiilor raţionale

Să fie necesar să se găsească mcd-ul polinoamelor și. Fără pierderea generalității, vom presupune că gradul nu este mai mare decât gradul. Să reprezentăm polinomul sub forma: unde este restul împărțirii la. Atunci gradul este mai mic decât gradul divizorului. Următorul...

Teoria reziduurilor

Teoria reziduurilor

Definiţie. Numărul d??Z, care împarte simultan numerele a, b, c, ..., k??Z, se numeşte divizor comun al acestor numere. Cel mai mare d cu această proprietate se numește cel mai mare divizor comun. Denumire: d = (a, b, c, ..., k). Teorema. Dacă (a, b) = d...

Teoria reziduurilor

Fie necesar să se rezolve o ecuație diofantică liniară: ax + by = c, unde a, b, c ??Z; a și b nu sunt zerouri. Să încercăm să raționăm uitându-ne la această ecuație. Fie (a, b) = d. Atunci a = a 1 d ; b = b 1 d și ecuația arată astfel: a 1 d x + b 1 d y = c, adică. d· (a 1 x + b 1 y) = c...

algoritmul lui Euclid este un algoritm pentru găsirea celui mai mare divizor comun (GCD) al unei perechi de numere întregi.

Cel mai mare divizor comun (GCD) este un număr care împarte două numere fără rest și este el însuși divizibil fără rest cu orice alt divizor al celor două numere date. Mai simplu spus, acesta este cel mai mare număr prin care două numere pentru care se caută mcd pot fi împărțite fără rest.

Algoritm pentru găsirea GCD prin diviziune

1. Împărțiți numărul mai mare la numărul mai mic.
2. Dacă este împărțit fără rest, atunci numărul mai mic este GCD (ar trebui să părăsiți ciclul).
3. Dacă există un rest, atunci înlocuiți numărul mai mare cu restul diviziunii.
4. Să trecem la punctul 1.

Dacă este divizibil fără rest, atunci numărul mai mic este cel mai mare divizor comun. Acum trebuie să ieși
Găsiți mcd pentru 30 și 18.
30 / 18 = 1 (restul 12)
18 / 12 = 1 (restul 6)
12 / 6 = 2 (restul 0)
Sfârșit: GCD este un divizor de 6.
GCD(30, 18) = 6

a = 50 b = 130 în timp ce a != 0 și b != 0 : dacă a > b: a = a % b altfel : b = b % a print (a + b)

În buclă, restul diviziunii este scris la variabila a sau b. Bucla se termină când cel puțin una dintre variabile este zero. Aceasta înseamnă că celălalt conține un gcd. Cu toate acestea, nu știm care dintre ele exact. Prin urmare, pentru GCD găsim suma acestor variabile. Deoarece una dintre variabile este zero, nu are niciun efect asupra rezultatului.

Algoritm pentru găsirea GCD prin scădere

1. Scădeți numărul mai mic din numărul mai mare.
2. Dacă rezultatul este 0, înseamnă că numerele sunt egale între ele și sunt GCD (ar trebui să ieși din buclă).
3. Dacă rezultatul scăderii nu este egal cu 0, atunci înlocuiți numărul mai mare cu rezultatul scăderii.
4. Să trecem la punctul 1.

Dacă este divizibil fără rest, atunci numărul mai mic este cel mai mare divizor comun. Acum trebuie să ieși
Găsiți mcd pentru 30 și 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Sfârșit: GCD este un minuend sau subtraend.
GCD(30, 18) = 6

a = 50 b = 130 în timp ce a != b: dacă a > b: a = a - b altfel : b = b - a print (a)

Să luăm î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.

Algoritm euclidian pentru găsirea GCD

Algoritmul lui Euclidean facilitează calcularea celui mai mare factor comun a două numere pozitive. Am prezentat formulările și dovezile algoritmului 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țin o serie 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 termina diviziunea când r k + 1 = 0, în timp ce r k = mcd (a, b).

Exemplul 1

64 Şi 48 .

Soluţie

Să introducem următoarele notații: a = 64, b = 48.

Pe baza algoritmului euclidian, vom efectua împărțirea 64 pe 48 .

Obținem 1 și restul 16. Se dovedește că q 1 = 1, r 1 = 16.

Al doilea pas este împărțirea 48 până la 16, obținem 3. Adică q 2 = 3, A r 2 = 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

Ne împărțim 432 pe 111 . Conform algoritmului euclidian, 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 este 111 Şi 432 – acesta este 3.

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

Exemplul 3

Aflați cel mai mare divizor comun al numerelor 661 și 113.

Soluţie

Să împărțim succesiv numerele și să obținem GCD (661 , 113) = 1 . Aceasta înseamnă că 661 și 113 sunt numere relativ prime. Am putea să ne dăm seama înainte de a începe calculul dacă am consulta un tabel cu numere prime.

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

Aflarea GCD prin factorizarea numerelor în factori primi

Pentru a găsi cel mai mare divizor comun a două numere folosind metoda descompunerea în factori, este necesar să înmulțiți toți factorii primi obținuți prin factorizarea 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 sunt 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 pentru 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 mcd (m a 1, m b 1) = m mgcd (a 1, b 1), unde m este orice număr întreg pozitiv .

Găsirea mcd-ului a trei sau mai multe numere

Indiferent de numărul de numere pentru care trebuie să găsim GCD-ul, vom urma 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 dk, care se găsește prin calcularea secvenţială a mcd (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

Aflați cel mai mare divizor comun al 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 = GCD (d 2 , a 3) = GCD (6, 570). Conform algoritmului euclidian 570 = 6 95. Aceasta înseamnă că d 3 = GCD (6 , 570) = 6 .

Să aflăm d 4 = GCD (d 3 , a 4) = GCD (6, 36). 36 divizibil cu 6 fara rest. Acest lucru ne permite să obținem d 4 = GCD (6 , 36) = 6 .

d4 = 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 mcd î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 vor fi numerele 2 și 3.

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

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

Găsirea GCD de numere negative

Dacă avem de-a face cu numere negative, atunci putem folosi modulele 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, luăm modulele numerelor date în condiție. Acestea vor fi numerele 231 și 140. Să-l notăm pe scurt: GCD (− 231 , − 140) = GCD (231, 140). Acum aplicăm algoritmul 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ă GCD (231, 140) = 7 .

Și de când GCD (− 231 , − 140) = GCD (231 , 140) , apoi mcd de numere − 231 Şi − 140 egală 7 .

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

Exemplul 9

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

Soluţie

Să înlocuim numerele negative din lista de mai sus cu valorile lor absolute, obținem GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Apoi factorăm toate aceste numere în factori primi: 585 = 3 3 5 13, 81 = 3 3 3 3 și 189 = 3 3 3 7. Comuni celor trei numere sunt 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 evidențiați și să apăsați Ctrl+Enter