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

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