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

Statement

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

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

Related facts

• Congruence condition on prime divisor of cyclotomic polynomial evaluated at an integer
• Quadratic nonresidue equals primitive root for Fermat prime

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 .