0 0
|

== include(page="template/taskfooter" task_id="euclid3") ==
 
h3. Indicatii de rezolvare

h2. Indicatii de rezolvare

Ecuatiile pot fi rezolvate cu ajutorul algoritmului lui Euclid extins, prezentat in acest "articol":algoritmul-lui-euclid de pe infoarena. Astfel se poate determina perechea $(x y)$ care satisface relatia $a * x + b * y = d$, unde $d$ este $cmmmdc(a, b)$. In cazul in care $c$ nu se divide cu $d$ ecuatia nu poate fi rezolvata in multimea numerelor intregi, in caz contrar se inmulteste intreaga ecuatie cu $c / d$.

Ca o completare: Pentru fiecare ecuatie exista o infinitate de solutii. Avand dat $a * x + b * y = c$, se observa ca toate solutiile de forma $(x + k * b/d, y - k * a/d)$, cu $k$ intreg respecta ecuatia.
Ecuatia devine $a * (x + k * b/d) + b * (y - k * a/d) = c$. Desfacand parantezele: $a * x + k * a * b / d + b * y - k * a * b / d = a * x + b * y$. Solutiile noi sunt la randul lor intregi, $a$ si $b$ fiind divizibile cu $d$.

 
== include(page="template/taskfooter" task_id="euclid3") ==
 
 

2761