Divizibilitate / Algoritmul lui Euclid


Etichete: nicio etichetă

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

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

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

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 ș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:

  • Cât timp m != 0:
    • Determinăm restul împărțirii lui n la m.
    • În continuare n devine m, iar m devine restul calculat.
  • Valoarea actuală a lui n este cel mai mare divizor comun a valorilor inițiale.

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;
}

Cel mai mic multiplu comun

Pentru a determina cel mai mic multiplu comun a două numere naturale folosim următoarea observație:

Produsul a două numere naturale este egal cu produsul dintre cel mai mare divizor comun al lor și cel mai mic multiplu comun al lor.
n * m = cmmdc * cmmmc

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.

Vezi și: