- Source: Table of congruences
In mathematics, a congruence is an equivalence relation on the integers. The following sections list important or interesting prime-related congruences.
Table of congruences characterizing special primes
Other prime-related congruences
There are other prime-related congruences that provide necessary and sufficient conditions on the primality of certain subsequences of the natural numbers.
Many of these alternate statements characterizing primality are related to Wilson's theorem, or are restatements of this classical result given in terms of other
special variants of generalized factorial functions. For instance, new variants of Wilson's theorem stated in terms of the
hyperfactorials, subfactorials, and superfactorials are given in.
= Variants of Wilson's theorem
=For integers
k
≥
1
{\displaystyle k\geq 1}
, we have the following form of Wilson's theorem:
(
k
−
1
)
!
(
p
−
k
)
!
≡
(
−
1
)
k
(
mod
p
)
⟺
p
prime.
{\displaystyle (k-1)!(p-k)!\equiv (-1)^{k}{\pmod {p}}\iff p{\text{ prime. }}}
If
p
{\displaystyle p}
is odd, we have that
(
p
−
1
2
)
!
2
≡
(
−
1
)
(
p
+
1
)
/
2
(
mod
p
)
⟺
p
an odd prime.
{\displaystyle \left({\frac {p-1}{2}}\right)!^{2}\equiv (-1)^{(p+1)/2}{\pmod {p}}\iff p{\text{ an odd prime. }}}
= Clement's theorem concerning the twin primes
=Clement's congruence-based theorem characterizes the twin primes pairs of the form
(
p
,
p
+
2
)
{\displaystyle (p,p+2)}
through the following conditions:
4
[
(
p
−
1
)
!
+
1
]
≡
−
p
(
mod
p
(
p
+
2
)
)
⟺
p
,
p
+
2
are both prime.
{\displaystyle 4[(p-1)!+1]\equiv -p{\pmod {p(p+2)}}\iff p,p+2{\text{ are both prime. }}}
P. A. Clement's original 1949 paper provides a
proof of this interesting elementary number theoretic criteria for twin primality based on Wilson's theorem.
Another characterization given in Lin and Zhipeng's article provides that
2
(
p
−
1
2
)
!
2
+
(
−
1
)
p
−
1
2
(
5
p
+
2
)
≡
0
⟺
p
,
p
+
2
are both prime.
{\displaystyle 2\left({\frac {p-1}{2}}\right)!^{2}+(-1)^{\frac {p-1}{2}}(5p+2)\equiv 0\iff p,p+2{\text{ are both prime. }}}
= Characterizations of prime tuples and clusters
=The prime pairs of the form
(
p
,
p
+
2
k
)
{\displaystyle (p,p+2k)}
for some
k
≥
1
{\displaystyle k\geq 1}
include the special cases of the cousin primes (when
k
=
2
{\displaystyle k=2}
) and the sexy primes (when
k
=
3
{\displaystyle k=3}
). We have elementary congruence-based characterizations of the primality of such pairs, proved for instance in the article. Examples of congruences characterizing these prime pairs include
2
k
(
2
k
)
!
[
(
p
−
1
)
!
+
1
]
≡
[
1
−
(
2
k
)
!
]
p
(
mod
p
(
p
+
2
k
)
)
⟺
p
,
p
+
2
k
are both prime,
{\displaystyle 2k(2k)![(p-1)!+1]\equiv [1-(2k)!]p{\pmod {p(p+2k)}}\iff p,p+2k{\text{ are both prime, }}}
and the alternate characterization when
p
{\displaystyle p}
is odd such that
p
⧸
∣
(
2
k
−
1
)
!
!
2
{\displaystyle p\not {\mid }(2k-1)!!^{2}}
given by
2
k
(
2
k
−
1
)
!
!
2
(
p
−
1
2
)
!
2
+
(
−
1
)
p
−
1
2
[
(
2
k
−
1
)
!
!
2
(
p
+
2
k
)
−
(
−
4
)
k
⋅
p
]
≡
0
⟺
p
,
p
+
2
k
are both prime.
{\displaystyle 2k(2k-1)!!^{2}\left({\frac {p-1}{2}}\right)!^{2}+(-1)^{\frac {p-1}{2}}\left[(2k-1)!!^{2}(p+2k)-(-4)^{k}\cdot p\right]\equiv 0\iff p,p+2k{\text{ are both prime. }}}
Still other congruence-based characterizations of the primality of triples, and more general prime clusters (or prime tuples) exist and are typically proved starting from Wilson's theorem.).
References
Kata Kunci Pencarian:
- Table of congruences
- Congruence relation
- Fermat's little theorem
- Wilson prime
- Modular arithmetic
- Wilson's theorem
- Wolstenholme's theorem
- Wall–Sun–Sun prime
- Semigroup
- Glossary of mathematical symbols
