# Difference between revisions of "Poulet number"

From Number

(→Facts) |
(→Facts) |
||

Line 31: | Line 31: | ||

! 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]] | + | | [[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>) || 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>. | + | | [[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>. |

|- | |- | ||

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

## Revision as of 19:08, 2 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 .

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

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