5
$\begingroup$

Why is it that the euler totient function has the following condition true based on its definition?

$$ \phi(p^k)=p^{k-1}(p-1) = p^k(1-\frac{1}{p}) = p^k-p^{k-1} $$

A proof would be awesome and an intuition on why this is true would be even better!

(to prove it I thought of using multiplicativity of the totient function but that would not work because p is not coprime to itself :( )

A more detailed explanation of the wikipedia article will get a like and accepted answer.

To get accepted, giving an explanation on why the number of multiples of p is $p^{k-1}$ will be an important factor. Also, are the multiples of p we are excluding between 1 to $p^k - 1$ or to $p^k$?

Some kind of counting argument is necessary to get accepted.

$\endgroup$
4
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – PITTALUGA
    Jan 7, 2014 at 8:12
  • 1
    $\begingroup$ Look at it as $p^k - p^{k-1}$. $\endgroup$ Jan 7, 2014 at 8:23
  • $\begingroup$ If you want I can accept your answers if you provide a little more detailed explanation of $p^k -p^{k-1}$ or the Wikipedia article. Specifically, I am a little unsure about the $p^{k-1}$. Thanks thought, it has been helpful. $\endgroup$ Jan 8, 2014 at 0:22
  • $\begingroup$ Bounty started to address the details of $p^{k}-p^{k-1}$. $\endgroup$ Jan 10, 2014 at 17:21

5 Answers 5

18
+50
$\begingroup$

Any positive integer $x$ less than $p^k$ can be written in base $p$ as $$ x = a_0 + a_1 p + a_2 p^2 + \cdots + a_{k-1} p^{k-1} $$ where $a_i \in \{0, 1, 2, \ldots, p-1\}$. Then $x$ is not relatively prime to $p^k$ iff $p \mid x$ iff $a_0 = 0$. Thus if we want $x$ to be relatively prime to $p^k$ we have $p-1$ choices for $a_0$ and $p$ choices for each of the other $k-1$ coefficients, hence $\varphi(p^k) = (p-1)p^{k-1}$.

$\endgroup$
3
  • 1
    $\begingroup$ This was such a unexpected and cute answer! kudos on that, I would have never had thought of it that way. $\endgroup$ Jan 13, 2014 at 5:58
  • $\begingroup$ For future reference, answer provided by user115654 also provides a great reference if this one did not make sense. $\endgroup$ Jan 13, 2014 at 6:15
  • 2
    $\begingroup$ I was learning about the $p$-adic numbers when I first saw this result, so it was very natural at the time! $\endgroup$ Jan 13, 2014 at 6:33
10
$\begingroup$

Here is intiution....

Take $p^2$. How many numbers in the range $1 \ldots p^2$ are not co-prime to it? They are precisely $p$, $2p$, $3p$ ... $p^2$. There are exactly $p$ of them. So the number co prime to $p^2$ is $$ \phi(p^2) = p^2 -p = p (p-1)$$

You can do the same for $p^3$ to get $$ \phi(p^3) = p^3 -p^2 = p^2 (p-1)$$

You can turn this into a proof by induction if you so wish.

$\endgroup$
4
$\begingroup$

I find it intuitive to think in terms of "what are the chances of not being coprime to $p^k$?"

Once you realize that "coprime to $p^k$" is synonymous with "not divisible by $p$", it suggests the proportion of numbers up to $p^k$ which are coprime to $p^k$ is $1 - \frac1p$, motivating the quantity $p^k(1-\frac1p)$.

The same reasoning applies to general $n$ (but takes more effort to justify carefully): "coprime to $n$" is synonymous with "not divisible by any of the prime factors of $n$", and if you can convince yourself that the individual probabilities are independent this suggests $\phi(n) = n\prod_{p\mid n} (1-\frac1p)$.

$\endgroup$
2
  • $\begingroup$ How do you know that the proportion of elements that are coprime to $p^k$ is $1 - \frac{1}{p}$? $\endgroup$ Jan 13, 2014 at 6:37
  • 1
    $\begingroup$ @Pinocchio Because the proportion that are divisible by $p$ is $\frac1p$. $\endgroup$
    – Erick Wong
    Jan 14, 2014 at 4:50
1
$\begingroup$

$p^k$ only shares common factors with other multiples of $p$. How many multiples of $p$ are there under $p^k$?: $\frac{p^k}{p}=p^{k-1}$ Just look at 8 for example. There are 4 multiples of 2 under and including 8. To get the totient value by definition exclude from $p^k$ all the values under it that share a common factor, of which there are $p^{k-1}$.

$\endgroup$
3
  • $\begingroup$ I am sorry if its extremely obvious to you, but if you provide further detail on why $p^k/p$ "works", I will be happy. It makes sense that you want to exclude element that are multiples of p. I'm not sure why just dividing $p^k$ by p works. Is $p^k$ the number of element between 1 to $p^k$ or the elements 1 from $p^{k-1}$? why did dividing by p "worked"? Basically I am having trouble counting the number of multiples of p rigorously or precisely. $\endgroup$ Jan 13, 2014 at 5:37
  • $\begingroup$ $p^k$ is an integer. An integer $n$ also denotes the size of the set of integers 1 through $n$, inclusive. Now starting from 1, say you jump to every multiple of $p$. You will be jumping a size of p every time first to p then to 2p then to 3p....So you have an integer $n=p^k$ and you want to see how many times you can make a jump of size p inside n. The division operation is defined to do just that. How many times does 3 fit in 12? 4 times. How many times does p fit in $p^k$? $p^{k-1}$ Does that make sense? $\endgroup$
    – Flowers
    Jan 13, 2014 at 7:06
  • $\begingroup$ The sets {1,2,...p}, {p+1,p+2,...2p}, {2p+1,2p+2,...3p}... {p^{k}-p+1,p^{k}-p+2,...p^{k}}are all size p and each one has only one multiple of p. $\endgroup$
    – Flowers
    Jan 13, 2014 at 7:15
1
$\begingroup$

Another explanation (much of which is implicit in the other answers):

A number $n$ is not coprime to $p \iff \text{gcd}(p,n) \neq 1 \iff \text{gcd}(p,n) = p \iff n$ is a multiple of $p$. Now the multiples of $p$ between $1$ and $p^k$ are precisely the numbers $mp$, for $1 \leq m \leq p^{k-1}$, of which there are $p^{k-1}$. Subtracting these from the total gives $p^k - p^{k-1} = \phi(p^k)$.

$\endgroup$
4
  • $\begingroup$ Euler's totient function counts the number of elements $\pmod p^k$ that have a $gcd(x,p^k) = 1$. Thus, $0 \leq x \leq p^k -1$ are the only candidate elements to be in the set (We don't have to exclude 0 yet, because it will be excluded by your counting argument). Thus, now you apply your counting argument and m's range is $0 \leq m \leq p^{k-1} - 1$. Which yields the correct bound but is "more" correct. Right? Also, your first sentence in your second paragraph is hard to follow, do you mind rewriting that? (Thanks btw, that was super helpful). $\endgroup$ Jan 13, 2014 at 5:54
  • $\begingroup$ Yes, the range $1 \leq m \leq p^k$ is the same, modulo $p^k$, as the range $0 \leq m \leq p^k - 1$ (and the latter is preferable). I have changed the "iff"s to symbols, in an attempt to improve legibility $\endgroup$
    – zcn
    Jan 13, 2014 at 6:14
  • $\begingroup$ If the second one is preferred then why did you write the other one? $\endgroup$ Jan 13, 2014 at 6:18
  • 1
    $\begingroup$ Starting at 0 is preferable if your definition counts elements of $\mathbb{Z}/p^k\mathbb{Z}$, but starting at 1 is preferable if your definition counts elements of $\mathbb{N}$. I have opted for the latter, but as the two are equivalent, it really is a matter of personal choice $\endgroup$
    – zcn
    Jan 13, 2014 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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