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

$2^{n-1}\equiv 1{\pmod {n}}$	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]).

gollark: And it draws that whole taskbar thing at the bottom *just* for the `start` button, since this "OS" is monotasking and doesn't actually have windowing support at all.

gollark: The `settings` option doesn't work, `programs` is only Paint and LuaIDE, and there's no way to get a shell except the `run` button.

gollark: Also, you're doing fake loading bars in startup, which is basically evil.

gollark: Onto what seems to break it, it looks like the paste you download as `/os/google/google` or whatever is no longer available, and your downloader program does not actually detect this.

gollark: I'm still looking at the other files, since there are a lot.

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.
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 requires |journal= (help)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.

[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 requires |journal= (help)