A super-Poulet number is a Poulet number, or pseudoprime to base 2, whose every divisor d divides
In mathematics, a divisor of an integer , also called a factor of , is an integer that may be multiplied by some integer to produce . In this case, one also says that is a multiple of An integer is divisible by another integer if is a divisor of ; this implies dividing by leaves no remainder.
- 2d− 2.
For example, 341 is a super-Poulet number: it has positive divisors {1, 11, 31, 341} and we have:
- (211 - 2) / 11 = 2046 / 11 = 186
- (231 - 2) / 31 = 2147483646 / 31 = 69273666
- (2341 - 2) / 341 = 13136332798696798888899954724741608669335164206654835981818117894215788100763407304286671514789484550
When a composite number is a pseudoprime to base 2, but not to every base (That is, not a Carmichael number), then it is a super-Poulet number, and when 
is not prime, then it and every divisor of it are a pseudoprime to base 2, and a super-Poulet number.
In number theory, a Carmichael number is a composite number which satisfies the modular arithmetic congruence relation:
The super-Poulet numbers below 10,000 are (sequence A050217 in the OEIS ):
The On-Line Encyclopedia of Integer Sequences (OEIS), also cited simply as Sloane's, is an online database of integer sequences. It was created and maintained by Neil Sloane while a researcher at AT&T Labs. Foreseeing his retirement from AT&T Labs in 2012 and the need for an independent foundation, Sloane agreed to transfer the intellectual property and hosting of the OEIS to the OEIS Foundation in October 2009. Sloane is president of the OEIS Foundation.
| n | |
|---|
| 1 | 341 = 11 × 31 |
| 2 | 1387 = 19 × 73 |
| 3 | 2047 = 23 × 89 |
| 4 | 2701 = 37 × 73 |
| 5 | 3277 = 29 × 113 |
| 6 | 4033 = 37 × 109 |
| 7 | 4369 = 17 × 257 |
| 8 | 4681 = 31 × 151 |
| 9 | 5461 = 43 × 127 |
| 10 | 7957 = 73 × 109 |
| 11 | 8321 = 53 × 157 |
|
Super-Poulet numbers with 3 or more distinct prime divisors
It is relatively easy to get super-Poulet numbers with 3 distinct prime divisors. If you find three Poulet numbers with three common prime factors, you get a super-Poulet number, as you built the product of the three prime factors.
Example: 2701 = 37 * 73 is a Poulet number, 4033 = 37 * 109 is a Poulet number, 7957 = 73 * 109 is a Poulet number;
so 294409 = 37 * 73 * 109 is a Poulet number too.
Super-Poulet numbers with up to 7 distinct prime factors you can get with the following numbers:
- { 103, 307, 2143, 2857, 6529, 11119, 131071 }
- { 709, 2833, 3541, 12037, 31153, 174877, 184081 }
- { 1861, 5581, 11161, 26041, 37201, 87421, 102301 }
- { 6421, 12841, 51361, 57781, 115561, 192601, 205441 }
For example, 1118863200025063181061994266818401 = 6421 * 12841 * 51361 * 57781 * 115561 * 192601 * 205441 is a super-Poulet number with 7 distinct prime factors and 120 Poulet numbers.
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function. It can be defined more formally as the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.
Fermat's little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
In mathematics the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of
and is not a divisor of
for any k < n. Its roots are all nth primitive roots of unity
, where k runs over the positive integers not greater than n and coprime to n. In other words, the nth cyclotomic polynomial is equal to
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might be called compositeness tests instead of primality tests.
The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. It was first discovered by Russian mathematician M. M. Artjuhov.
Gary L. Miller rediscovered it; Miller's version of the test is deterministic, but its correctness relies on the unproven extended Riemann hypothesis. Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm.
In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and
In number theory, a sphenic number is a positive integer that is the product of three distinct prime numbers.
In number theory, a deficient or deficient number is a number n for which the sum of divisors σ(n)<2n, or, equivalently, the sum of proper divisors s(n)<n. The value 2n − σ(n) is called the number's deficiency.
In number theory, a Wieferich prime is a prime number p such that p2 divides 2p − 1 − 1, therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides 2p − 1 − 1. Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's last theorem, at which time both of Fermat's theorems were already well known to mathematicians.
In recreational number theory, a unique prime or unique period prime is a certain kind of prime number. A prime p ≠ 2, 5 is called unique if there is no other prime q such that the period length of the decimal expansion of its reciprocal, 1 / p, is equal to the period length of the reciprocal of q, 1 / q. For example, 3 is the only prime with period 1, 11 is the only prime with period 2, 37 is the only prime with period 3, 101 is the only prime with period 4, so they are unique primes. In contrast, 41 and 271 both have period 5; 7 and 13 both have period 6; 239 and 4649 both have period 7; 73 and 137 both have period 8; 21649 and 513239 both have period 11; 53, 79 and 265371653 all have period 13; 31 and 2906161 both have period 15; 17 and 5882353 both have period 16; 2071723 and 5363222357 both have period 17; 19 and 52579 both have period 18; 3541 and 27961 both have period 20. Therefore, none of these is a unique prime. Unique primes were first described by Samuel Yates in 1980.
In mathematics, a semiprime is a natural number that is the product of two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers.
Because there are infinitely many prime numbers, there are also infinitely many semiprimes. Semiprimes are also called biprimes.
The Lucas numbers or Lucas series are an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–91), who studied both that sequence and the closely related Fibonacci numbers. Lucas numbers and Fibonacci numbers form complementary instances of Lucas sequences.
In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. When referred to as the divisor function, it counts the number of divisors of an integer. It appears in a number of remarkable identities, including relationships on the Riemann zeta function and the Eisenstein series of modular forms. Divisor functions were studied by Ramanujan, who gave a number of important congruences and identities; these are treated separately in the article Ramanujan's sum.
105 is the natural number following 104 and preceding 106.
4000 is the natural number following 3999 and preceding 4001. It is a decagonal number.
An untouchable number is a positive integer that cannot be expressed as the sum of all the proper divisors of any positive integer. That is, these numbers are not in the image of the aliquot sum function. Their study goes back at least to Abu Mansur al-Baghdadi, who observed that both 2 and 5 are untouchable.
In number theory, a probable prime is a number that passes a primality test.
A strong probable prime is a number that passes a strong version of a primality test.
A strong pseudoprime is a composite number that passes a strong version of a primality test.
All primes pass these tests, but a small fraction of composites also pass, making them "false primes".
The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff.
A cyclic number is a natural number n such that n and φ(n) are coprime. Here φ is Euler's totient function. An equivalent definition is that a number n is cyclic if and only if any group of order n is cyclic.