Infinitude of Poulet numbers - Revision history

Vipul: Created page with '{{infinitude fact}} ==Statement== There exist infinitely many fact about::Poulet numbers, i.e., there infinitely many odd composite numbers $n$ such that:
2009-04-22T00:23:41Z

Created page with '{{infinitude fact}} ==Statement== There exist infinitely many fact about::Poulet numbers, i.e., there infinitely many odd composite numbers <math>n</math> such that: <math...'

New page
{{infinitude fact}}

==Statement==

There exist infinitely many [[fact about::Poulet number]]s, i.e., there infinitely many odd composite numbers <math>n</math> such that:

<math>2^{n-1} \equiv 1 \pmod n</math>.

==Facts used==

# [[uses::Mersenne number for prime or Poulet implies prime or Poulet]]
# [[uses::Mersenne number for composite number is composite]]

==Proof==

By fact (1), if <math>n</math> is a Poulet number, the Mersenne number <math>M_n</math> is either prime or a Poulet number. But by fact (2), it cannot be prime. Thus, the Mersenne number for a Poulet number is a Poulet number.

Thus, suppose <math>a</math> is a Poulet number. Consider the sequence:

<math>a_0 = a, \qquad a_{i+1} = M_{a_i}</math>.

In other words, each member of the sequence is the Mersenne number for the preceding number. This is a strictly increasing sequence, and each member of it is a Poulet number, so if there is one Poulet number, there are infinitely many Poulet numbers.

Thus, it is sufficient to find just one Poulet number. Using fact (1), consider <math>M_{11} = 2047 = 23 \cdot 89</math>. This is not prime, so by fact (1), it is a Poulet number, and this completes the proof.