solution of
Theorem 1.
Given an integer , if there exist integers and such that
then one has
where and are integers such that divides .
Proof.
To begin, cross multiply to obtain
Since this involves setting a product equal to anotherproduct, we can think in terms of factorization. Toclarify things, let us pull out a common factor andwrite and , where is the greatestcommon factor and is relatively prime to . Then,cancelling a common factor of , our equation becomesthe following:
This is equivalent to
Since and are relatively prime, it follows that isrelatively prime to and that is relatively prime to as well. Hence, we must have that divides ,
Now we can obtain the general solution to the equation.Write with and relatively prime. Then,substituting into our equation and cancelling a and a, we obtain
so the solution to the original equation is
Using the definition of , this can be rewritten as
∎