Pocklington's Criterion: A Closer Look

[CRGreathouse]

http://mathworld.wolfram.com/PocklingtonsCriterion.html

I'm confused by the statement of this theorem. Either there's a mistake in the explanation, or I'm missing something pretty big.

Let me take an example and go through step by step. Let p=3 and k=4. p is an odd prime and 1 <= 4 <= 8. 3 does not divide 4.

The statement on MathWorld seems to say that 1 and 2 are equivilent:
1. 25 = 2 * 4 * 3 + 1 is prime.
2. There exists an a such that GCD(a^4+1, 25)=1.

5*5=25 is not prime. Checking briefly:
GCD(1,25)=1
GCD(2,25)=1
GCD(17,25)=1
GCD(82,25)=1
GCD(257,25)=1
GCD(626,25)=1

What am I misunderstanding?

 

[shmoe]

Odd, Mathworld seems to leave out a couple of conditions. You also need

2<=a<N

and

N divides a^(kp)+1

for condition 2.

This is in Ribenboim's My Numbers, My Friends.

 

[CRGreathouse]

I knew there was something. The entry was overly sparse.

Thanks!