Prime divisors of n-1, prove n is prime - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-25T08:05:05Z http://mathoverflow.net/feeds/question/57432 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57432/prime-divisors-of-n-1-prove-n-is-prime Prime divisors of n-1, prove n is prime yuki 2011-03-05T04:18:51Z 2011-03-05T22:45:58Z <p>Hi everyone! I have a problem in solving my number theory homework. My question is as follows:</p> <p>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. </p> <p>Please edit my writing because I cannot install MathJax in my computer. Thank you for any help!</p> <p>I believe we have to use some reasoning on the order of $x$, but I don't know where to start. Thanks!</p> <p>PLease let me know why you closed my question? Thanks!</p>