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

Homework Help: Primality testing

  1. Apr 3, 2006 #1
    I'm having trouble with this problem

    Let n be a positive integer. Show that if the prime-power factorization of n-1 is n-1=(p1)^(a1)*(p2)^(a2)*......*(pt)^(at) , and for j=1,2,.....,t, there exists an integer xj such that
    (xj)^(n-1)/(pj) is incongruent to 1(modn)
    and
    (xj)^(n-1)≡1(modn)
    then n is prime
    when I write (pt),(xj).... I mean p sub t and x sub j

    so far I have
    we know ordn(xj)|(n-1)
    suppose ordn(xj)≠n-1 then there exists and integer k s.t. n-1=kordn(xj) and we know k>1
    (xj)^(n-1)\(pj)=(xj)^((kordn(xj))/(pj))=((xj)^ordn(xj))^(k/(pj))≡1(modp)
    this is a condridiction to the original statement
    therefore ordn(xj)=n-1 ordn(xj)<=Φ(n)<=n-1
    Φ(n)=n-1 and n is prime

    the problem i'm encountering is we know (xj)^(n-1)/(pj) is incongruent to 1(modn) but (xj)^(n-1)/(pi) may not be incongruent to 1(modn) for an i≠j
    can anyone help me with this problem?
    thanks
     
  2. jcsd
  3. Apr 4, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    You can't get around this problem. If n is prime, just take xj to be an element with order pj^aj.

    Fortunately though, you don't need to. Just consider the condition for one value of j at a time. What does it tell you about the power of pj that appears in phi(n)?
     
  4. Apr 5, 2006 #3
    The power of pj that appears in phi(n) is aj. I'm not sure what the exact value of aj is or where you would go from there. Is there a way I could get an answer or a common base by multiplying all of the xj's together to get one base incongruent 1(modn)?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook