phi(n) divides n-1 then is prime.

abhishekkgp

abhishekkgp

New member
Joined
Jan 23, 2012
Messages
25
Prove that if \(\displaystyle \phi(n) | (n-1)\) then \(\displaystyle n\) is prime.

I am able to show that under the above condition \(\displaystyle n\) is necessarily square free. How do I do the rest?
 
With group theory, this is not difficult. Going through the proofs for groups might lead you to a purely number-theoretic argument. Possibly using prime factorizations as well.

Let (Z/nZ)* be the set of nonzero elements of Z/nZ.

(Z/nZ)* is a group under multiplication if and only if (n,a)=1 for all 1 <= a < n. This is true because if (n,a) = d >1. then d*(n/d) does not belong to (Z/nZ)*. Conversely, it is relatively straight-forward to show that (n,a)=1, (n,b)=1 implies (ab,n)=1 and that every element has an inverse. It follows that (Z/nZ)* is a group (associativity and identity are trivial).

(n,a)=1 for all 1<= a< n if and only if phi(n)=|(Z/nZ)*| = n-1.
 
daon2 said:
With group theory, this is not difficult. Going through the proofs for groups might lead you to a purely number-theoretic argument. Possibly using prime factorizations as well.

Let (Z/nZ)* be the set of nonzero elements of Z/nZ.

(Z/nZ)* is a group under multiplication if and only if (n,a)=1 for all 1 <= a < n. This is true because if (n,a) = d >1. then d*(n/d) does not belong to (Z/nZ)*. Conversely, it is relatively straight-forward to show that (n,a)=1, (n,b)=1 implies (ab,n)=1 and that every element has an inverse. It follows that (Z/nZ)* is a group (associativity and identity are trivial).

(n,a)=1 for all 1<= a< n if and only if phi(n)=|(Z/nZ)*| = n-1.
Click to expand...

From what I can understand you have proved that:
(Z/nZ)* is a group if and only if n is a prime. (Agreed)

But then you have said:
(n,a)=1 for all 1<= a< n if and only if phi(n)=|(Z/nZ)*| = n-1
How do we get the "only if" part here?

Thank You.
 
abhishekkgp said:
From what I can understand you have proved that:
(Z/nZ)* is a group if and only if n is a prime. (Agreed)

But then you have said:
(n,a)=1 for all 1<= a< n if and only if phi(n)=|(Z/nZ)*| = n-1
How do we get the "only if" part here?

Thank You.
Click to expand...

(n,a)=1 for every 1 <= a < n means that phi(n)=n-1, that is the definition.

Moreover the units of n, U(n) is always a group with elements from (Z/nZ)*. U(n) has order phi(n), so if (Z/nZ)* is a group, phi(n) divides its order.

edit: actually you are right, this does not imply your question, not sure what I was thinking. I'm not sure how to approach it.
 
Last edited:
daon2 said:
(n,a)=1 for every 1 <= a < n means that phi(n)=n-1, that is the definition.

Moreover the units of n, U(n) is always a group with elements from (Z/nZ)*. U(n) has order phi(n), so if (Z/nZ)* is a group, phi(n) divides its order.

edit: actually you are right, this does not imply your question, not sure what I was thinking. I'm not sure how to approach it.
Click to expand...

I searched through the internet and now I have found this!
http://en.wikipedia.org/wiki/Euler's_totient_function


Look for Lehmer's conjecture on the page.
 
daon2 said:
haha so if i had answered this, you'd run away and steal the glory, eh? jk

did not know it was a famous conjecture
Click to expand...

When I saw "this can be solved using group theory..." I immediately started writing a paper!!! (lol)

Even I didn't know that this is an unsolved problem. My friend said that he had "discovered" it while he was working on a problem. He proved it (erroneously) then gave it to me as a challenge. When I gave up on the problem I asked him "show me your solution.." only to find a mistake in his argument.
Only now I know how HARD this was!!
 
You must log in or register to reply here.
Top