Page 43 - MATINF Nr. 11-12

Algoritmul extins al lui Euclid 43

if(a>0 && b>0) return _cmmdcExtinsR (a,b,m,n);
if(a<0 && b <0){d= _cmmdcExtinsR (-a,-b,m,n); m=-m;n=-n; return d;}
if(a <0){d=_cmmdcExtinsR (-a,b,m,n); m=-m; return d;}
d= _cmmdcExtinsR(a,-b,m,n); n=-n; return d;
}

4 Aplicatie. Rezolvarea ecuatiei liniare diofantice ax + by = c
,
,
a
S˘ se determine solut , ia general˘a a ecuat , iei diofantice

a · x + b · y = c, a, b, c ∈ Z. (7)

Solut ,ie. Fie d = (a, b). Ecuat , ia (7) are solut , ii dac˘a s , i numai dac˘a d|c.
ˆ
Intr-adev˘ar, dac˘a exist˘a x 0 , y 0 astfel ˆıncˆat a · x 0 + b · y 0 = c, cum d = (a, b) ⇒ d|a, d|b deci
d|a · x 0 + b · y 0 = c.

Dac˘a d|c ⇒ (∃) q astfel ˆıncˆat c = q · d. Cum d = (a, b) ⇒ (∃) m, n ∈ Z astfel ˆıncˆat
d = m · a + n · b ⇒ q · d = q · m · a + q · n · b ⇒ perechea (q · m, q · n) este solut , ie a ecuat , iei (7).
Fie perechea (x 0 , y ) o solut , ie particular˘ s , i perechea (x, y) o solut , ie oarecare pentru ecuat , ia
a
0
(7).
a
Avem a · x 0 + b · y 0 = c, a · x + b · y = c s , i deducem c˘ a (x − x 0 ) = −b(y − y 0 ).
a b
Å ã
Cum d = (a, b) ⇒ , = 1.
d d
a b b b
Deoarece · (x − x 0 ) = − · (y − y 0 ) ⇒ | (x − x 0 ) ⇒ x − x 0 = − · t ⇒
d d d d
b a
x = x 0 − · t, y = y 0 + · t, t ∈ Z.
d d

Implementarea acestui algoritm este urm˘atoarea:
#include <iostream>
#include<cmath>

using namespace std;

int _cmmdcExtins (int a, int b,int &m, int &n) ///a>0,b>=0
{
if ( b== 0) { m = 1; n = 0; return a; }
int d = _cmmdcExtins (b,a % b, n, m);
n=n-(a/b)*m;
return d;
}

int cmmdcExtins(int a,int b, int &m, int &n)
{
int d;
if(b==0) { m=1; n=0; return a;}