Thread: Proving numbers in sequences and summation

Let n be a positive integer, and let k be the number of integers < n that are relatively prime to n.

Show that n is prime if and only if k = n-1.

Originally Posted by racewithferrari

Let n be a positive integer, and let k be the number of integers < n that are relatively prime to n.

Show that n is prime if and only if k = n-1.

It's pretty straight forward isn't it? Since there are exactly n-1 integers less than n to begin with, that is saying "n is prime if and only if it is relatively prime to every number less than it".

Can you elaborate your answer in an easy way so that I can understand, because I am new to this and I don't want my teacher to think that I have cheated.

Note that what this is really saying is that has exactly two divisors. And since are always divisors of we may conclude that they are the only divisors. But that is the defintion of primeness, that only the number itself and one are positive divisors.