# phi(n) divides n-1 implies n is prime

• Mar 6th 2012, 03:55 AM
abhishekkgp
phi(n) divides n-1 implies n is prime
Prove that if $\phi(n)|(n-1)$ then $n$ is prime, where $\phi(n)$. is the Euler's totient function.

I am able to show that $n$ is square-free under the above condition.
• Mar 6th 2012, 04:40 AM
princeps
Re: phi(n) divides n-1 implies n is prime
Quote:

Originally Posted by abhishekkgp
Prove that if $\phi(n)|(n-1)$ then $n$ is prime, where $\phi(n)$. is the Euler's totient function.

I am able to show that $n$ is square-free under the above condition.

Lehmer's conjecture
• Mar 6th 2012, 05:09 AM
abhishekkgp
Re: phi(n) divides n-1 implies n is prime
Quote:

Originally Posted by princeps

Thank You. I did not know its an unsolved problem or I would not post it.