Proof.
First we prove
![$ (i)$](img8.png)
.
If
![$ (s_0, t_0) \in R^2$](img13.png)
is a solution of Equation (
2),
then
![$ h$](img9.png)
which divides
![$ s_0 f + t_0 g$](img21.png)
, divides also
![$ a$](img10.png)
.
Conversly, we assume that
![$ h = {\gcd}(f,g)$](img6.png)
divides
![$ a$](img10.png)
.
The claim is trivial if
![$ h = 0$](img22.png)
. (Indeed, this implies
![$ f = g = 0$](img23.png)
and also
![$ a = 0$](img24.png)
.)
Otherwise, let
![$ (s_0, t_0) \in R^2$](img13.png)
be computed by the Extended Euclidean Algorithm
applied to
![$ (f, g)$](img25.png)
, such that we have
![$ s_0 f + t_0 g = h$](img26.png)
.
Then
![$ (s, t) = (s_0 a / h, t_0 a / h)$](img27.png)
is a solution of
Equation (
2).
Now we prove
. Assume
and let
is a solution of
Equation (2).
Since
, then
and
are coprime.
Let
be in
.
Then we have
Finally, we prove
![$ (iii)$](img15.png)
. Let
![$ (s_1, t_1) \in R^2$](img33.png)
be a solution of
Equation (
2).
Let
![$ q$](img34.png)
and
![$ t_0$](img35.png)
be the quotient and the remainder of
![$ t_1$](img36.png)
w.r.t.
![$ f / h$](img28.png)
.
Hence we have
![$\displaystyle t_1 = f/h q + t_0 \ \ {\rm and} \ \ {\deg} t_0 < {\deg} f - {\deg} h.$](img37.png) |
(6) |
We define
![$\displaystyle s_0 = s_1 + q g / h.$](img38.png) |
(7) |
Observe that
solves Equation (
2) too.
By Relation (
6) and by hypothesis we have
leading to
Therefore we have
This proves the existence. Let us prove the unicity.
Let
![$ (s, t)$](img30.png)
be a solution of Equation (
2).
We know that there exists
![$ r \in R$](img43.png)
such that
![$ s = s_0 + r g / h$](img44.png)
.
Since
![$ {\deg} s_0 < {\deg} g - {\deg} h$](img45.png)
holds, if
![$ r \neq 0$](img46.png)
, we have
This implies the uniquemess.