Proof.
First we prove

.
If

is a solution of Equation (
2),
then

which divides

, divides also

.
Conversly, we assume that

divides

.
The claim is trivial if

. (Indeed, this implies

and also

.)
Otherwise, let

be computed by the Extended Euclidean Algorithm
applied to

, such that we have

.
Then

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

. Let

be a solution of
Equation (
2).
Let

and

be the quotient and the remainder of

w.r.t.

.
Hence we have
 |
(6) |
We define
 |
(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

be a solution of Equation (
2).
We know that there exists

such that

.
Since

holds, if

, we have
This implies the uniquemess.