Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pocklington's Criterion?

  1. Aug 9, 2006 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  2. jcsd
  3. Aug 10, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Aug 10, 2006 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

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

    Thanks!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Pocklington's Criterion?
Loading...