1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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)
    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
    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?
  2. jcsd
  3. Apr 4, 2006 #2


    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