Composite Fermat number implies Poulet number

From Number
Revision as of 00:10, 22 April 2009 by Vipul (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Statement

Suppose is a nonnegative integer. Let be the Fermat number:

.

Then:

.

In particular, if is composite, then is a Poulet number.

Related facts

Proof

Given: A nonnegative integer , .

To prove: .

Proof: For any nonnegative integer , . Thus, .

Now, for a Fermat number , the order of modulo is precisely . From the above, we conclude that the order of modulo divides , so .