Poulet number: Difference between revisions

Revision as of 19:59, 2 January 2012

Definition

A Poulet number or Sarrus number is an odd composite number $n$ such that:

$2^{n-1}\equiv 1\mod n$ .

In other words, $n$ divides Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{n-1}-1} . Equivalently, $n$ is a Fermat pseudoprime modulo $2$ .

Occurrence

Initial examples

The first few Poulet numbers are Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 341,561,645,1105,1387,1729,1905,2047} .

These include, for instance:

The Mersenne number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_{11} = 2047} , 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 561, 1105, 1729} . Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1729} 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	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_n = 2^n - 1} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} itself is a Poulet number OR Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_n} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is prime and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_n} isn't	2047 (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_{11}} ) factors as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 23 * 89}	Use that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x - 1} divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^m - 1} as a polynomial with integer coefficients.
Composite Fermat number implies Poulet number	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n = 2^{2^n} + 1} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_n} is not prime	4294967297 (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_5} ) factors as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 641* 6700417}	Use that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x - 1} divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^m - 1} as a polynomial with integer coefficients, and also that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{n+1}} divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{2^n}} because Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n + 1 \le 2^n} .
Square of Wieferich prime is Poulet number	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^2} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is a prime such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{p-1} \equiv 1 \pmod {p^2}}	1194649 (square of 1093)	Use that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x - 1} divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^m - 1} 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	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(2p - 1)} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \equiv 1 \pmod {12}} and both Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p,2p-1} 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).

@@ Line 37: / Line 37: @@
 | [[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 || apply Fermat's little theorem, condition for 2 to be a quadratic residue
+| [[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.