which may furthermore be written as
Accordingly, one can obtain the the solution of the given congruence from the solution of the pair of congruences
Case 1: is a quadratic residue. Then (2) has a root , and therefore also the second root . The roots are incongruent, because otherwise one had
and thus which is not possible in this case.
Case 2: . Now (2) implies that , whence the corresponding root of the linear congruence (3) does not allow other incongruent roots for (1).
Case 3: is a quadratic nonresidue. The congruence (2) cannot have solutions; the same concerns thus also (1).
Example. Solve the congruence
We have and the Legendre symbol
(see values of the Legendre symbol) says that is a quadratic residue modulo 43. The congruence corresponding (2) is
which is satisfied by as one finds after a little experimenting. Then we have the two linear congruences , i.e.
corresponding (3). The first of them, , is satisfied by and the second, , by . Thus the solution of the given congruence is
|Date of creation||2013-03-22 17:45:30|
|Last modified on||2013-03-22 17:45:30|
|Last modified by||pahio (2872)|