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$
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – PITTALUGA Jan 7 '14 at 8:12
  • 1
    $\begingroup$ Look at it as $p^k - p^{k-1}$. $\endgroup$ – ShreevatsaR Jan 7 '14 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$ – Pinocchio Jan 8 '14 at 0:22
  • $\begingroup$ Bounty started to address the details of $p^{k}-p^{k-1}$. $\endgroup$ – Pinocchio Jan 10 '14 at 17:21
15
+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$
  • $\begingroup$ This was such a unexpected and cute answer! kudos on that, I would have never had thought of it that way. $\endgroup$ – Pinocchio Jan 13 '14 at 5:58
  • $\begingroup$ For future reference, answer provided by user115654 also provides a great reference if this one did not make sense. $\endgroup$ – Pinocchio Jan 13 '14 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$ – André 3000 Jan 13 '14 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$
  • $\begingroup$ How do you know that the proportion of elements that are coprime to $p^k$ is $1 - \frac{1}{p}$? $\endgroup$ – Pinocchio Jan 13 '14 at 6:37
  • 1
    $\begingroup$ @Pinocchio Because the proportion that are divisible by $p$ is $\frac1p$. $\endgroup$ – Erick Wong Jan 14 '14 at 4:50
2
$\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$
  • $\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$ – Pinocchio Jan 13 '14 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 '14 at 6:14
  • $\begingroup$ If the second one is preferred then why did you write the other one? $\endgroup$ – Pinocchio Jan 13 '14 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 '14 at 6:23
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$
  • $\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$ – Pinocchio Jan 13 '14 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 '14 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 '14 at 7:15

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.