Quadratic Residue
Let and we say that is a quadratic residue when the congruence has a solution, we define the collection of quadratic residues as
Being a quadratic residue means "you have a square root"
Eulers Criterion
Let
and
such that
then
is a
quadratic residue if and only if
Legendre Symbol
Let and , then we define the legendre symbol as:
Quadratic Residue iff Legendre Symbol is One
Let and then if and only if there is some such that
Quadratic Residues mod p Come in Pairs
Let , and suppose that is a solution to then there are exactly 2 solutions to this equation given by
Clearly if is a solution then so is because . These solutions are indeed unique as they would be the same iff which is impossible as that would imply that and , therefore it must be that , now and since is even, then it's impossible that (which implies that is even), therefore we must have that and therefore so these two solutions are distinct solutions.
Suppose there were another solution given by so that , then we have and so we deduce that or which is to say that either or which means that any other solution is congruent to one of , therefore we conclude that there are exactly two solutions.
Half of them are Quadratic Resides and the Rest Aren't
Let prove that
Because every prime has a primitive root
Quadratic Residue with a Composite Modulus
Let be the prime factorization of , then has a solution if and only if for every has a solution
Supposing we had a solution to , then these would also be solutions to for any
So now suppose that we have a solution for each of the individual call each solution instance , now setup a new system for each as by applying the crt we obtain a solution to this system which is unique mod , moreover .
Now we do chinese remainder theorem one last time, but focus on it's uniqueness requirement, the system has a unique solution mod , but from before we know that and both solve this system, so we must have that so that we have a solution, as needed.
When a Quadratic Congruence has a Solution mod p Squared
Let and , then has solutions if and only if
Suppose that we have a solution so that then thus
Now suppose that therefore we have a solution to therefore for some we have that if then and we would be done, so in the other case when then we will have to find a new solution to the equation, consider , let's see if we can construct a solution using this form. If we attempt this solution we see that Note that , so now we require an such that but recall that thus thus for if it were not the case then we would have which would be a contradiction as , this shows that has an inverse, similarly has an inverse as since so therefore we have and thus we can always find a value of that will work, meaning is a solution to as needed.
Obtaining a Solution to a Quadratic Congrugence mod p Squared from a Solution mod p
Suppose that
is a solution to
so that
for some
, then
- (where ) is a solution to
A Quadratic Equation mod p Squared has 2 Solutions if the Legendre Symbol is One and None if Minus One
has precisely 2 solutions if and no solutions if
Suppose that
and that
are both solutions to
such that
, so that
and
for some
. Since
then we also have
so that
note that if we had that
then
because
, therefore
, moreover since
, then we can see that
so they can be
cancelled to obtain that
so that
We've just shown that given two congruent solutions to then they are also congruent solutions to which by the contrapositive shows that if we have two incongruent solutions to then they must also be incongruent mod .
Since then we have a solution to and and therefore it has exactly two solutions.
Solutions to 2783
Find all incongruent solutions to where
Recall
A Number is a Solution of a Quadratic Equation mod a Power of 2 iff a Power of 2 Minus the Number is as well
Let and then is a solution of iff is also a solution.
Only Numbers Congruent to 1 mod 8 Have Quadratic Residues mod a Power of 2
Let and then has a solution iff
A Quadratic Congruence mod a Power of 2 has 4 Solutions
Let and then there are exactly 4 incongruent solutions to