Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
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. –  joriki Sep 30 '11 at 9:41
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. –  joriki Sep 30 '11 at 10:25
1  
@crazystudent: Please clean up the title and the body of the question. –  Arturo Magidin Sep 30 '11 at 13:26

1 Answer 1

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.