Table of congruences

Last updated November 24, 2023

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

$2^{p-1}\equiv 1{\pmod {p}}$	special case of Fermat's little theorem, satisfied by all odd prime numbers
$2^{p-1}\equiv 1{\pmod {p^{2}}}$	solutions are called Wieferich primes (smallest example: 1093)
$F_{n-\left({\frac {n}{5}}\right)}\equiv 0{\pmod {n}}$	satisfied by all prime numbers
$F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p^{2}}}$	solutions are called Wall–Sun–Sun primes (no examples known)
${2n-1 \choose n-1}\equiv 1{\pmod {n^{3}}}$	by Wolstenholme's theorem satisfied by all prime numbers greater than 3
${2p-1 \choose p-1}\equiv 1{\pmod {p^{4}}},$	solutions are called Wolstenholme primes (smallest example: 16843)
$(n-1)!\ \equiv \ -1{\pmod {n}}$	by Wilson's theorem a natural number n is prime if and only if it satisfies this congruence
$(p-1)!\ \equiv \ -1{\pmod {p^{2}}}$	solutions are called Wilson primes (smallest example: 5)
$4[(p-1)!+1]\ \equiv \ -p{\pmod {p(p+2)}}$	solutions are the twin 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.^[1]

Variants of Wilson's theorem

For integers $k\geq 1$ , we have the following form of Wilson's theorem:

(k-1)!(p-k)!\equiv (-1)^{k}{\pmod {p}}\iff p{\text{ prime. }}

If $p$ is odd, we have that

\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)$ through the following conditions:

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 ^[2] 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\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+2k)$ for some $k\geq 1$ include the special cases of the cousin primes (when $k=2$ ) and the sexy primes (when $k=3$ ). We have elementary congruence-based characterizations of the primality of such pairs, proved for instance in the article.^[3] Examples of congruences characterizing these prime pairs include

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$ is odd such that $p\not {\mid }(2k-1)!!^{2}$ given by

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 (see, for example, Section 3.3 in ^[4]).

Related Research Articles

<span class="mw-page-title-main">Quadratic reciprocity</span> Gives conditions for the solvability of quadratic equations modulo prime numbers

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

In number theory, Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$ , the number $a p - a$ is an integer multiple of $p$ . In the notation of modular arithmetic, this is expressed as

In mathematics, a Fermat number, named after Pierre de Fermat, the first known to have studied them, is a positive integer of the form

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.

In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,

The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.

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, the factorial $satisfies$

In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.

In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that n is prime.

In mathematics, and more specifically number theory, the hyperfactorial of a positive integer $is the product of the numbers of the form from to .$

In mathematics, and more specifically number theory, the superfactorial of a positive integer $is the product of the first factorials. They are a special case of the Jordan-Pólya numbers, which are products of arbitrary collections of factorials.$

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 (see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially an Euler–Jacobi probable prime test.

Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.

In mathematics, Wolstenholme's theorem states that for a prime number $, the congruence$

<span class="mw-page-title-main">Carmichael function</span> Function in mathematical number theory

In number theory, a branch of mathematics, the Carmichael function $λ (n)$ of a positive integer $n$ is the smallest positive integer $m$ such that

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

In number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusually large number of proofs. Several hundred proofs of the law of quadratic reciprocity have been published.

Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x⁴ ≡ p is solvable; the word "reciprocity" comes from the form of some of these theorems, in that they relate the solvability of the congruence x⁴ ≡ p to that of x⁴ ≡ q.

In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as

References

↑ Aebi, Christian; Cairns, Grant (May 2015). "Generalizations of Wilson's Theorem for Double-, Hyper-, Sub- and Superfactorials". The American Mathematical Monthly. 122 (5): 433–443. doi:10.4169/amer.math.monthly.122.5.433. JSTOR 10.4169/amer.math.monthly.122.5.433. S2CID 207521192.
↑ Clement, P. A. (1949). "Congruences for sets of primes". Amer. Math. Monthly. 56 (1): 23–25. doi:10.2307/2305816. JSTOR 2305816.
↑ C. Lin and L. Zhipeng (2005). "On Wilson's theorem and Polignac conjecture". Math. Medley. 6. arXiv: math/0408018 . Bibcode:2004math......8018C.
↑ Schmidt, M. D. (2017). "New Congruences and Finite Difference Equations for Generalized Factorial Functions". arXiv: 1701.04741 . Bibcode:2017arXiv170104741S.{{cite journal}}: Cite journal requires |journal= (help)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Aebi, Christian; Cairns, Grant (May 2015). "Generalizations of Wilson's Theorem for Double-, Hyper-, Sub- and Superfactorials". The American Mathematical Monthly. 122 (5): 433–443. doi:10.4169/amer.math.monthly.122.5.433. JSTOR 10.4169/amer.math.monthly.122.5.433. S2CID 207521192.

[2] Clement, P. A. (1949). "Congruences for sets of primes". Amer. Math. Monthly. 56 (1): 23–25. doi:10.2307/2305816. JSTOR 2305816.

[3] C. Lin and L. Zhipeng (2005). "On Wilson's theorem and Polignac conjecture". Math. Medley. 6. arXiv: math/0408018 . Bibcode:2004math......8018C.

[4] Schmidt, M. D. (2017). "New Congruences and Finite Difference Equations for Generalized Factorial Functions". arXiv: 1701.04741 . Bibcode:2017arXiv170104741S.{{cite journal}}: Cite journal requires |journal= (help)

[1]

[2]

[3]

[4]

Table of congruences

Contents