Prime divisor of Fermat number is congruent to one modulo large power of two

From Number
Jump to: navigation, search

Statement

Suppose is the Fermat number, i.e., . Then, we have:

  • If is a prime divisor of , then .
  • For , .

Related facts

Facts used

  1. Congruence condition for two to be a quadratic residue
  2. Fermat's little theorem

Proof

Given: A nonnegative integer . is the Fermat number. is a prime divisor of .

To prove: divides , and , divides .

Proof: Consider the order of modulo . We have:

.

Thus:

.

The order of modulo divides but does not divide . Hence, it equals .

On the other hand, by Fermat's little theorem, the order of modulo divides . Thus, divides .

Now consider the case . In this case, , and thus, by fact (1), is a quadratic residue modulo . Thus, there exists such that . This forces that the order of modulo is . Combining this with Fermat's little theorem, we obtain that divides .