Difference between revisions of "Poulet number"
From Number
(→Facts) |
(→Initial examples) |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 13: | Line 13: | ||
===Initial examples=== | ===Initial examples=== | ||
| − | The first few Poulet numbers are < | + | The first few Poulet numbers are: |
| + | |||
| + | <section begin="list"/>[[341]], [[561]], [[645]], [[1105]], [[1387]], [[1729]], [[1905]], [[2047]], <toggledisplay>[[2465]], [[2701]], [[2821]], 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341</toggledisplay> [[Oeis:A001567|View list on OEIS]]<section end="list"/> | ||
These include, for instance: | These include, for instance: | ||
| Line 31: | Line 33: | ||
! Statement !! Kind of numbers it says are Poulet numbers !! Smallest example !! Proof idea | ! Statement !! Kind of numbers it says are Poulet numbers !! Smallest example !! Proof idea | ||
|- | |- | ||
| − | | [[Mersenne number for prime or Poulet implies prime or Poulet]] || 2047 (<math>M_{11}</math>)|| <math> | + | | [[Mersenne number for prime or Poulet implies prime or Poulet]] || <math>M_n = 2^n - 1</math> where <math>n</math> itself is a Poulet number OR <math>M_n</math> where <math>n</math> is prime and <math>M_n</math> isn't || 2047 (<math>M_{11}</math>) factors as <math>23 * 89</math> || Use that <math>x - 1</math> divides <math>x^m - 1</math> as a polynomial with integer coefficients. |
| + | |- | ||
| + | | [[Composite Fermat number implies Poulet number]] || <math>F_n = 2^{2^n} + 1</math> where <math>F_n</math> is ''not'' prime || 4294967297 (<math>F_5</math>) factors as <math>641* 6700417</math> || Use that <math>x - 1</math> divides <math>x^m - 1</math> as a polynomial with integer coefficients, and also that <math>2^{n+1}</math> divides <math>2^{2^n}</math> because <math>n + 1 \le 2^n</math>. | ||
| + | |- | ||
| + | | [[Square of Wieferich prime is Poulet number]] || <math>p^2</math> where <math>p</math> is a prime such that <math>2^{p-1} \equiv 1 \pmod {p^2}</math> || 1194649 (square of 1093) || Use that <math>x - 1</math> divides <math>x^m - 1</math> as a polynomial with integer coefficients twice (in base, then in exponent) | ||
|- | |- | ||
| − | | [[ | + | | [[Product of successive primes in Cunningham chain of the second kind satisfying congruence conditions is Poulet number]] || <math>p(2p - 1)</math> where <math>p \equiv 1 \pmod {12}</math> and both <math>p,2p-1</math> are primes || 2701 (product of 37 and 73) || apply [[Fermat's little theorem]], condition for 2 to be a quadratic residue |
|- | |- | ||
| [[Infinitude of Poulet numbers]] || N/A || N/A || Use the Mersenne number iteratively, after having found at least one Poulet number. | | [[Infinitude of Poulet numbers]] || N/A || N/A || Use the Mersenne number iteratively, after having found at least one Poulet number. | ||
Latest revision as of 21:23, 15 January 2012
Template:Pseudoprimality property
Contents
Definition
A Poulet number or Sarrus number is an odd composite number 
such that:
.
In other words, divides 
. Equivalently, is a Fermat pseudoprime modulo 
.
Occurrence
Initial examples
The first few Poulet numbers are:
341, 561, 645, 1105, 1387, 1729, 1905, 2047, [SHOW MORE] View list on OEISThese include, for instance:
- The Mersenne number
, which is a Poulet number on account of the fact that Mersenne number for prime or Poulet implies prime or Poulet.
- Three Carmichael numbers -- these are numbers that are pseudoprime to every relatively prime base. These are
. 
is also known as the Hardy-Ramanujan number, and is the smallest number expressible as the sum of two cubes in two distinct ways.
Infinitude
Further information: Infinitude of Poulet numbers
There are infinitely many Poulet numbers. This can be proved in many ways. For instance, Mersenne number for prime or Poulet implies prime or Poulet. This shows that if we find one Poulet number, we can iterate the operation of taking the Mersenne number and obtain infinitely many Poulet numbers.
Facts
| Statement | Kind of numbers it says are Poulet numbers | Smallest example | Proof idea |
|---|---|---|---|
| Mersenne number for prime or Poulet implies prime or Poulet |  where itself is a Poulet number OR  where is prime and isn't |
2047 ( ) factors as  |
Use that  divides  as a polynomial with integer coefficients.
|
| Composite Fermat number implies Poulet number |  where  is not prime |
4294967297 ( ) factors as  |
Use that divides as a polynomial with integer coefficients, and also that  divides  because  .
|
| Square of Wieferich prime is Poulet number |  where  is a prime such that  |
1194649 (square of 1093) | Use that divides as a polynomial with integer coefficients twice (in base, then in exponent)
|
| Product of successive primes in Cunningham chain of the second kind satisfying congruence conditions is Poulet number |  where  and both  are primes |
2701 (product of 37 and 73) | apply Fermat's little theorem, condition for 2 to be a quadratic residue |
| Infinitude of Poulet numbers | N/A | N/A | Use the Mersenne number iteratively, after having found at least one Poulet number. |
Relation with other properties
Stronger properties
- Absolute pseudoprime (at least, for odd numbers).
