Vipul: Created page with '==Statement== Suppose $n$ is a nonnegative integer. Let $F_n$ be the $n^{th}$ fact about::Fermat number: $F_n = 2^{2^n} + 1$ . T...'

2009-04-22T00:10:30Z

Created page with '==Statement== Suppose <math>n</math> is a nonnegative integer. Let <math>F_n</math> be the <math>n^{th}</math> fact about::Fermat number: <math>F_n = 2^{2^n} + 1</math>. T...'

New page

==Statement==

Suppose <math>n</math> is a nonnegative integer. Let <math>F_n</math> be the <math>n^{th}</math> [[fact about::Fermat number]]:

<math>F_n = 2^{2^n} + 1</math>.

Then:

<math>2^{F_n - 1} \equiv 1 \pmod{F_n}</math>.

In particular, if <math>F_n</math> is composite, then <math>F_n</math> is a [[fact about::Poulet number]].

==Related facts==

* [[Prime divisor of Fermat number is congruent to one modulo large power of two]]
* [[Mersenne number for prime or Poulet is prime or Poulet]]
==Proof==

'''Given''': A nonnegative integer <math>n</math>, <math>F_n = 2^{2^n} + 1</math>.

'''To prove''': <math>2^{F_n - 1} \equiv 1 \pmod{F_n}</math>.

'''Proof''': For any nonnegative integer <math>n</math>, <math>n + 1 \le 2^n</math>. Thus, <math>2^{n+1} | 2^{2^n}</math>.

Now, for a Fermat number <math>F_n</math>, the order of <math>2</math> modulo <math>F_n</math> is precisely <math>2^{n+1}</math>. From the above, we conclude that the order of <math>2</math> modulo <math>F_n</math> divides <math>2^{2^n} = F_n - 1</math>, so <math>2^{F_n - 1} \equiv 1 \pmod {F_n}</math>.

Composite Fermat number implies Poulet number - Revision history

Vipul: Created page with '==Statement== Suppose n is a nonnegative integer. Let F_n be the n^{th} fact about::Fermat number: F_n = 2^{2^n} + 1. T...'

Vipul: Created page with '==Statement== Suppose $n$ is a nonnegative integer. Let $F_n$ be the $n^{th}$ fact about::Fermat number: $F_n = 2^{2^n} + 1$ . T...'