Thread: Prime Power Factorization and Modulo

Show that if the prime power factorization of n-1 is p1^a1...pt^at and that there exists integers xj , for j = 1,2,3,...,t such that for each j:

xj^[(n-1)/pj] is not congruent to 1 (mod n)

and

xj^(n-1) is congruent to 1 (mod n)

then n is a prime.

Any ideas on how to prove the above? Thanks

Originally Posted by KatyCar

Show that if the prime power factorization of n-1 is p1^a1...pt^at and that there exists integers xj , for j = 1,2,3,...,t such that for each j:

xj^[(n-1)/pj] is not congruent to 1 (mod n)

and

xj^(n-1) is congruent to 1 (mod n)

then n is a prime.

Any ideas on how to prove the above? Thanks

The proof can be found here.

try that, full proof

Wilson's Theorem and Fermat's Theorem