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, 06: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, 07:52 AMHallsofIvy
- Nov 16th 2009, 02: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, 03:13 PMDrexel28
Note that what this is really saying is that $\displaystyle n$ has exactly two divisors. And since $\displaystyle 1,n$ are always divisors of $\displaystyle 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.