Conţinutul principal
Curs: Mate pentru Info > Unitatea 10
Lecția 5: Cel mai mare divizor comunAlgoritmul lui Euclid
Cel mai mare divizor comun (CMMDC) a două numere întregi A și B este cel mai mare număr întreg care divide atât pe A, cât și pe B.
Algoritmul lui Euclid este o tehnică prin care aflăm rapid CMMDC a două numere întregi.
Algoritmul
Algoritmul lui Euclid pentru determinarea CMMDC(A, B) este următorul:
- Dacă A = 0, atunci CMMDC(A,B)=B, deoarece CMMDC(0,B)=B.
- Dacă B = 0, atunci CMMDC(A,B)=A, deoarece CMMDC(A,0)=A.
- Îl scriem pe A într-o împărțire cu rest (A = B⋅Q + R)
- Aflăm CMMDC(B,R) folosind Algoritmul lui Euclid, deoarece CMMDC(A, B) = CMMDC(B,R)
Exemplu:
Găsește CMMDC(270, 192)
- A=270, B=192
- A ≠0
- B ≠0
- Prin împărțirea (lungă) cu rest aflăm că 270/192 = 1 cu restul 78. Putem scrie astfel: 270 = 192 * 1 +78
- Aflăm CMMDC(192,78), deoarece CMMDC(270,192)=CMMDC(192,78)
A=192, B=78
- A ≠0
- B ≠0
- Prin împărțirea (lungă) cu rest aflăm că 192/78 = 2 cu restul 36. Putem scrie sub forma:
- 192 = 78 * 2 + 36
- Aflăm CMMDC(78,36), deoarece CMMDC(192,78)=CMMDC(78,36)
A=78, B=36
- A ≠0
- B ≠0
- Prin împărțirea (lungă) cu rest aflăm că 78/36 = 2 cu restul 6. Putem scrie sub forma:
- 78 = 36 * 2 + 6
- Aflăm CMMDC(36,6), deoarece CMMDC(78,36)=CMMDC(36,6)
A=36, B=6
- A ≠0
- B ≠0
- Prin împărțirea (lungă) cu rest aflăm că 36/6 = 6 cu restul 0. Putem scrie sub forma:
- 36 = 6 * 6 + 0
- Aflăm GCD(6,0), deoarece CMMDC(36,6)=CMMDC(6,0)
A=6, B=0
- A ≠0
- B =0, CMMDC(6,0)=6
Rezultatul final este:
CMMDC(270,192) = CMMDC(192,78) = CMMDC(78,36) = CMMDC(36,6) = CMMDC(6,0) = 6
CMMDC(270,192) = 6
Înțelegerea Algoritmului lui Euclid
Dacă examinăm Algoritmul lui Euclid, putem observa că folosește următoarele proprietăți:
- CMMDC(A,0) = A
- CMMDC(0,B) = B
- Dacă A = B⋅Q + R și B≠0 atunci CMMDC(A,B) = CMMDC(B,R), unde Q este un întreg, iar R este un întreg între 0 și B-1
Primele două proprietăți ne permit să găsim CMMDC dacă oricare dintre numere este 0. A treia proprietate ne permite să rezolvăm o problemă mai dificilă și să o reducem la o problemă mai ușor de rezolvat.
Algoritmul lui Euclid folosește aceste proprietăți prin reducerea rapidă a problemei la probleme din ce in ce mai simple, folosind a treia proprietate, până când este ușor de rezolvat prin utilizarea uneia dintre primele două proprietăți.
Putem înțelege de ce aceste proprietăți funcționează prin demonstrarea lor.
Putem demonstra că CMMDC(A,0)=A astfel:
- Cel mai mare întreg care îl poate divide pe A este A.
- Toți întregii îl divid pe 0, deoarece pentru orice întreg C putem scrie C ⋅ 0 = 0. Deci, putem spune că A trebuie să îl dividă pe 0.
- Cel mai mare număr care divide și pe A și pe 0 este A.
Demonstrația pentru CMMDC(0,B)=B este similară. (Aceeași demonstrație, doar că înlocuim A cu B).
Pentru a demonstra că CMMDC(A,B)=CMMDC(B,R), trebuie să demonstrăm mai întâi că CMMDC(A,B)=CMMDC(B,A-B).
Să presupunem că avem 3 numere întregi A,B și C astfel încât A-B=C.
Demonstrăm că CMMDC(A,B) divide pe C
Prin definiție, CMMDC(A,B) divide pe A. Prin urmare, A trebuie să fie multiplu de CMMDC(A,B), de exemplu, X⋅CMMDC(A,B)=A, unde X este un întreg
Prin definiție, CMMDC(A,B) divide pe B. Prin urmare, B trebuie să fie multiplu de CMMDC(A,B), de exemplu, Y⋅CMMDC(A,B)=B, unde Y este un întreg
A-B=C ne conduce la:
- X⋅CMMDC(A,B) - Y⋅CMMDC(A,B) = C
- (X - Y)⋅CMMDC(A,B) = C
Putem observa că CMMDC(A,B) divide pe C.
O ilustrație a acestei demonstrații este arătată în partea stângă a imaginii de mai jos:
Demonstrăm că CMMDC(B,C) divide pe A
CMMDC(B,C), prin definiție, divide pe B. Așadar, B trebuie să fie multiplu de CMMDC(B,C), de exemplu, M⋅CMMDC(B,C)=B, unde M este un întreg
CMMDC(B,C), prin definiție, divide pe C. Așadar, C trebuie să fie multiplu de CMMDC(B,C), de exemplu, N⋅CMMDC(B,C)=C, unde N este un întreg
A-B=C ne conduce la:
- B+C=A
- M⋅GCD(B,C) + N⋅GCD(B,C) = A
- (M + N)⋅GCD(B,C) = A
Se poate observa că CMMDC(B,C) divide pe A.
O ilustrație a acestei demonstrații se poate observa în figura de mai jos
Demonstrăm că CMMDC(A,B)=CMMDC(A, A-B)
- CMMDC(A,B), prin definiție, divide pe B.
- Am demonstrat că CMMDC(A,B) divide pe C.
- Deoarece CMMDC(A,B) divide atât pe B cât și pe C, el este un divizor comun al lui B și C.
CMMDC(A,B) trebuie să fie mai mic sau egal cu CMMDC(B,C) deoarece CMMDC(B,C) este „cel mai mare” divizor comun al lui B și C.
- CMMDC(B,C), prin definiție, divide pe B.
- Am demonstrat că CMMDC(B,C) divide pe A.
- Deoarece CMMDC(B,C) divide atât pe A cât și pe B, el este un divizor comun al lui A și B.
CMMDC(B,C) trebuie să fie mai mic sau egal cu CMMDC(A,B) deoarece CMMDC(A,B) este „cel mai mare” divizor comun al lui A și B.
Dacă CMMDC(A,B)≤CMMDC(B,C) și CMMDC(B,C)≤CMMDC(A,B), putem concluziona că:
CMMDC(A,B)=CMMDC(B,C)
Care este echivalent cu:
CMMDC(A,B)=CMMDC(B,A-B)
O ilustrație a acestei demonstrații se poate observa în partea dreaptă a figurii de mai jos.
Demonstrăm că CMMDC(A,B)=CMMDC(B,R)
Am demonstrat că CMMDC(A,B)=CMMDC(B,A-B)
Ordinea termenilor nu contează, deci putem spune că CMMDC(A,B)=CMMDC(A-B,B)
Putem aplica, în mod repetat, CMMDC(A,B)=CMMDC(A-B,B) pentru a obține:
CMMDC(A,B)=CMMDC(A-B,B)=CMMDC(A-2B,B)=CMMDC(A-3B,B)=...=CMMDC(A-Q⋅B,B)
Dar, A= B⋅Q + R , deci A-Q⋅B=R
Astfel CMMDC(A,B)=CMMDC(R,B)
Ordinea termenilor nu contează, astfel:
CMMDC(A,B)=CMMDC(B,R)
Vrei să te alături conversației?
Nici o postare încă.