Prime divisor of Fermat number is congruent to one modulo large power of two
Suppose is the Fermat number, i.e., . Then, we have:
- If is a prime divisor of , then .
- For , .
- Congruence condition on prime divisor of cyclotomic polynomial evaluated at an integer
- Quadratic nonresidue equals primitive root for Fermat prime
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:
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 .