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.

Printable View

- Nov 15th 2009, 07:09 AMracewithferrariProving 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 AMHallsofIvy
- Nov 16th 2009, 03:49 PMracewithferrari
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 PMDrexel28
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.