ΘρϵηΠατπ

Quadratic Residue
Let n∈ℕ1 and c∈ℤ we say that c is a quadratic residue when the congruence x2≡c(modn) has a solution, we define the collection of quadratic residues as QR⁡(n)

Being a quadratic residue means "you have a square root"

Eulers Criterion
Let p∈ℙ3 and c∈ℤ such that p∤c then c is a quadratic residue if and only if cp−12≡1(modp)
Legendre Symbol
Let p∈ℙ3 and c∈ℤ, then we define the legendre symbol as: leg⁡(c,p):={0 if p|c1 if p∤c and c∈QR⁡(n)−1 if p∤c and c∉QR⁡(n)
Quadratic Residue iff Legendre Symbol is One
Let c∈ℤ and p∈ℙ3 then leg⁡(c,p)=1 if and only if there is some x0∈ℤ such that x02≡c(modp)
Quadratic Residues mod p Come in Pairs
Let p∈ℙ3, c∈cop⁡(p) and suppose that x0∈ℤ is a solution to x2≡c(modp) then there are exactly 2 solutions to this equation given by ±x0

Clearly if x0 is a solution then so is −x0 because (−x0)2=x2≡c(modp). These solutions are indeed unique as they would be the same iff x0≡0(modp) which is impossible as that would imply that c≡0(modp) and c∈cop⁡(p), therefore it must be that x0≠0, now x0∈[1,…,p−1] and p−x0[1,…,p−1] since p−1 is even, then it's impossible that x0=p−x0 (which implies that p is even), therefore we must have that x0≠p−x0 and therefore x0≢p−x0≡−x0(modp) so these two solutions are distinct solutions.

Suppose there were another solution given by s so that s2≡c≡x02, then we have x02−s2≡0⟺(x0+s)(x0−s)≡0(modp) and so we deduce that p|x0+s or p|x0−s which is to say that either s≡−x0(modp) or s≡x0(modp) which means that any other solution is congruent to one of x0,−x0, therefore we conclude that there are exactly two solutions.

Half of them are Quadratic Resides and the Rest Aren't
Let p∈ℙ3 prove that |{c∈[1,…,p−1]:leg⁡(c,p)=1}|=|{c∈[1,…,p−1]:leg⁡(c,p)=−1}|
Because every prime has a primitive root
Quadratic Residue with a Composite Modulus
Let n=∏i=1lpiαi be the prime factorization of n∈ℕ2, then x2≡c(modn) has a solution if and only if for every i∈[1,…,l] x2≡c(modpiαi) has a solution

Supposing we had a solution to x2≡c(modn) , then these would also be solutions to x2≡c(modpiαi) for any i∈[1,…,l]

So now suppose that we have a solution for each of the individual x2≡c(modpiαi) call each solution instance si, now setup a new system for each i∈[1,…,l] as y≡si(modpiαi) by applying the crt we obtain a solution x‾ to this system which is unique mod n, moreover x‾2≡si2(modpiαi).

Now we do chinese remainder theorem one last time, but focus on it's uniqueness requirement, the system z≡si2(modpiαi) has a unique solution mod n, but from before we know that c and x‾ both solve this system, so we must have that x‾2≡c(modn) so that we have a solution, as needed.

When a Quadratic Congruence has a Solution mod p Squared
Let p∈ℙ3 and c∈cop⁡(p), then x2≡c(modp2) has solutions if and only if leg⁡(c,p)=1

⟹ Suppose that we have a solution x0 so that x02≡c(modp2) then x02≡c(modp) thus leg⁡(c,p)=1

⟸ Now suppose that leg⁡(c,p)=1 therefore we have a solution x0∈ℤ to x2≡c(modp) therefore for some m∈ℤ we have that x02=mp+c if p|m then x02≡c(modp) and we would be done, so in the other case when p∤m then we will have to find a new solution to the equation, consider y0=x0+np, let's see if we can construct a solution using this form. If we attempt this solution we see that (x0+np)2=x02+2np+n2p2≡x02+2np≡c+mp+2x0np(modp2) Note that m+2x0np=p(m+2x0n), so now we require an n such that 2x0+m≡0(modp) but recall that leg⁡(c,p)=1 thus c∈cop⁡(p) thus x0∈cop⁡(n) for if it were not the case then we would have c∉cop⁡(p) which would be a contradiction as x02≡c(modp), this shows that x0 has an inverse, similarly 2 has an inverse as 2∈cop⁡(p) since p∈ℙ3 so therefore we have 2x0n+m≡0(modp)⟺n≡−m(2x0)−1 and thus we can always find a value of n that will work, meaning y0=x0+np is a solution to x2≡c(modp) as needed.

Obtaining a Solution to a Quadratic Congrugence mod p Squared from a Solution mod p
Suppose that x0 is a solution to x2≡c(modp) so that x02=mp+c for some m∈ℤ, then
  • x0+αp (where α≡(−m)(2x0)−1(modp) ) is a solution to x2≡c(modp2)
A Quadratic Equation mod p Squared has 2 Solutions if the Legendre Symbol is One and None if Minus One
x2≡c(modp) has precisely 2 solutions if leg⁡(c,p)=1 and no solutions if leg⁡(c,p)=−1
Suppose that leg⁡(c,p)=1 and that x0,y0inℤ are both solutions to x2≡c(modp) such that x0≡y0(modp), so that x0=k+mp and y0=k+np for some k,m,n∈ℤ. Since x02≡c≡y02(modp2) then we also have x02≡(k+mp)2≡k2+2kmp+m2p2≡k2+2knp+n2p2≡(k+np)2≡y02(modp2) so that 2kmp≡2knp(modp2) note that if we had that k∉cop⁡(n) then c∉cop⁡(n) because c≡x02≡k2+2kmp, therefore k∈cop⁡(n) , moreover since 2∈cop⁡(p), then we can see that 2k∈cop⁡(p) so they can be cancelled to obtain that mp≡np(modp2) so that x0=k+mp≡k+mp=y0(modp)

We've just shown that given two congruent solutions to x2≡c(modp) then they are also congruent solutions to x2≡c(modp2) which by the contrapositive shows that if we have two incongruent solutions to x2≡c(modp)2 then they must also be incongruent mod p.

Since leg⁡(c,p)=1 then we have a solution to x2≡c(modp) and and therefore it has exactly two solutions.

Solutions to 2783
Find all incongruent solutions to x2≡3(mod2783) where 2783=112⋅23
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 c≡1(mod8) and k∈ℕ3 then x0 is a solution of x2≡c(mod2k) iff 2k−1−x0 is also a solution.
Only Numbers Congruent to 1 mod 8 Have Quadratic Residues mod a Power of 2
Let c∈ℤodd⁡ and k∈ℕ3 then x2≡c(mod2k) has a solution iff c≡1(mod8)
A Quadratic Congruence mod a Power of 2 has 4 Solutions
Let c≡1(mod8) and k∈ℕ3 then there are exactly 4 incongruent solutions to x2≡c(mod2k)