- #1
buzzmath
- 112
- 0
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
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