Page 34 - MATINF Nr. 13-14

34 V. P˘aun

Exemplu: x ≡ 2 (mod 4) s , i x ≡ 4 (mod 6).

Aici cmmdc(4, 6) = 2.

Verific˘am: 4 − 2 = 2, care este divizibil cu 2.
Deci avem solut , ie.

Pasul A: Scriem prima ecuat , ie sub form˘ liniar˘a: x = 4k + 2.
a
Pasul B: Introducem aceast˘ expresie ˆın a doua ecuatie: 4k + 2 ≡ 4 (mod 6).
a
Pasul C: Rezolv˘am pentru k: 4k ≡ 2 (mod 6).

Aceasta este o ecuat , ie liniar˘a de tipul ax ≡ b (mod m).
ˆ
Imp˘art , im totul la cmmdc(4, 6) = 2, avem 2k ≡ 1 (mod 3).
Pasul D: G˘asim inversul lui 2 modulo 3, care este 2:

k ≡ 1 ∗ 2 (mod 3), deci k = 3j + 2.
ˆ
Pasul E: Inlocuim k ˆınapoi ˆın expresia lui x: x = 4(3j + 2) + 2 = 12j + 8 + 2 = 12j + 10.
Rezultat: x ≡ 10 (mod 12) (unde 12 este cmmmc(4, 6)).

Implementare ˆın C++
#include <iostream>
using namespace std;

// Returneaza cmmdc(a, b)
long long cmmdc(long long a, long long b)
{
long long r;
while (b){r=a%b; a=b; b=r;}
return a;
}

// Returneaza cmmmc(a, b)
long long cmmmc(long long a, long long b)
{
return (a/cmmdc(a, b))*b; // Evita overflow
}

/*Algoritmul extins al lui Euclid rezolva urmatoarea problema:
determina d=cmmdc(a,b) si doi intregi m si n astfel incat m*a+n*b=d.
*/
long long euclidExtins(long long a, long long b, long long &m, long long &n)
{
if ( b== 0) { m = 1; n = 0; return a; }
int d = euclidExtins(b,a % b, n, m);
n=n-(a/b)*m;
return d;
}

// Gaseste inversul modular al lui a modulo m
// Returneaza 0 daca nu exista (cand cmmdc(a,m) != 1)