Abstract Algebra: Why is the number of prime numbers to a set $\mathbb{Z}_n$ usually $\varphi(n)$

I've been trying to figure this out all night with no luck.

Here is what I've noticed: $\varphi(n)$ is the number of units or generators of a set. I'm trying to connect this to $n^p$ being congruent to $n \pmod p$ where $\gcd(n,p) = 1$. But I don't see it. Why would this tell me that the number of numbers relatively prime to $n$ is $n^p - n^{p-1}$?

-
I actually meant n^p - n^(p - 1). Sorry. – crazy student Sep 30 '11 at 9:15
Please edit the correction into the body of the question (using the "edit" link) so people don't have to read the comments to understand the question. – joriki Sep 30 '11 at 9:37
a) Please don't put fields like "abstract algebra" into the title; this is what the tags are for. b) I think (elementary-number-theory) is a better tag for this than (abstract-algebra). c) I don't understand the title -- what are "prime numbers to a set"? d) The number of numbers relatively prime to $n$ is neither $n^p-n$, nor $n^p-n^{p-1}$; is there another typo there? e) Please use $\TeX$ formatting by enclosing formulas in dollar signs; you can right-click on any formula and select "Show Source" to see how to produce it. – joriki Sep 30 '11 at 9:41
You edited the question without addressing a single one of my comments. Please engage with comments provided under your questions in an attempt to improve them. – joriki Sep 30 '11 at 10:25
@crazystudent: Please clean up the title and the body of the question. – Arturo Magidin Sep 30 '11 at 13:26

Fermat's Little Theorem follows from the following two observations:

• $\varphi(p) = p-1$ when $p$ is a prime. Because every number $d$, $1\leq d\lt p$, is relatively prime to $p$. (In fact, this is an alternative definition for prime number in the integers).

• A corollary to Lagrange's Theorem: If $G$ is a finite group with $k$ elements in it, and $a\in G$, then $a^k=1$.

Now let $n$ be any integer; if $\gcd(n,p)=p$, then $n\equiv 0\pmod{p}$, so $n^p\equiv 0^p \equiv 0\equiv n\pmod{p}$. If $\gcd(n,p)=1$, then look at the group of units modulo $p$. It contains the class of $n$, and has order $\varphi(p)=p-1$. So $n^{p-1}\equiv 1 \pmod{p}$ by Lagrange's Theorem. Multiplying through by $n$ we get $n^p\equiv n\pmod{p}$.

Finally, it is not true that the number of integers relatively prime to $n$ is $n^p-n^{p-1}$, in any reasonable or sensible understanding of the terms and formulas. For one thing, $n$ is fixed, but $p$ is an arbitrary prime.

Perhaps you are asking why the number of positive integers relatively prime to $p^n$ and smaller than $p^n$ is $p^n-p^{n-1} = p^{n-1}(p-1)$ (i.e., $\varphi(p^n)=p^n-p^{n-1}$?

An integer is relatively prime to $p^n$ if and only if it is not divisible by $p$. Of the $p^n$ nonnegative integers smaller than $p^n$, which ones are multiples of $p$? We have $0$, $p$, $2p$, $3p,\ldots,(p-1)p$, $p^2, (p+1)p,\ldots,(p^{n-1}-1)p$, and that's it. There are exactly $p^{n-1}$ of them. So out of all $p^n$ integers, we need to take out $p^{n-1}$ of them, leaving us with exactly $p^n-p^{n-1}$ that are relatively prime to $p$. So $\varphi(p^n)=p^{n}-p^{n-1}=p^{n-1}(p-1)$.

-
Or use the general formula that the interval $\rm\: [a,b)\:$ has exactly $\rm\:(b-a)/c\:$ multiples of $\rm\:c\$ if $\rm\ c\ |\ b-a\:.$ Hence for $\rm\:a=0,\ b = p^n,\ c= p\$ we infer that $\rm\:[0,p^n)\:$ has $\rm\:(p^n-0)/p = p^{n-1}\:$ multiples of $\rm\:p\:.\qquad$ – Bill Dubuque Sep 30 '11 at 16:12
Thank you Arturo, you are so understandable! – crazy student Sep 30 '11 at 21:44
@crazystudent: Can you please clean up the question? – Arturo Magidin Oct 1 '11 at 3:26