Definiții
Fie
și ;- dacă
și , atunci .
Cel mai mare divizor comun al numerelor
Dacă
Proprietăți cmmdc
Cel mai mare divizor comun al numerelor naturale are proprietățile:
Determinarea celui mai mare divizor comun
Cel mai mare divizor comun al două numere naturale n
și m
poate fi determinat folosind descompunerea în factori primi a celor două numere. Această metodă este mai dificil de implementat. Există o metodă mai simplu de implementat într-un program, numită algoritmul lui Euclid.
Sunt două variante ale algoritmului lui Euclid: cu scăderi și cu împărțiri.
Algoritmul lui Euclid cu scăderi
Algoritmul lui Euclid cu scăderi se bazează pe ideea că cele mai mare divizor a două numere divide și diferența acestora. Algoritmul este:
- Cât timp numerele sunt diferite, se scade numărul mai mic din numărul mai mare.
- Când numerele devin egale, valoare comună este cel mai mare divizor comun al valorilor inițiale.
- Algoritmul nu poate fi aplicat dacă unul dintre numere este
0
. De ce?
Exemplu:
- Fie
n=32
șim=24
. - Numerele nu sunt egale, scădem numărul mai mic din numărul mai mare,
n = n - m = 32 - 24 = 8
. - Acum
n = 8
șim = 24
. - Numerele nu sunt egale, scădem numărul mai mic din numărul mai mare,
m = m - n = 24 - 8 = 16
. - Acum
n = 8
șim =16
. - Numerele nu sunt egale, scădem numărul mai mic din numărul mai mare,
m = m - n = 16 - 8 = 8
. - Acum
n = 8
șim = 8
. - Numerele sunt egale. Valoarea comună,
8
, este cel mai mare divizor comun al valorilor inițiale,32
și24
Program C++:
int main() { int n , m; std :: cin >> n >> m; while(n != m) if(n > m) n -= m; else m -= n; std :: cout << n << std :: endl; return 0; }
Algoritmul lui Euclid cu împărțiri
Algoritmul lui Euclid cu împărțiri se bazează pe ideea că cel mai mare divizor a două numere divide și restul împărțirii acestora, conform teoremei împărțirii cu rest. Algoritmul este:
- Cât timp
m != 0
:- Determinăm restul împărțirii lui
n
lam
. - În continuare
n
devinem
, iarm
devine restul calculat.
- Determinăm restul împărțirii lui
- Valoarea actuală a lui
n
este cel mai mare divizor comun a valorilor inițiale.
Exemplu:
- Fie
n=32
șim=24
. m != 0
:- Calculăm
r = n % m = 8
n
devinem
, iarm
deviner
.
- Calculăm
- Acum
n=24
șim=8
. m != 0
:- Calculăm
r = n % m = 0
n
devinem
, iarm
deviner
.
- Calculăm
- Acum
n=8
șim=0
. m
este0
. Valoarea actuală a luin = 8
este cel mai mare divizor comun al valorilor inițiale,32
și24
.
Program C++:
int main() { int n , m; std :: cin >> n >> m; while(m != 0) { int r = n % m; n = m; m = r; } std :: cout << n << std :: endl; return 0; }
Determinarea cmmdc pentru mai multe numere
Pentru a determina cel mai mare divizor comun a mai multor numere:
- determinăm cmmdc dintre primele două numere.
- determinăm cmmdc între cmmdc anterior și al treilea număr.
- determinăm cmmdc între cmmdc anterior și al patrulea număr.
- ș.a.m.d.
Cel mai mic multiplu comun
Fie
Cel mai mic multiplu comun al numerelor
Determinarea cmmmc
Pentru a determina cel mai mic multiplu comun se pot folosi mai multe metode:
Determinarea cmmmc folosind cmmdc
Determinarea cmmmc folosind un algoritm de tip Euclid
Fie a
și b
valorile date. Vom construi valorile m
și n
, astfel:
- inițial
n ← a
,m ← b
; - cât timp
m ≠ n
:- dacă
n < m
, atuncin
crește cu valoarea luia
:n ← n + a
- dacă
n > m
, atuncim
crește cu valoarea luib
:m ← m + b
- dacă
- valoarea finală, comună, a lui
n
șim
este cel mai mic multiplu comun pentrua
șib
Observație: Algoritmul poate fi aplicat similar pentru trei sau mai multe numere!
Aplicații ale cmmmc
Deja știți că pentru a aduna două (sau mai multe) fracții trebuie să le aducem la același numitor, iar cel mai mic numitor comun a două fracții este egal cu cel mai mic multiplu comun al numitorilor.
Urmează alte două aplicații mai practice ale CMMMC.
Problema roților dințate
Se dă un angrenaj format din două roți dințate conectate. Prima are n
dinți, a doua are m
dinți. Între centrele celor două roți este trasată o linie colorată. Rotile încep să se miște. După câte rotații ale primei roți linia colorată va uni din nou centrele roților?
Răspunsul se determină folosind cel mai mic multiplu comun:
Alinierea planetelor
Considerăm trei planete care se rotesc în jurul soarelui. Ele fac rotație completă în
Răspunsul este