I'm having trouble with this problem(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Primality testing

**Physics Forums | Science Articles, Homework Help, Discussion**