ΘρϵηΠατπ

Quadratic Residue
Let n1 and c we say that c is a quadratic residue when the congruence x2c(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 p3 and c such that pc then c is a quadratic residue if and only if cp121(modp)
Legendre Symbol
Let p3 and c, then we define the legendre symbol as: leg(c,p):={0 if p|c1 if pc and cQR(n)1 if pc and cQR(n)
Quadratic Residue iff Legendre Symbol is One
Let c and p3 then leg(c,p)=1 if and only if there is some x0 such that x02c(modp)
Quadratic Residues mod p Come in Pairs
Let p3, ccop(p) and suppose that x0 is a solution to x2c(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=x2c(modp). These solutions are indeed unique as they would be the same iff x00(modp) which is impossible as that would imply that c0(modp) and ccop(p), therefore it must be that x00, now x0[1,,p1] and px0[1,,p1] since p1 is even, then it's impossible that x0=px0 (which implies that p is even), therefore we must have that x0px0 and therefore x0≢px0x0(modp) so these two solutions are distinct solutions.

Suppose there were another solution given by s so that s2cx02, then we have x02s20(x0+s)(x0s)0(modp) and so we deduce that p|x0+s or p|x0s which is to say that either sx0(modp) or sx0(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 p3 prove that |{c[1,,p1]:leg(c,p)=1}|=|{c[1,,p1]: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 n2, then x2c(modn) has a solution if and only if for every i[1,,l] x2c(modpiαi) has a solution

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

So now suppose that we have a solution for each of the individual x2c(modpiαi) call each solution instance si, now setup a new system for each i[1,,l] as ysi(modpiαi) by applying the crt we obtain a solution x to this system which is unique mod n, moreover x2si2(modpiαi).

Now we do chinese remainder theorem one last time, but focus on it's uniqueness requirement, the system zsi2(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 x2c(modn) so that we have a solution, as needed.

When a Quadratic Congruence has a Solution mod p Squared
Let p3 and ccop(p), then x2c(modp2) has solutions if and only if leg(c,p)=1

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

Now suppose that leg(c,p)=1 therefore we have a solution x0 to x2c(modp) therefore for some m we have that x02=mp+c if p|m then x02c(modp) and we would be done, so in the other case when pm 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+n2p2x02+2npc+mp+2x0np(modp2) Note that m+2x0np=p(m+2x0n), so now we require an n such that 2x0+m0(modp) but recall that leg(c,p)=1 thus ccop(p) thus x0cop(n) for if it were not the case then we would have ccop(p) which would be a contradiction as x02c(modp), this shows that x0 has an inverse, similarly 2 has an inverse as 2cop(p) since p3 so therefore we have 2x0n+m0(modp)nm(2x0)1 and thus we can always find a value of n that will work, meaning y0=x0+np is a solution to x2c(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 x2c(modp) so that x02=mp+c for some m, then
  • x0+αp (where α(m)(2x0)1(modp) ) is a solution to x2c(modp2)
A Quadratic Equation mod p Squared has 2 Solutions if the Legendre Symbol is One and None if Minus One
x2c(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 x2c(modp) such that x0y0(modp), so that x0=k+mp and y0=k+np for some k,m,n. Since x02cy02(modp2) then we also have x02(k+mp)2k2+2kmp+m2p2k2+2knp+n2p2(k+np)2y02(modp2) so that 2kmp2knp(modp2) note that if we had that kcop(n) then ccop(n) because cx02k2+2kmp, therefore kcop(n) , moreover since 2cop(p), then we can see that 2kcop(p) so they can be cancelled to obtain that mpnp(modp2) so that x0=k+mpk+mp=y0(modp)

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

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

Solutions to 2783
Find all incongruent solutions to x23(mod2783) where 2783=11223
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 c1(mod8) and k3 then x0 is a solution of x2c(mod2k) iff 2k1x0 is also a solution.
Only Numbers Congruent to 1 mod 8 Have Quadratic Residues mod a Power of 2
Let codd and k3 then x2c(mod2k) has a solution iff c1(mod8)
A Quadratic Congruence mod a Power of 2 has 4 Solutions
Let c1(mod8) and k3 then there are exactly 4 incongruent solutions to x2c(mod2k)