# Primality testing

1. Apr 3, 2006

### buzzmath

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. Apr 4, 2006

### shmoe

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)?

3. Apr 5, 2006

### buzzmath

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)?