CMMDC și CMMMC. Algoritmul lui Euclid

Definiții

Fie \(a\) și \(b\) două numere naturale. Un număr natural \(d\) se numește cel mai mare divizor comun (pe scurt cmmdc) al lui \(a\) și \(b\) dacă îndeplinește condițiile:

1. \( d \vert a\) și \( d \vert b\);
2. dacă \( c \vert a\) și \( c \vert b\), atunci \( c \vert d\).

Cel mai mare divizor comun al numerelor \(a\) și \(b\) se notează \( (a,b) \) sau \(gcd(a,b)\) – greatest common divisor.

Dacă \( (a,b) = 1\), spunem că \(a\) și \(b\) sunt prime între ele sau relativ prime, sau că \(a\) este prim cu \(b\).

Proprietăți cmmdc

Cel mai mare divizor comun al numerelor naturale are proprietățile:

1. \( ((a,b),c) = (a,(b,c)), \forall a,b,c\in \mathbb{N} \)
2. \( (a,b) = 1 , (a,c) = 1 \Rightarrow (a,bc) = 1 \)
3. \( a | bc \text{ și } (a,b)= 1 \Rightarrow a \vert c \)
4. \( a \vert c, b \vert c \text{ și } (a,b)=1 \Rightarrow ab \vert c\)

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:

Exemplu:

• Fie n=32 și m=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 și m = 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 și m =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 și m = 8.
• Numerele sunt egale. Valoarea comună, 8, este cel mai mare divizor comun al valorilor inițiale, 32 și 24

Program C++:

#include <iostream>
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:

Exemplu:

• Fie n=32 și m=24.
• m != 0:
  • Calculăm r = n % m = 8
  • n devine m, iar m devine r.
• Acum n=24 și m=8.
• m != 0:
  • Calculăm r = n % m = 0
  • n devine m, iar m devine r.
• Acum n=8 și m=0.
• m este 0. Valoarea actuală a lui n = 8 este cel mai mare divizor comun al valorilor inițiale, 32 și 24.

Program C++:

#include <iostream>
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 \(a\) și \(b\) două numere naturale. De numește cel mai mic multiplu comun (pe scurt cmmmc) al lui \(a\) și \(b\) cel mai mic număr natural nenul cu proprietatea că se divide atât cu \(a\) cât și cu \(b\).

Cel mai mic multiplu comun al numerelor \(a\) și \(b\) se notează \( [a,b] \) sau \(lcm(a,b)\) – least common multiple.

Determinarea cmmmc

Pentru a determina cel mai mic multiplu comun se pot folosi mai multe metode:

Determinarea cmmmc folosind cmmdc

Observație: Produsul a două numere naturale nenule este egal cu produsul dintre cel mai mare divizor comun al lor și cel mai mic multiplu comun al lor. $$a \cdot b = (a,b) \cdot [a,b]$$ $$a \cdot b = gcd(a,b) \cdot lcm(a,b)$$

Determinarea cmmmc folosind un algoritm de tip Euclid

Fie a și b valorile date. Vom construi valorile m și n, astfel:

1. inițial n ← a, m ← b;
2. cât timp m ≠ n:
   • dacă n < m, atunci n crește cu valoarea lui a: n ← n + a
   • dacă n > m, atunci m crește cu valoarea lui b: m ← m + b
3. valoarea finală, comună, a lui n și m este cel mai mic multiplu comun pentru a și b

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: \( [n,m] \). Mai precis, prima roată va face \( \frac{[n,m]}{n} \) rotații iar a doua va face \( \frac{[n,m]}{m} \) rotații.

Alinierea planetelor

Considerăm trei planete care se rotesc în jurul soarelui. Ele fac rotație completă în \(a\), \(b\), respectiv \(c\) ani, numere naturale. Dacă la un moment dat planetele sunt aliniate (între ele și cu soarele), după cât timp vor din nou aliniate?

Răspunsul este \([a,b,c]\) ani. În acest ele vor face \(\frac{[a,b,c]}{a}\), \(\frac{[a,b,c]}{b}\), respectiv \(\frac{[a,b,c]}{c}\) rotații complete în jurul soarelui.