x Squared is Congruent to 1 iff x is Congruent to Plus or Minus One Mod p
⟹
Suppose that
x
2
≡
1
(
mod
p
)
therefore
p
∣
x
2
−
1
=
(
x
+
1
)
(
x
−
1
)
therefore
p
∣
(
x
+
1
)
or
p
∣
(
x
−
1
)
so that
x
≡
±
1
(
mod
p
)
⟸
Suppose that
x
≡
±
1
(
mod
p
)
therefore
x
2
≡
1
(
mod
p
)
as needed.
Quadratic's Little
Let
p
∈
P
3
and prove that for any
a
∈
Z
such that
p
∤
a
we have
a
p
−
1
2
≡
±
1
(
mod
p
)
Note that since
p
∤
a
we have that
a
p
−
1
≡
1
(
mod
p
)
since
p
−
1
is even, then
2
divides it so that
p
−
1
2
∈
Z
, therefore we have
(
a
p
−
1
2
)
2
≡
1
therefore
a
p
−
1
2
≡
±
1
(
mod
p
)
Number of Solutions to x Squared Congruent to Minus One Mod p
The equation
x
2
≡
(
−
1
)
(
mod
p
)
has two solutions explicitly given by
±
(
p
−
1
2
)
!
(which are incongruent mod
p
) iff
p
=
4
k
+
1
⟹
Suppose that
x
2
≡
−
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
[
(
p
−
1
2
)
!
]
2
≡
(
−
1
)
4
k
+
3
+
1
2
≡
1
(
mod
p
)
which is a contradiction because if
p
=
4
k
+
3
then
p
≥
3
therefore
−
1
≢
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
[
(
p
−
1
2
)
!
]
2
≡
(
−
1
)
4
k
+
1
+
1
2
≡
−
1
(
mod
p
)
We'll prove that these two solutions are incongruent, first note that since
p
≥
2
then we know that
k
≥
1
therefore we know that
p
≥
5
1
≤
p
−
1
2
<
p
therefore
p
∤
(
p
−
1
2
)
!
, thus
(
p
−
1
2
)
!
has an inverse, so then if they happened to be congruent we have
(
p
−
1
2
)
!
≡
−
(
p
−
1
2
)
!
(
mod
p
)
which implies that
1
≡
−
1
(
mod
p
)
which is a contradiction since
p
≥
5
therefore we must have that
(
p
−
1
2
)
!
≢
−
(
p
−
1
2
)
!
(
mod
p
)
Incongruent mod 37
Obtain all incongruent solutions to the quadratic congruence
x
2
≡
−
1
(
mod
37
)
By the above we know that
±
18
!
works.
a Squared b Squared
Suppose that
p
∈
P
3
and that
p
∣
a
2
+
b
2
such that
a
,
b
∈
Z
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
≡
−
b
2
(
mod
p
)
then we would be able to say that
−
1
≡
(
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
)
≥
p
which is a contradiction, therefore
p
∤
a
, as needed.
Number of Solutions to a Quadratic Congruence
x
2
≡
1
(
mod
p
α
)
- has two solutions if
p
is odd