1
$\begingroup$

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} $?

  • 1
    @crazystudent: Please clean up the title and the body of the question.2011-09-30

1 Answers 1

4

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)$.

  • 0
    @crazystudent: Can you please clean up the question?2011-10-01