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

  • 0
    I actually meant n^p - n^(p - 1). Sorry.2011-09-30
  • 0
    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.2011-09-30
  • 1
    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.2011-09-30
  • 1
    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.2011-09-30
  • 0
    Are you asking why $\varphi(p^n) = p^{n}-p^{n-1}$?2011-09-30
  • 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
    Or use the [general formula](http://math.stackexchange.com/questions/68073/how-many-numbers-of-8-digits-and-9-digits-are-there-which-are-multiples-of-1/68086#68086) 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$2011-09-30
  • 0
    Thank you Arturo, you are so understandable!2011-09-30
  • 0
    @crazystudent: Can you please clean up the question?2011-10-01