In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, a Wieferich prime is a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
''p'' such that ''p''
2 divides ,
therefore connecting these primes with
Fermat's little theorem, which states that every odd prime ''p'' divides . Wieferich primes were first described by
Arthur Wieferich
Arthur Josef Alwin Wieferich (April 27, 1884 – September 15, 1954) was a German mathematician and teacher, remembered for his work on number theory, as exemplified by a type of prime numbers named after him.
He was born in Münster, attended the ...
in 1909 in works pertaining to
Fermat's Last Theorem
In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers , , and satisfy the equation for any integer value of greater than 2. The cases and have been ...
, at which time both of Fermat's theorems were already well known to mathematicians.
Since then, connections between Wieferich primes and various other topics in mathematics have been discovered, including other types of numbers and primes, such as
Mersenne
Marin Mersenne, OM (also known as Marinus Mersennus or ''le Père'' Mersenne; ; 8 September 1588 – 1 September 1648) was a French polymath whose works touched a wide variety of fields. He is perhaps best known today among mathematicians for ...
and
Fermat
Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he is ...
numbers, specific types of
pseudoprime
A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.
Some sources use the term pseudoprime to ...
s and some types of numbers generalized from the original definition of a Wieferich prime. Over time, those connections discovered have extended to cover more properties of certain prime numbers as well as more general subjects such as
number field
In mathematics, an algebraic number field (or simply number field) is an extension field K of the field of rational numbers such that the field extension K / \mathbb has finite degree (and hence is an algebraic field extension).
Thus K is a f ...
s and the
''abc'' conjecture.
, the only known Wieferich primes are 1093 and 3511 .
Equivalent definitions
The stronger version of
Fermat's little theorem, which a Wieferich prime satisfies, is usually expressed as a
congruence relation . From the definition of the
congruence relation on integers, it follows that this property is equivalent to the definition given at the beginning. Thus if a prime ''p'' satisfies this congruence, this prime divides the
Fermat quotient In number theory, the Fermat quotient of an integer ''a'' with respect to an odd prime ''p'' is defined as= 3/ref>
The smallest solutions of ''q'p''(''a'') ≡ 0 (mod ''p'') with ''a'' = ''n'' are:
:2, 1093, 11, 1093, 2, 66161, 5, 3, 2, 3, 71, ...
. The following are two illustrative examples using the primes 11 and 1093:
: For ''p'' = 11, we get
which is 93 and leaves a
remainder
In mathematics, the remainder is the amount "left over" after performing some computation. In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient ( integer division). In algeb ...
of 5 after division by 11, hence 11 is not a Wieferich prime. For ''p'' = 1093, we get
or 485439490310...852893958515 (302 intermediate digits omitted for clarity), which leaves a remainder of 0 after division by 1093 and thus 1093 is a Wieferich prime.
Wieferich primes can be defined by other equivalent congruences. If ''p'' is a Wieferich prime, one can multiply both sides of the congruence by 2 to get . Raising both sides of the congruence to the power ''p'' shows that a Wieferich prime also satisfies , and hence for all . The converse is also true: for some implies that the
multiplicative order In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n.
In other words, the multiplicative order ...
of 2 modulo ''p''
2 divides
gcd,
φ, that is, and thus ''p'' is a Wieferich prime. This also implies that Wieferich primes can be defined as primes ''p'' such that the multiplicative orders of 2 modulo ''p'' and modulo ''p''
2 coincide: , (By the way, ord
10932 = 364, and ord
35112 = 1755).
H. S. Vandiver proved that if and only if
.
History and search status
In 1902,
Meyer Meyer may refer to:
People
*Meyer (surname), listing people so named
* Meyer (name), a list of people and fictional characters with the name
Companies
* Meyer Burger, a Swiss mechanical engineering company
* Meyer Corporation
* Meyer Sound Labo ...
proved a theorem about solutions of the congruence ''a''
''p'' − 1 ≡ 1 (mod ''p''
''r'').
Later in that decade
Arthur Wieferich
Arthur Josef Alwin Wieferich (April 27, 1884 – September 15, 1954) was a German mathematician and teacher, remembered for his work on number theory, as exemplified by a type of prime numbers named after him.
He was born in Münster, attended the ...
showed specifically that if the
first case of Fermat's last theorem has solutions for an odd prime exponent, then that prime must satisfy that congruence for ''a'' = 2 and ''r'' = 2.
In other words, if there exist solutions to ''x''
''p'' + ''y''
''p'' + ''z''
''p'' = 0 in integers ''x'', ''y'', ''z'' and ''p'' an
odd prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
with ''p''
∤ ''xyz'', then ''p'' satisfies 2
''p'' − 1 ≡ 1 (mod ''p''
2). In 1913,
Bachmann
Bachmann is a surname of Switzerland and Germany. It originates as a description of the bearer as dwelling near a brook (''Bach''), such as a farm "Hofstatt am Bach" also called "Bachmanns Hofstatt" near Hinwil or Dürnten (recorded 1387), or the ...
examined the
residues of
. He asked the question when this residue
vanishes and tried to find expressions for answering this question.
The prime 1093 was found to be a Wieferich prime by in 1913 and confirmed to be the only such prime below 2000. He calculated the smallest residue of
for all primes ''p'' < 2000 and found this residue to be zero for ''t'' = 364 and ''p'' = 1093, thereby providing a counterexample to a
conjecture by
Grave
A grave is a location where a dead body (typically that of a human, although sometimes that of an animal) is buried or interred after a funeral. Graves are usually located in special areas set aside for the purpose of burial, such as grav ...
about the impossibility of the Wieferich congruence.
later ordered verification of the correctness of Meissner's congruence via only elementary calculations. Inspired by an earlier work of
Euler, he simplified Meissner's proof by showing that 1093
2 , (2
182 + 1) and remarked that (2
182 + 1) is a factor of (2
364 − 1). It was also shown that it is possible to prove that 1093 is a Wieferich prime without using
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the fo ...
s contrary to the method used by Meissner, although Meissner himself hinted at that he was aware of a proof without complex values.
The prime
3511 was first found to be a Wieferich prime by
N. G. W. H. Beeger in 1922 and another proof of it being a Wieferich prime was published in 1965 by
Guy. In 1960, Kravitz doubled a previous record set by and in 1961
Riesel extended the search to 500000 with the aid of
BESK
BESK (''Binär Elektronisk SekvensKalkylator'', Swedish for "Binary Electronic Sequence Calculator") was Sweden's first electronic computer, using vacuum tubes instead of relays. It was developed by '' Matematikmaskinnämnden'' ( Swedish Boar ...
. Around 1980,
Lehmer was able to reach the search limit of 6. This limit was extended to over 2.5 in 2006,
finally reaching 3. It is now known that if any other Wieferich primes exist, they must be greater than 6.7.
In 2007–2016, a search for Wieferich primes was performed by the
distributed computing
A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...
project Wieferich@Home. In 2011–2017, another search was performed by the
PrimeGrid
PrimeGrid is a volunteer computing project that searches for very large (up to world-record size) prime numbers whilst also aiming to solve long-standing mathematical conjectures. It uses the Berkeley Open Infrastructure for Network Computing ...
project, although later the work done in this project was claimed wasted. While these projects reached search bounds above 1, neither of them reported any sustainable results.
In 2020, PrimeGrid started another project that searches for Wieferich and
Wall–Sun–Sun prime
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.
Definition
Let p be a prime number. When each term in the sequence of Fibonac ...
s simultaneously. The new project uses checksums to enable independent double-checking of each subinterval, thus minimizing the risk of missing an instance because of faulty hardware. the leading edge of this search was over 3.
It has been conjectured (as for
Wilson prime
In number theory, a Wilson prime is a prime number p such that p^2 divides (p-1)!+1, where "!" denotes the factorial function; compare this with Wilson's theorem, which states that every prime p divides (p-1)!+1. Both are named for 18th-century E ...
s) that infinitely many Wieferich primes exist, and that the number of Wieferich primes below ''x'' is approximately log(log(''x'')), which is a
heuristic result that follows from the plausible assumption that for a prime ''p'', the degree
roots of unity
In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in ...
modulo ''p''
2 are
uniformly distributed in the
multiplicative group of integers modulo ''p''2.
Properties
Connection with Fermat's Last Theorem
The following theorem connecting Wieferich primes and
Fermat's Last Theorem
In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers , , and satisfy the equation for any integer value of greater than 2. The cases and have been ...
was proven by Wieferich in 1909:
:Let ''p'' be prime, and let ''x'', ''y'', ''z'' be
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 such that . Furthermore, assume that ''p'' does not divide the
product
Product may refer to:
Business
* Product (business), an item that serves as a solution to a specific consumer problem.
* Product (project management), a deliverable or set of deliverables that contribute to a business solution
Mathematics
* Produ ...
''xyz''. Then ''p'' is a Wieferich prime.
The above case (where ''p'' does not divide any of ''x'', ''y'' or ''z'') is commonly known as the
first case of Fermat's Last Theorem (FLTI) and FLTI is said to fail for a prime ''p'', if solutions to the Fermat equation exist for that ''p'', otherwise FLTI holds for ''p''.
In 1910,
Mirimanoff expanded the theorem by showing that, if the preconditions of the theorem hold true for some prime ''p'', then ''p''
2 must also divide . Granville and Monagan further proved that ''p''
2 must actually divide for every prime ''m'' ≤ 89.
Suzuki extended the proof to all primes ''m'' ≤ 113.
Let ''H
p'' be a set of pairs of integers with 1 as their
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
, ''p'' being prime to ''x'', ''y'' and ''x'' + ''y'', (''x'' + ''y'')
''p''−1 ≡ 1 (mod p
2), (''x'' + ''ξy'') being the ''p''th power of an
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
of ''K'' with ''ξ'' defined as cos 2''π''/''p'' + ''i'' sin 2''π''/''p''. ''K'' = Q(''ξ'') is the
field extension obtained by adjoining all
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
s in the
algebraic number ''ξ'' to the
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
of
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
s (such an extension is known as a
number field
In mathematics, an algebraic number field (or simply number field) is an extension field K of the field of rational numbers such that the field extension K / \mathbb has finite degree (and hence is an algebraic field extension).
Thus K is a f ...
or in this particular case, where ''ξ'' is a
root of unity
In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important ...
, a
cyclotomic number field).
From
uniqueness of factorization of ideals in Q(ξ) it follows that if the first case of Fermat's last theorem has solutions ''x'', ''y'', ''z'' then ''p'' divides ''x''+''y''+''z'' and (''x'', ''y''), (''y'', ''z'') and (''z'', ''x'') are elements of ''H
p''.
Granville and Monagan showed that (1, 1) ∈ ''H
p'' if and only if ''p'' is a Wieferich prime.
Connection with the ''abc'' conjecture and non-Wieferich primes
A non-Wieferich prime is a prime ''p'' satisfying .
J. H. Silverman showed in 1988 that if the
''abc'' conjecture holds, then there exist infinitely many non-Wieferich primes. More precisely he showed that the ''abc'' conjecture implies the existence of a constant only depending on ''α'' such that the number of non-Wieferich primes to base ''α'' with ''p'' less than or equal to a variable ''X'' is greater than log(''X'') as ''X'' goes to infinity. Numerical evidence suggests that very few of the prime numbers in a given interval are Wieferich primes. The set of Wieferich primes and the set of non-Wieferich primes, sometimes denoted by ''W
2'' and ''W
2c'' respectively,
are
complementary sets, so if one of them is shown to be finite, the other one would necessarily have to be infinite, because both are
proper subsets of the set of prime numbers. It was later shown that the existence of infinitely many non-Wieferich primes already follows from a weaker version of the ''abc'' conjecture, called the ''ABC''-(''k'', ''ε'') ''conjecture''. Additionally, the existence of infinitely many non-Wieferich primes would also follow if there exist infinitely many square-free Mersenne numbers as well as if there exists a real number ''ξ'' such that the set is of
density
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematical ...
one, where the ''index of composition'' ''λ''(''n'') of an integer ''n'' is defined as
and
, meaning
gives the product of all
prime factors of ''n''.
Connection with Mersenne and Fermat primes
It is known that the ''n''th
Mersenne number
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th ...
is prime only if ''n'' is prime.
Fermat's little theorem implies that if is prime, then ''M''
''p''−1 is always divisible by ''p''. Since Mersenne numbers of prime indices ''M''
''p'' and ''M''
''q'' are co-prime,
::A prime divisor ''p'' of ''M''
''q'', where ''q'' is prime, is a Wieferich prime if and only if ''p''
2 divides ''M''
''q''.
Thus, a Mersenne prime cannot also be a Wieferich prime. A notable
open problem is to determine whether or not all Mersenne numbers of prime index are
square-free {{no footnotes, date=December 2015
In mathematics, a square-free element is an element ''r'' of a unique factorization domain ''R'' that is not divisible by a non-trivial square. This means that every ''s'' such that s^2\mid r is a unit of ''R''.
A ...
. If ''q'' is prime and the Mersenne number ''M''
''q'' is ''not'' square-free, that is, there exists a prime ''p'' for which ''p''
2 divides ''M''
''q'', then ''p'' is a Wieferich prime. Therefore, if there are only finitely many Wieferich primes, then there will be at most finitely many Mersenne numbers with prime index that are not square-free. Rotkiewicz showed a related result: if there are infinitely many square-free Mersenne numbers, then there are infinitely many non-Wieferich primes.
Similarly, if ''p'' is prime and ''p''
2 divides some
Fermat number
In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form
:F_ = 2^ + 1,
where ''n'' is a non-negative integer. The first few Fermat numbers are:
: 3, 5, 17, 257, 65537, 42949672 ...
''F''
''n'' , then ''p'' must be a Wieferich prime.
In fact, there exists a natural number ''n'' and a prime ''p'' that ''p''
2 divides
(where
is the ''n''-th
cyclotomic polynomial)
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is b ...
''p'' is a Wieferich prime. For example, 1093
2 divides
, 3511
2 divides
. Mersenne and Fermat numbers are just special situations of
. Thus, if 1093 and 3511 are only two Wieferich primes, then all
are
square-free {{no footnotes, date=December 2015
In mathematics, a square-free element is an element ''r'' of a unique factorization domain ''R'' that is not divisible by a non-trivial square. This means that every ''s'' such that s^2\mid r is a unit of ''R''.
A ...
except
and
(In fact, when there exists a prime ''p'' which ''p''
2 divides some
, then it is a Wieferich prime); and clearly, if
is a prime, then it cannot be Wieferich prime. (Any odd prime ''p'' divides only one
and ''n'' divides , and if and only if the period length of 1/p in
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
is ''n'', then ''p'' divides
. Besides, if and only if ''p'' is a Wieferich prime, then the period length of 1/p and 1/p
2 are the same (in binary). Otherwise, this is ''p'' times than that.)
For the primes 1093 and 3511, it was shown that neither of them is a divisor of any Mersenne number with prime index nor a divisor of any Fermat number, because 364 and 1755 are neither prime nor powers of 2.
Connection with other equations
Scott and Styer showed that the equation ''p''
x – 2
y = ''d'' has at most one solution in positive integers (''x'', ''y''), unless when ''p''
4 , 2
ord''p'' 2 – 1 if ''p'' ≢ 65 (mod 192) or unconditionally when ''p''
2 , 2
ord''p'' 2 – 1, where ord
''p'' 2 denotes the
multiplicative order In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n.
In other words, the multiplicative order ...
of 2 modulo ''p''. They also showed that a solution to the equation ±''a''
''x''1 ± 2
''y''1 = ±''a''
''x''2 ± 2
''y''2 = ''c'' must be from a specific set of equations but that this does not hold, if ''a'' is a Wieferich prime greater than 1.25 x 10
15.
Binary periodicity of ''p'' − 1
Johnson observed
that the two known Wieferich primes are one greater than numbers with periodic
binary expansion
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" ( one).
The base-2 numeral system is a positional notatio ...
s (1092 = 010001000100
2=444
16; 3510 = 110110110110
2=6666
8). The Wieferich@Home project searched for Wieferich primes by testing numbers that are one greater than a number with a periodic binary expansion, but up to a "bit pseudo-length" of 3500 of the tested binary numbers generated by combination of bit strings with a bit length of up to 24 it has not found a new Wieferich prime.
Abundancy of ''p'' − 1
It has been noted that the known Wieferich primes are one greater than mutually
friendly number
In number theory, friendly numbers are two or more natural numbers with a common abundancy index, the ratio between the sum of divisors of a number and the number itself. Two numbers with the same "abundancy" form a friendly pair; ''n'' numbers w ...
s (the shared abundancy index being 112/39).
Connection with pseudoprimes
It was observed that the two known Wieferich primes are the square factors of all
non-square free base-2
Fermat pseudoprime
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
Definition
Fermat's little theorem states that if ''p'' is prime and ''a'' is coprime to ''p'', then ''a'p''− ...
s up to 25. Later computations showed that the only repeated factors of the pseudoprimes up to 10
12 are 1093 and 3511. In addition, the following connection exists:
:Let ''n'' be a base 2 pseudoprime and ''p'' be a prime divisor of ''n''. If
, then also
.
Furthermore, if ''p'' is a Wieferich prime, then ''p''
2 is a
Catalan pseudoprime
In mathematics, a Catalan pseudoprime is an odd composite number ''n'' satisfying the congruence
: (-1)^ \cdot C_ \equiv 2 \pmod n,
where ''Cm'' denotes the ''m''-th Catalan number. The congruence also holds for every odd prime number ''n'' that ...
.
Connection with directed graphs
For all primes up to , only in two cases: and , where is the number of vertices in the cycle of 1 in the ''doubling diagram'' modulo . Here the doubling diagram represents the
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
with the non-negative integers less than ''m'' as vertices and with directed edges going from each vertex ''x'' to vertex 2''x'' reduced modulo ''m''.
It was shown, that for all odd prime numbers either or .
Properties related to number fields
It was shown that
and
if and only if where ''p'' is an odd prime and
is the
fundamental discriminant In mathematics, a fundamental discriminant ''D'' is an integer invariant (mathematics), invariant in the theory of integer, integral binary quadratic forms. If is a quadratic form with integer coefficients, then is the discriminant of ''Q''(''x'', ...
of the imaginary
quadratic field
In algebraic number theory, a quadratic field is an algebraic number field of degree two over \mathbf, the rational numbers.
Every such quadratic field is some \mathbf(\sqrt) where d is a (uniquely defined) square-free integer different from 0 a ...
. Furthermore, the following was shown: Let ''p'' be a Wieferich prime. If , let
be the fundamental discriminant of the imaginary quadratic field
and if , let
be the fundamental discriminant of the imaginary quadratic field
. Then
and
(''χ'' and ''λ'' in this context denote Iwasawa
invariants).
Furthermore, the following result was obtained: Let ''q'' be an odd prime number, ''k'' and ''p'' are primes such that and the order of ''q'' modulo ''k'' is
. Assume that ''q'' divides ''h''
+, the
class number of the real
cyclotomic field
In number theory, a cyclotomic field is a number field obtained by adjoining a complex root of unity to , the field of rational numbers.
Cyclotomic fields played a crucial role in the development of modern algebra and number theory because of ...
, the cyclotomic field obtained by adjoining the sum of a ''p''-th
root of unity
In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important ...
and its
reciprocal
Reciprocal may refer to:
In mathematics
* Multiplicative inverse, in mathematics, the number 1/''x'', which multiplied by ''x'' gives the product 1, also known as a ''reciprocal''
* Reciprocal polynomial, a polynomial obtained from another pol ...
to the field of rational numbers. Then ''q'' is a Wieferich prime.
This also holds if the conditions and are replaced by and as well as when the condition is replaced by (in which case ''q'' is a
Wall–Sun–Sun prime
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.
Definition
Let p be a prime number. When each term in the sequence of Fibonac ...
) and the incongruence condition replaced by .
Generalizations
Near-Wieferich primes
A prime ''p'' satisfying the congruence 2
(''p''−1)/2 (mod ''p''
2) with small , ''A'', is commonly called a ''near-Wieferich prime'' .
Near-Wieferich primes with ''A'' = 0 represent Wieferich primes. Recent searches, in addition to their primary search for Wieferich primes, also tried to find near-Wieferich primes.
[About project Wieferich@Home]
/ref> The following table lists all near-Wieferich primes with , ''A'', ≤ 10 in the interval , 3
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
This search bound was reached in 2006 in a search effort by P. Carlisle, R. Crandall and M. Rodenkirch. Bigger entries are by PrimeGrid.
The sign +1 or -1 above can be easily predicted by Euler's criterion (and the second supplement to the law of quadratic reciprocity
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 st ...
).
Dorais and Klyve used a different definition of a near-Wieferich prime, defining it as a prime ''p'' with small value of where is the Fermat quotient In number theory, the Fermat quotient of an integer ''a'' with respect to an odd prime ''p'' is defined as= 3/ref>
The smallest solutions of ''q'p''(''a'') ≡ 0 (mod ''p'') with ''a'' = ''n'' are:
:2, 1093, 11, 1093, 2, 66161, 5, 3, 2, 3, 71, ...
of 2 with respect to ''p'' modulo ''p'' (the modulo operation
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is th ...
here gives the residue with the smallest absolute value). The following table lists all primes ''p'' ≤ with .
The two notions of nearness are related as follows. If , then by squaring, clearly . So if had been chosen with small, then clearly is also (quite) small, and an even number. However, when is odd above, the related from before the last squaring was not "small". For example, with , we have which reads extremely non-near, but after squaring this is which is a near-Wieferich by the second definition.
Base-''a'' Wieferich primes
A ''Wieferich prime base a'' is a prime ''p'' that satisfies
: , with ''a'' less than ''p'' but greater than 1.
Such a prime cannot divide ''a'', since then it would also divide 1.
It's a conjecture that for every natural number ''a'', there are infinitely many Wieferich primes in base ''a''.
Bolyai showed that if ''p'' and ''q'' are primes, ''a'' is a positive integer not divisible by ''p'' and ''q'' such that , , then . Setting ''p'' = ''q'' leads to . It was shown that if and only if .
Known solutions of for small values of ''a'' are: (checked up to 5 × 1013)
:
For more information, see and. (Note that the solutions to ''a'' = ''bk'' is the union of the prime divisors of ''k'' which does not divide ''b'' and the solutions to ''a'' = ''b'')
The smallest solutions of are
:2, 1093, 11, 1093, 2, 66161, 5, 3, 2, 3, 71, 2693, 2, 29, 29131, 1093, 2, 5, 3, 281, 2, 13, 13, 5, 2, 3, 11, 3, 2, 7, 7, 5, 2, 46145917691, 3, 66161, 2, 17, 8039, 11, 2, 23, 5, 3, 2, 3, ... (The next term > 4.9×1013)
There are no known solutions of for ''n'' = 47, 72, 186, 187, 200, 203, 222, 231, 304, 311, 335, 355, 435, 454, 546, 554, 610, 639, 662, 760, 772, 798, 808, 812, 858, 860, 871, 983, 986, 1002, 1023, 1130, 1136, 1138, ....
It is a conjecture that there are infinitely many solutions of for every natural number ''a''.
The bases ''b'' < ''p''2 which ''p'' is a Wieferich prime are (for ''b'' > ''p''2, the solutions are just shifted by ''k''·''p''2 for ''k'' > 0), and there are solutions < ''p''2 of ''p'' and the set of the solutions congruent
Congruence may refer to:
Mathematics
* Congruence (geometry), being the same size and shape
* Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure
* In mod ...
to ''p'' are
:
The least base ''b'' > 1 which prime(''n'') is a Wieferich prime are
:5, 8, 7, 18, 3, 19, 38, 28, 28, 14, 115, 18, 51, 19, 53, 338, 53, 264, 143, 11, 306, 31, 99, 184, 53, 181, 43, 164, 96, 68, 38, 58, 19, 328, 313, 78, 226, 65, 253, 259, 532, 78, 176, 276, 143, 174, 165, 69, 330, 44, 33, 332, 94, 263, 48, 79, 171, 747, 731, 20, ...
We can also consider the formula , (because of the generalized Fermat little theorem, is true for all prime ''p'' and all natural number ''a'' such that both ''a'' and are not divisible by ''p''). It's a conjecture that for every natural number ''a'', there are infinitely many primes such that .
Known solutions for small ''a'' are: (checked up to 4 × 1011)
:
Wieferich pairs
A Wieferich pair is a pair of primes ''p'' and ''q'' that satisfy
: ''p''''q'' − 1 ≡ 1 (mod ''q''2) and ''q''''p'' − 1 ≡ 1 (mod ''p''2)
so that a Wieferich prime ''p'' ≡ 1 (mod 4) will form such a pair (''p'', 2): the only known instance in this case is . There are only 7 known Wieferich pairs.
: (2, 1093), (3, 1006003), (5, 1645333507), (5, 188748146801), (83, 4871), (911, 318917), and (2903, 18787) (sequence in OEIS
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
)
Wieferich sequence
Start with a(1) any natural number (>1), a(''n'') = the smallest prime ''p'' such that (a(''n'' − 1))''p'' − 1 = 1 (mod ''p''2) but ''p''2 does not divide a(''n'' − 1) − 1 or a(''n'' − 1) + 1. (If ''p''2 divides a(''n'' − 1) − 1 or a(''n'' − 1) + 1, then the solution is a trivial solution In mathematics, the adjective trivial is often used to refer to a claim or a case which can be readily obtained from context, or an object which possesses a simple structure (e.g., groups, topological spaces). The noun triviality usually refers to a ...
) It is a conjecture that every natural number ''k'' = a(1) > 1 makes this sequence become periodic, for example, let a(1) = 2:
:2, 1093, 5, 20771, 18043, 5, 20771, 18043, 5, ..., it gets a cycle: .
Let a(1) = 83:
:83, 4871, 83, 4871, 83, 4871, 83, ..., it gets a cycle: .
Let a(1) = 59 (a longer sequence):
:59, 2777, 133287067, 13, 863, 7, 5, 20771, 18043, 5, ..., it also gets 5.
However, there are many values of a(1) with unknown status, for example, let a(1) = 3:
:3, 11, 71, 47, ? (There are no known Wieferich primes in base 47).
Let a(1) = 14:
:14, 29, ? (There are no known Wieferich prime in base 29 except 2, but 22 = 4 divides 29 − 1 = 28)
Let a(1) = 39 (a longer sequence):
:39, 8039, 617, 101, 1050139, 29, ? (It also gets 29)
It is unknown that values for a(1) > 1 exist such that the resulting sequence does not eventually become periodic.
When a(''n'' − 1)=''k'', a(''n'') will be (start with ''k'' = 2): 1093, 11, 1093, 20771, 66161, 5, 1093, 11, 487, 71, 2693, 863, 29, 29131, 1093, 46021, 5, 7, 281, ?, 13, 13, 25633, 20771, 71, 11, 19, ?, 7, 7, 5, 233, 46145917691, 1613, 66161, 77867, 17, 8039, 11, 29, 23, 5, 229, 1283, 829, ?, 257, 491531, ?, ... (For ''k'' = 21, 29, 47, 50, even the next value is unknown)
Wieferich numbers
A Wieferich number is an odd natural number ''n'' satisfying the congruence 2(''n'') ≡ 1 (mod ''n''2), where denotes the Euler's totient function (according to Euler's theorem, 2(''n'') ≡ 1 (mod ''n'') for every odd natural number ''n''). If Wieferich number ''n'' is prime, then it is a Wieferich prime. The first few Wieferich numbers are:
:1, 1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, 52665, 68859, 94797, 99463, ...
It can be shown that if there are only finitely many Wieferich primes, then there are only finitely many Wieferich numbers. In particular, if the only Wieferich primes are 1093 and 3511, then there exist exactly 104 Wieferich numbers, which matches the number of Wieferich numbers currently known.
More generally, a natural number ''n'' is a Wieferich number to base ''a'', if ''a''(''n'') ≡ 1 (mod ''n''2).
Another definition specifies a Wieferich number as odd natural number ''n'' such that ''n'' and are not coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
, where ''m'' is the multiplicative order In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n.
In other words, the multiplicative order ...
of 2 modulo ''n''. The first of these numbers are:
:21, 39, 55, 57, 105, 111, 147, 155, 165, 171, 183, 195, 201, 203, 205, 219, 231, 237, 253, 273, 285, 291, 301, 305, 309, 327, 333, 355, 357, 385, 399, ...
As above, if Wieferich number ''q'' is prime, then it is a Wieferich prime.
Weak Wieferich prime
A weak Wieferich prime to base ''a'' is a prime ''p'' satisfies the condition
:''a''''p'' ≡ ''a'' (mod ''p''2)
Every Wieferich prime to base ''a'' is also a weak Wieferich prime to base ''a''. If the base ''a'' is squarefree
In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, is square-fr ...
, then a prime ''p'' is a weak Wieferich prime to base ''a'' if and only if ''p'' is a Wieferich prime to base ''a''.
Smallest weak Wieferich prime to base ''n'' are (start with ''n'' = 0)
:2, 2, 1093, 11, 2, 2, 66161, 5, 2, 2, 3, 71, 2, 2, 29, 29131, 2, 2, 3, 3, 2, 2, 13, 13, 2, 2, 3, 3, 2, 2, 7, 7, 2, 2, 46145917691, 3, 2, 2, 17, 8039, 2, 2, 23, 5, 2, 2, 3, ...
Wieferich prime with order ''n''
For integer ''n'' ≥2, a Wieferich prime to base ''a'' with order ''n'' is a prime ''p'' satisfies the condition
:''a''''p''−1 ≡ 1 (mod ''p''''n'')
Clearly, a Wieferich prime to base ''a'' with order ''n'' is also a Wieferich prime to base ''a'' with order ''m'' for all 2 ≤ ''m'' ≤ ''n'', and Wieferich prime to base ''a'' with order 2 is equivalent to Wieferich prime to base ''a'', so we can only consider the ''n'' ≥ 3 case. However, there are no known Wieferich prime to base 2 with order 3. The first base with known Wieferich prime with order 3 is 9, where 2 is a Wieferich prime to base 9 with order 3. Besides, both 5 and 113 are Wieferich prime to base 68 with order 3.
Lucas–Wieferich primes
Let ''P'' and ''Q'' be integers. The Lucas sequence
In mathematics, the Lucas sequences U_n(P,Q) and V_n(P, Q) are certain constant-recursive integer sequences that satisfy the recurrence relation
: x_n = P \cdot x_ - Q \cdot x_
where P and Q are fixed integers. Any sequence satisfying this rec ...
of the first kind associated with the pair
Pair or PAIR or Pairing may refer to:
Government and politics
* Pair (parliamentary convention), matching of members unable to attend, so as not to change the voting margin
* ''Pair'', a member of the Prussian House of Lords
* ''Pair'', the Frenc ...
(''P'', ''Q'') is defined by
:
for all . A Lucas–Wieferich prime associated with (''P'', ''Q'') is a prime ''p'' such that ''U''''p''−''ε''(''P'', ''Q'') ≡ 0 (mod ''p''2), where ''ε'' equals the Legendre symbol . All Wieferich primes are Lucas–Wieferich primes associated with the pair (3, 2).
Fibonacci–Wieferich primes
Let ''Q'' = −1. For every natural number ''P'', the Lucas–Wieferich primes associated with (''P'', −1) are called ''P''-Fibonacci–Wieferich primes or ''P''-Wall–Sun–Sun prime
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.
Definition
Let p be a prime number. When each term in the sequence of Fibonac ...
s. If ''P'' = 1, they are called Fibonacci–Wieferich primes. If ''P'' = 2, they are called Pell–Wieferich primes.
For example, 241 is a Lucas–Wieferich prime associated with (3, −1), so it is a 3-Fibonacci–Wieferich prime or 3-Wall–Sun–Sun prime. In fact, 3 is a ''P''-Fibonacci–Wieferich prime if and only if ''P'' congruent to 0, 4, or 5 (mod 9), which is analogous to the statement for traditional Wieferich primes that 3 is a base-''n'' Wieferich prime if and only if ''n'' congruent to 1 or 8 (mod 9).
Wieferich places
Let ''K'' be a global field In mathematics, a global field is one of two type of fields (the other one is local field) which are characterized using valuations. There are two kinds of global fields:
* Algebraic number field: A finite extension of \mathbb
*Global function fi ...
, i.e. a number field
In mathematics, an algebraic number field (or simply number field) is an extension field K of the field of rational numbers such that the field extension K / \mathbb has finite degree (and hence is an algebraic field extension).
Thus K is a f ...
or a function field in one variable over a finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
and let ''E'' be an elliptic curve
In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
. If ''v'' is a non-archimedean place of norm
Naturally occurring radioactive materials (NORM) and technologically enhanced naturally occurring radioactive materials (TENORM) consist of materials, usually industrial wastes or by-products enriched with radioactive elements found in the envi ...
''qv'' of ''K'' and a ∈ K, with ''v''(''a'') = 0 then ≥ 1. ''v'' is called a ''Wieferich place'' for base ''a'', if > 1, an ''elliptic Wieferich place'' for base ''P'' ∈ ''E'', if ''NvP'' ∈ ''E''2 and a ''strong elliptic Wieferich place'' for base ''P'' ∈ ''E'' if ''nvP'' ∈ ''E''2, where ''nv'' is the order of ''P'' modulo ''v'' and ''Nv'' gives the number of rational point
In number theory and algebraic geometry, a rational point of an algebraic variety is a point whose coordinates belong to a given field. If the field is not mentioned, the field of rational numbers is generally understood. If the field is the fiel ...
s (over the residue field In mathematics, the residue field is a basic construction in commutative algebra. If ''R'' is a commutative ring and ''m'' is a maximal ideal, then the residue field is the quotient ring ''k'' = ''R''/''m'', which is a field. Frequently, ''R'' is a ...
of ''v'') of the reduction of ''E'' at ''v''.
See also
* Wall–Sun–Sun prime
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.
Definition
Let p be a prime number. When each term in the sequence of Fibonac ...
– another type of prime number which in the broadest sense also resulted from the study of FLT
* Wolstenholme prime – another type of prime number which in the broadest sense also resulted from the study of FLT
* Wilson prime
In number theory, a Wilson prime is a prime number p such that p^2 divides (p-1)!+1, where "!" denotes the factorial function; compare this with Wilson's theorem, which states that every prime p divides (p-1)!+1. Both are named for 18th-century E ...
* 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 ...
– lists other congruences satisfied by prime numbers
* PrimeGrid
PrimeGrid is a volunteer computing project that searches for very large (up to world-record size) prime numbers whilst also aiming to solve long-standing mathematical conjectures. It uses the Berkeley Open Infrastructure for Network Computing ...
– primes search project
*BOINC
The Berkeley Open Infrastructure for Network Computing (BOINC, pronounced – rhymes with "oink") is an open-source middleware system for volunteer computing (a type of distributed computing). Developed originally to support SETI@home, it beca ...
*Distributed computing
A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...
References
Further reading
*
*
*
*
*
*
External links
*
Fermat-/Euler-quotients with arbitrary ''k''
* PrimeGrid'
Wieferich Prime Search project
page
{{Prime number classes, state=collapsed
Classes of prime numbers
Unsolved problems in number theory