$n$ is a positive prime number if only if $k^{n-1} \equiv 1$ mod $n$ with $1 < k < n$? When I read the Fermat's little theorem I found a problem, after that I found the problem is the Chinese hypothesis. 
When I read the Wilson's theorem I found that $(p-2)! \equiv -1 $ mod $p$ but after that I known this is special case of the Sylow theorems.
I can not prove, can not check by my computer the following statement because the Chinese hypothesis true up to $n={340}$ with $k$ is constant $2$. In here I let $1< k < n$


Is it true that if $n$ is a positive prime number if only if $k^{n-1} \equiv 1$ mod $n$ with for all $k$, $1 < k < n$




*

*If $n$ is positive prime number, by the Fermat's little theorem $\Rightarrow$ $k^{n-1} \equiv 1$ mod $n$.

*If $k^{n-1} \equiv 1$ mod $n$ with $k=1, 2, 3, ...,n-1$ then $n$ is also prime.


Or can you help me show that that why if $k^{n-1} \equiv 1$ mod $n$ then $gcd(k,n)=1$ ?


See also:


*

*Agoh–Giuga conjecture
 A: Suppose $n=pq$ is not a prime, and $p$ is a prime factor. Then $p^{n-1}$ has $p$ as a prime factor and can't be $\equiv 1 \bmod n$.
You may be interested in Carmichael Numbers which do have he property for all $k$ which are coprime with $n$ (eg $561$)
A: Fermat's Little Theorem shows that if $n$ is a prime number, then $k^{n-1} \equiv 1 \pmod n$ for all $1 \le k \lt n$. The converse is also true. To show this, consider $n \gt 1$ not being prime, i.e., $n = ab$ where $a,b$ are positive integers with $1 \lt a,b \lt n$. Then $a^{k-1} \not\equiv 1 \pmod n$ and $b^{k-1} \not\equiv \pmod n$ since $a^{k-1} - 1$ and $b^{k-1} - 1$ must be relatively prime to $a$ and $b$ respectively and, thus, can't be a multiple of $n$. As such, if for some $n \gt 1$ you have $k^{n-1} \equiv 1 \pmod n$ for all $1 \le k \lt n$, then $n$ must a prime.
This basically shows the last part you're asking about, i.e., if $k^{n-1} \equiv 1 \pmod n$, then consider $\gcd(k,n) = d$. Since $d \mid n$ and $n \mid k^{n-1} - 1$, then $d \mid k^{n-1} - 1$, but for $n \gt 1$ this can only be true for $d = 1$.
