# Proving numbers in sequences and summation

• Nov 15th 2009, 07:09 AM
racewithferrari
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.
• Nov 15th 2009, 08:52 AM
HallsofIvy
Quote:

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".
• Nov 16th 2009, 03:49 PM
racewithferrari
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.
• Nov 16th 2009, 04:13 PM
Drexel28
Note that what this is really saying is that $n$ has exactly two divisors. And since $1,n$ are always divisors of $n$ 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.