MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Prime divisors of n-1, prove n is prime [closed]

Hi everyone! I have a problem in solving my number theory homework. My question is as follows:

If $n$ is a positive integer and if an integer $x$ exists such that $x^{n-1}= 1 mod n$ and $x^{\frac{n-1}{q}} =/= 1 \mod n$ for all prime divisors $q$ of $n-1$, then $n$ is prime.

Please edit my writing because I cannot install MathJax in my computer. Thank you for any help!

I believe we have to use some reasoning on the order of $x$, but I don't know where to start. Thanks!

PLease let me know why you closed my question? Thanks!

-
MathOverflow is not for homework help. See the FAQ for suggestions of other sites to use - mathoverflow.net/faq#whatnot – François G. Dorais Mar 5 2011 at 4:31