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

From Number

## Contents

## 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

## 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 .