4
$\begingroup$

The following problem is the beginning of an easy proof using Möbius inversion to prove that if $p$ is a prime, then there are exactly $\phi(d)$ incongruent integers having order $d$ modulo $p$.

Let $p$ be a prime number. Given a positive divisor $d$ of $p-1$, let $f(d)$ be the number of integers between $1$ and $p-1$ inclusive having order $d$. Show that $$\sum_{c \mid d} f(c) = d.$$

My logic so far has been to say that since every integer between $1$ and $p-1$ inclusive has order dividing $p-1$, so $$\sum_{d \mid p-1} f(d) = p-1.$$ Now is there a simple way to extend the result to $d$ instead of $p-1$?

$\endgroup$
  • 2
    $\begingroup$ Do you mean maybe: $$\sum_{ c \mid d} \phi(c)=d$$ ? If so,you can take a look at my answer.. $\endgroup$ – evinda Jul 30 '14 at 10:00
2
$\begingroup$

$\forall n \geq 1$:

$$\sum_{d \mid n} \phi(d)=n$$

Proof:

We define the arithmetic function $F$ with:

$$F(n)=\sum_{d \mid n} \phi(d)$$

Suppose that $n$ is a power of a prime: $n=p^a$ with a prime $p$ and $a \geq 1$

Then,the positive divisors of $p^a$ are: $1,p, \dots,p^a$ and so:

$$F(p^a)=\phi(1)+\phi(p)+ \dots + \phi(p^a)=1+(p-1)+ \dots + (p^a-p^{a-1})=p^a$$

because the last sum is telescoping.

Because of the fact that $\phi$ is multiplicative,it implies that $F$ is also multiplicative. Therefore, $F(1)=1$ and, if $n>1$ and $n$ has the prime factorization $n=p_1^{a_1} \cdots p_k^{a_k}$,then:

$$F(n)=F(p_1^{a_1}) \cdots F(p_k^{a_k})=n$$

So,it stands $F(n)=n , \forall n \geq 1.$

$\endgroup$
  • 1
    $\begingroup$ Ah, I see. It was the reasoning why we should interpret it as summing over $\phi(d)$ that was the tricky part. $\endgroup$ – Numbersandsoon Aug 1 '14 at 19:20
2
$\begingroup$

Let $g$ be a primitive root of $p$ be $g$ (it exists, since $p$ is a prime).

For all $n\in[1,p-1]$ there uniquely exists $r\in[1,\phi(p)]=[1,p-1]$ such that $g^r\equiv n\pmod p$. So $\{1,2,\ldots,p-1\}$ is same as $\{g^1,g^2,\ldots,g^{p-1}\}$, on $\Bbb Z/p\Bbb Z$. (This is the basic property of the primitive root.)

Since the order of $g^r$ is $\phi(p)/(\phi(p),r)$, if the order of $g^r$ is $d$, $(\phi(p),r)=\phi(p)/d$, and the number of such $r$ is $\phi(d)$.

Thus what we want to prove is: $$\sum_{c\mid d}\phi(c)=d,$$ and that is the thing which evinda proved.

$\endgroup$
  • 1
    $\begingroup$ Ahh, I see! Very nice :). Perhaps this should be the accepted answer, as it was the reason why we should prove the summation you stated that was a little tricky. $\endgroup$ – Numbersandsoon Aug 1 '14 at 19:18
1
$\begingroup$

Interpreting your question in the same way as Evinda, here is a really nice proof of the resulting statement ($\sum_{d|n} \phi(d) = n$) that I learned from Pieter Moree.

Consider the fractions $\frac{1}{n}, \frac{2}{n}, \ldots, \frac{n}{n}$.

Clearly there are $n$ of them. If we all simplify them to lowest form, then each divisor $d$ of $n$ will appear as a denominator a number of times. Moreover the number of times denominator $d$ appears is equal to the number of enumerators that come with it, which is exactly the set of numbers smaller than and coprime to $d$.

So for each $d|n$ we get $\phi(d)$ fractions with denominator $d$ and in total there are still $n$ fractions, QED.

$\endgroup$
  • $\begingroup$ What a cool proof! Wish I could mark several answers as the accepted answer. $\endgroup$ – Numbersandsoon Aug 1 '14 at 19:19

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.