Unique prime

Period of a prime in base b

The representation of the reciprocal of a prime number (or, more generally, an integer) p in the numeral base b is periodic of period n if

1 p = ∑ i = 1 ∞ q ( b n ) i ,

where q is a positive integer smaller than b n . According to the summation formula of geometric series, this may be rewritten as

1 p = q b n − 1 .

In other words, n is a period of the representation of 1/p if and only if p is a divisor of b n − 1. Euler's theorem asserts that, if an integer b is coprime with p, then p is a divisor of p φ ( n ) − 1 where φ is Euler's totient function. This proves that, for every integer p coprime with b, the representation of the reciprocal of p is periodic in base b.

All the periods of a periodic function are multiples of a shortest period generally called the fundamental period. In this article, we call period of p in base b the shortest period of the representation of 1/p in base b. Therefore, the period of p in base b is the smallest positive integer n such that that p is a divisor of b n − 1. In other words, the period of a prime p in base b is the multiplicative order of b modulo p.

According to Zsigmondy's theorem, every positive integer is a period of some prime in base b except in the following cases:

b = 2 and n = 1 or 6

n = 2 and b= 2^k − 1 for some integer k > 1

As

x n − 1 = ∏ i ∣ n Φ n ( x ) ,

where Φ n is the nth cyclotomic polynomial, the primes of period n in base b are prime divisors of Φ n ( b ) . More precisely, the primes of period n are exactly the prime divisors of Φ n ( b ) that do not divide n (see below for a proof of this result and of the following ones).

If b is even (this includes the binary and the decimal cases), the prime divisors of Φ n ( b ) that do not divide n are exactly the prime divisors of

R n ( b ) = Φ n ( b ) gcd ( Φ n ( b ) , n ) .

This is wrong if b is odd: if n = 2 and b = 4k − 1, where k is a positive integer, then

R 2 ( b ) = Φ 2 ( b ) gcd ( Φ 2 ( b ) , 2 ) = b + 1 2 = 2 k ,

although 2 divides both n = 2 and Φ n ( b ) .

If b is odd, the primes of period n are exactly, if n = 1, the prime divisors of R 1 ( b ) = b − 1 , or, if n > 1, the odd prime divisors of R_n(b).

A prime p is a unique prime in base b, if and only if, for some n, it is the unique prime divisor of Φ n ( b ) that does not divide n. If b is even (which includes the binary and the decimal cases) this means that

R n ( b ) = Φ n ( b ) gcd ( Φ n ( b ) , n ) = p c .

for some positive integer c .

If b is odd, this means that

R n ( b ) = Φ n ( b ) gcd ( Φ n ( b ) , n ) = p c 2 d .

for some integers c > 0 and d ≥ 0. This provides an efficient method for computing the unique primes and the primes of a given period.

Note that a prime divisor of b is coprime with b n − 1 , and thus also with its divisor Φ n ( b ) . Such a prime has no period length, as the representation in base b of its reciprocal is finite instead of being periodic. Thus, such a prime is never considered as a unique prime, even if it is the unique prime that has a finite reciprocal in base b. For example, 2 is not considered as a unique prime in binary, although it is the only prime with finite reciprocal in binary.

Decimal unique primes

At present, more than fifty unique primes or probable primes are known. However, there are only twenty-three unique primes below 10¹⁰⁰. The following table gives an overview of all 23 unique primes below 10¹⁰⁰ (sequence A040017 (sorted) and A007615 (ordered by period length) in OEIS) and their periods (sequence A051627 (ordered by corresponding primes) and A007498 (sorted) in OEIS)

The prime with period length 294 is similar to the reciprocal of 7 (0.142857142857142857...)

Just after the table, the twenty-fourth unique prime has 128 digits and period length 320. It can be written as (9₃₂0₃₂)₂ + 1, where a subscript number n indicates n consecutive copies of the digit or group of digits before the subscript.

Though they are rare, based on the occurrence of repunit primes and probable primes, it is conjectured strongly that there are infinitely many unique primes. (Any repunit prime is unique.)

As of 2010 the repunit (10²⁷⁰³⁴³-1)/9 is the largest known probable unique prime.

In 1996 the largest proven unique prime was (10¹¹³² + 1)/10001 or, using the notation above, (99990000)₁₄₁+ 1. It has 1129 digits. The record has been improved many times since then. As of 2014 the largest proven unique prime is Φ 47498 ( 10 ) , it has 20160 digits.

Binary unique primes

The first unique primes in binary (base 2) are:

3, 5, 7, 11, 13, 17, 19, 31, 41, 43, 73, 127, 151, 241, 257, 331, 337, 683, ... (sequence A144755 (sorted) and A161509 (ordered by period length) in OEIS)

The period length of them are:

2, 4, 3, 10, 12, 8, 18, 5, 20, 14, 9, 7, 15, 24, 16, 30, 21, 22, ... (sequence A247071 (ordered by corresponding primes) and A161508 (sorted) in OEIS)

They include Fermat primes (the period length is a power of 2), Mersenne primes (the period length is a prime) and Wagstaff primes (the period length is twice an odd prime).

Additionally, if n is a natural number which is not equal to 1 or 6, than at least one prime have period n in base 2, because of the Zsigmondy theorem. Besides, if n is congruent to 4 (mod 8) and n > 20, then at least two primes have period n in base 2, (Thus, n is not a unique period in base 2) because of the Aurifeuillean factorization, for example, 113 (= Φ 28 L ( 2 ) ) and 29 (= Φ 28 M ( 2 ) ) both have period 28 in base 2, 37 (= Φ 36 L ( 2 ) ) and 109 (= Φ 36 M ( 2 ) ) both have period 36 in base 2, and that 397 (= Φ 44 L ( 2 ) ) and 2113 (= Φ 44 M ( 2 ) ) both have period 44 in base 2,

As shown above, a prime p is a unique prime of period n in base 2 if and only if there exists a natural number c such that

Φ n ( 2 ) gcd ( Φ n ( 2 ) , n ) = p c .

The only known values of n such that Φ n ( 2 ) is composite but Φ n ( 2 ) / gcd ( Φ n ( 2 ) , n ) is prime are 18, 20, 21, 54, 147, 342, 602, and 889 (in these case, Φ n ( 2 ) has a small factor which divides n). It is a conjecture that there is no other n with this property. All other known base 2 unique primes are of the form Φ n ( 2 ) .

In fact, no prime with c > 1 (that is Φ n ( 2 ) / gcd ( Φ n ( 2 ) , n ) is a true power of p) have been discovered, and all known unique primes p have c = 1. It is conjectured that all unique primes have c = 1 (that is, all base 2 unique primes are not Wieferich primes).

The largest known base 2 unique prime is 2^74207281-1, it is also the largest known prime. With an exception of Mersenne primes, the largest known probable base 2 unique prime is 2 13372531 + 1 3 , and the largest proved base 2 unique prime is 2 83339 + 1 3 . Besides, the largest known probable base 2 unique prime which is not Mersenne prime or Wagstaff prime is 2 4101572 + 1 17 .

Similar to base 10, though they are rare (but more than the case to base 10), it is conjectured that there are infinitely many base 2 unique primes, because all Mersenne primes are unique in base 2, and it is conjectured they there are infinitely many Mersenne primes.

They divide none of overpseudoprimes to base 2, but every other odd prime number divide one overpseudoprime to base 2, because if and only if a composite number can be written as Φ n ( 2 ) gcd ( Φ n ( 2 ) , n ) , it is an overpseudoprime to base 2.

There are 52 unique primes in base 2 below 2⁶⁴, they are:

After the table, the next 10 binary unique prime have period length 170, 234, 158, 165, 147, 129, 184, 89, 208, and 312. Besides, the bits (digits in binary) of them are 65, 73, 78, 81, 82, 84, 88, 89, 96, and 97.

Bi-unique primes

Bi-unique primes are a pairs of primes having a period length shared by no other primes. For example, in binary, the bi-unique primes with at least one prime less than 10000 are:

Although there are 1228 odd primes below 10000, only 21 of them are unique and 76 of them are bi-unique in binary.

A classic example of binary bi-unique primes are

468172263510722656207776706750069723016189792142528328750689763038394004
13682313921168154465151768472420980044715745858522803980473207943564433 (143 digits)

and

527739642811233917558838216073534609312522896254707972010583175760467054
896492872702786549764052643493511382273226052631979775533936351462037464
331880467187717179256707148303247 (177 digits)

they are the two prime factor of the Mersenne number 2¹⁰⁶¹−1. Thus, the period length of them is 1061.

As of October 2016, the largest known probable binary bi-unique prime is 2 5240707 − 1 75392810903 , it has a period length of 5240707 shares with only the prime 75392810903.

Similarly, we can define "tri-unique primes" as a triple of primes having a period length shared by no other primes. The first few tri-unique primes are:

In binary, the smallest n-unique prime are

3, 23, 53, 149, 269, 461, 619, 389, ...

In binary, the period length of odd primes are: (sequence A014664 in the OEIS)

In binary, the primes with given period length are: (sequence A108974 in the OEIS)