In mathematics, a
congruence is an
equivalence relation on the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s. 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
In algebra and number theory, Wilson's theorem states that a natural number ''n'' > 1 is a prime number if and only if the product of all the positive integers less than ''n'' is one less than a multiple of ''n''. That is (using the notations of m ...
, 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
In algebra and number theory, Wilson's theorem states that a natural number ''n'' > 1 is a prime number if and only if the product of all the positive integers less than ''n'' is one less than a multiple of ''n''. That is (using the notations of m ...
stated in terms of the
hyperfactorials,
subfactorials, and
superfactorials are given in.
Variants of Wilson's theorem
For integers
, we have the following form of Wilson's theorem:
:
If
is odd, we have that
:
Clement's theorem concerning the twin primes
Clement's congruence-based theorem characterizes the
twin primes pairs of the form
through the following conditions:
:
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
:
Characterizations of prime tuples and clusters
The prime pairs of the form
for some
include the special cases of the
cousin primes (when
) and the
sexy primes
In number theory, sexy primes are prime numbers that differ from each other by 6. For example, the numbers 5 and 11 are both sexy primes, because both are prime and .
The term "sexy prime" is a pun stemming from the Latin word for six: .
If o ...
(when
). 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
:
and the alternate characterization when
is odd such that
given by
:
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 (see, for example, Section 3.3 in
).
References
{{Reflist
Congruences
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
Modular arithmetic