Quadratic Congruences

x Squared is Congruent to 1 iff x is Congruent to Plus or Minus One Mod p

x^{2} \equiv 1 (\mod p) ⟺ x \equiv \pm 1 (\mod p)

$⟹$ Suppose that $x^{2} \equiv 1 (\mod p)$ therefore $p | x^{2} - 1 = (x + 1) (x - 1)$ therefore $p | (x + 1)$ or $p | (x - 1)$ so that $x \equiv \pm 1 (\mod p)$

$⟸$ Suppose that $x \equiv \pm 1 (\mod p)$ therefore $x^{2} \equiv 1 (\mod p)$ as needed.

Quadratic's Little

Let

p \in ℙ_{3}

and prove that for any

a \in ℤ

such that

p ∤ a

we have

a^{\frac{p - 1}{2}} \equiv \pm 1 (\mod p)

Note that since

p ∤ a

we have that

a^{p - 1} \equiv 1 (\mod p)

since

p - 1

is even, then

2

divides it so that

\frac{p - 1}{2} \in ℤ

, therefore we have

{(a^{\frac{p - 1}{2}})}^{2} \equiv 1

therefore

a^{\frac{p - 1}{2}} \equiv \pm 1 (\mod p)

Number of Solutions to x Squared Congruent to Minus One Mod p

The equation

x^{2} \equiv (- 1) (\mod p)

has two solutions explicitly given by

\pm (\frac{p - 1}{2})!

(which are incongruent mod

p

) iff

p = 4 k + 1

$⟹$ Suppose that $x^{2} \equiv - 1 (\mod p)$ has two solutions as stated in the question, suppose for the sake of contradiction that $p = 4 k + 3$ , then we have ${[(\frac{p - 1}{2})!]}^{2} \equiv {(- 1)}^{\frac{4 k + 3 + 1}{2}} \equiv 1 (\mod p)$ which is a contradiction because if $p = 4 k + 3$ then $p \geq 3$ therefore $- 1 \equiv̸ 1 (\mod p)$ but that is implied as through the assumption and the fact we just noticed above.

$⟸$ Suppose that $p = 4 k + 1$ and recall that this means that ${[(\frac{p - 1}{2})!]}^{2} \equiv {(- 1)}^{\frac{4 k + 1 + 1}{2}} \equiv - 1 (\mod p)$ We'll prove that these two solutions are incongruent, first note that since $p \geq 2$ then we know that $k \geq 1$ therefore we know that $p \geq 5$ $1 \leq \frac{p - 1}{2} < p$ therefore $p ∤ (\frac{p - 1}{2})!$ , thus $(\frac{p - 1}{2})!$ has an inverse, so then if they happened to be congruent we have $(\frac{p - 1}{2})! \equiv - (\frac{p - 1}{2})! (\mod p)$ which implies that $1 \equiv - 1 (\mod p)$ which is a contradiction since $p \geq 5$ therefore we must have that $(\frac{p - 1}{2})! \equiv̸ - (\frac{p - 1}{2})! (\mod p)$

Incongruent mod 37

Obtain all incongruent solutions to the quadratic congruence

x^{2} \equiv - 1 (\mod 37)

By the above we know that

\pm 18!

works.

a Squared b Squared

Suppose that

p \in ℙ_{3}

and that

p | a^{2} + b^{2}

such that

a, b \in ℤ

are coprime, prove that

p

is of the form

4 k + 1

If it so happens that $a$ had an inverse mod $p$ (denoted by $c$ ) since we know that $a^{2} \equiv - b^{2} (\mod p)$ then we would be able to say that $- 1 \equiv {(b c)}^{2} (\mod p)$ and therefore $p$ is of the form $4 k + 1$ .

Therefore one just has to verify that $a$ is invertible mod $p$ , and actually if it was that $b$ was invertible then we could have symmetrically done the same. Recall that a number is invertible mod $p$ if $p ∤ a$ , so suppose for the sake of contradiction that $p | a$ therefore $p | a^{2}$ and since $p | a^{2} + b^{2}$ then $p | b^{2}$ but then $p | b$ and so $\gcd (a, b) \geq p$ which is a contradiction, therefore $p ∤ a$ , as needed.

Number of Solutions to a Quadratic Congruence

x^{2} \equiv 1 (\mod p^{α})

has two solutions if $p$ is odd