help with Pepin's primatlity test

ezong · #1 $Old$ November 16th, 2009, 08:48 PM

In class today, the prof explained Pepin's test, but I got lost midway. This is what I have so far:
Let $F_{n}=2^{2^n}+1$ , then $\frac{F_{n}-1}{2}=2^{2^n-1}$ Call this number $q$ .
If $3^q \equiv -1 (mod$ $F_{n})$ (1), then $3^{2q} \equiv 1(mod$ $F_{n})$ . Because of (1), 2q is the order. What I don't understand is how this shows that $F_{n}$ is prime. I also don't get how $F_{n} \equiv 2(mod$ $3)$ .
Any help is much appreciated.

bictory · #2 $Old$ November 16th, 2009, 08:52 PM

Read this:
Pépin's test - Wikipedia, the free encyclopedia

Wikipedia for the win!

(I feel too tired right now to do anything useful)