User:David J Wilson/sandbox1

From Wikipedia, the free encyclopedia

< User:David J Wilson

[edit] Other formulas involving Euler's function

$\;\varphi\left(n^m\right) = n^{m-1}\varphi(n)\text{ for }m\ge 1$

$\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}$

$\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)\text{ for }n>1$

$\sum_{k=1}^n\varphi(k) = \frac{1}{2}\left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)$

$\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor$

$\sum_{k=1}^n\frac{k}{\varphi(k)} = \mathcal{O}(n)$

$\sum_{k=1}^n\frac{1}{\varphi(k)} = \mathcal{O}(\log(n))$

$\sum_{1\le k\le n \atop (k,m)=1} 1 = n \frac {\varphi(m)}{m} + \mathcal{O} \left ( 2^{\omega(m)} \right ),$

where m > 1 is a positive integer and ω(m) designates the number of distinct prime factors of m. (This formula counts the number of naturals less than or equal to n and relatively prime to m, additional material is listed among the external links.)

Proofs of some of these identities can be seen by clicking on "show".
Click on "hide" (to the far right on the line above) to hide these proofs. [edit] Proofs of totient identities involving the floor function The proof of the identity $\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor$ is by mathematical induction on $n$ . The base case is $n = 1$ and we see that the claim holds: $\varphi(1)/1 = 1 = \frac{\mu(1)}{1} \left\lfloor 1\right\rfloor.$ For the induction step we need to prove that $\frac{\varphi(n+1)}{n+1} = \sum_{k=1}^n\frac{\mu(k)}{k} \left(\left\lfloor\frac{n+1}{k}\right\rfloor - \left\lfloor\frac{n}{k}\right\rfloor\right) + \frac{\mu(n+1)}{n+1}.$ The key observation is that $\left\lfloor\frac{n+1}{k}\right\rfloor - \left\lfloor\frac{n}{k}\right\rfloor \; = \; \begin{cases} 1, & \mbox{if }k\|(n+1) \\ 0, & \mbox{otherwise, } \end{cases}$ so that the sum is $\sum_{k\|n+1,\; k<n+1} \frac{\mu(k)}{k} + \frac{\mu(n+1)}{n+1} = \sum_{k\|n+1} \frac{\mu(k)}{k}.$ Now the fact that $\sum_{k\|n+1} \frac{\mu(k)}{k} = \frac{\varphi(n+1)}{n+1}$ is a basic totient identity. To see that it holds, let $p_1^{v_1} p_2^{v_2} \ldots p_q^{v_q}$ be the prime factorization of n+1. Then $\frac{\varphi(n+1)}{n+1} = \prod_{l=1}^q \left( 1 - \frac{1}{p_l} \right) = \sum_{k\|n+1} \frac{\mu(k)}{k}$ by definition of $μ(k).$ This concludes the proof.^{[citation needed]} An alternate proof proceeds by substituting $\frac{\varphi(k)}{k} = \sum_{d\|k}\frac{\mu(d)}{d}$ directly into the left side of the identity, giving $\sum_{k=1}^n \sum_{d\|k}\frac{\mu(d)}{d}.$ Now we ask how often the term $\begin{matrix}\frac{\mu(d)}{d}\end{matrix}$ occurs in the double sum. The answer is that it occurs for every multiple $k$ of $d$ , but there are precisely $\begin{matrix}\left\lfloor\frac{n}{d}\right\rfloor\end{matrix}$ such multiples, which means that the sum is $\sum_{d=1}^n\frac{\mu(d)}{d}\left\lfloor\frac{n}{d}\right\rfloor$ as claimed.^{[citation needed]} The trick where zero values of^{[citation needed]} $\begin{matrix} \left\lfloor\frac{n+1}{k}\right\rfloor - \left\lfloor\frac{n}{k}\right\rfloor \end{matrix}$ are filtered out may also be used to prove the identity $\sum_{k=1}^n\varphi(k) = \frac{1}{2}\left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right).$ The base case is $n = 1$ and we have $\varphi(1) = 1 = \frac{1}{2} \left(1+ \mu(1) \left\lfloor\frac{1}{1}\right\rfloor^2\right)$ and it holds. The induction step requires us to show that $\varphi(n+1) = \frac{1}{2} \sum_{k=1}^n \mu(k) \left( \left\lfloor\frac{n+1}{k}\right\rfloor^2 - \left\lfloor\frac{n}{k}\right\rfloor^2 \right) \; + \; \frac{1}{2} \; \mu(n+1) \; \left\lfloor\frac{n+1}{n+1}\right\rfloor^2 .$ Next observe that^{[citation needed]} $\left\lfloor\frac{n+1}{k}\right\rfloor^2 - \left\lfloor\frac{n}{k}\right\rfloor^2 \; = \; \begin{cases} 2\frac{n+1}{k} - 1, & \mbox{if }k\|(n+1) \\ 0, & \mbox{otherwise.} \end{cases}$ This gives the following for the sum $\frac{1}{2} \sum_{k\|n+1, \; k<n+1} \mu(k) \left( 2\frac{n+1}{k} - 1 \right) \; + \; \frac{1}{2} \; \mu(n+1) = \frac{1}{2} \sum_{k\|n+1} \mu(k) \left( 2 \; \frac{n+1}{k} - 1 \right).$ Treating the two inner terms separately, we get $(n+1) \sum_{k\|n+1} \frac{\mu(k)}{k} - \frac{1}{2} \sum_{k\|n+1} \mu(k).$ The first of these two is precisely $\varphi(n+1)$ as we saw earlier, and the second is zero, by a basic property of the Möbius function (using the same factorization of $n + 1$ as above, we have $\begin{matrix} \sum_{k\|n+1} \mu(k) = \prod_{l=1}^q (1-1) = 0 \end{matrix}$ .) This concludes the proof. This result may also be proved by inclusion-exclusion. Rewrite the identity as $-1 + 2\sum_{k=1}^n\varphi(k) = \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2.$ Now we see that the left side counts the number of lattice points (a, b) in [1,n] × [1,n] where a and b are relatively prime to each other. Using the sets $A p$ where p is a prime less than or equal to n to denote the set of points where both coordinates are divisible by p we have $\left\| \bigcup_p A_p \right\| = \sum_p \left\| A_p \right\| \; - \; \sum_{p<q} \left\| A_p \cap A_q \right\| \; + \; \sum_{p<q<r} \left\| A_p \cap A_q \cap A_r \right\| \; - \; \cdots \; \pm \; \left\| A_p \cap \; \cdots \; \cap A_s \right\|.$ This formula counts the number of pairs where a and b are not relatively prime to each other. The cardinalities are as follows: $\left\| A_p \right\| = \left\lfloor \frac{n}{p} \right\rfloor^2, \; \left\| A_p \cap A_q \right\| = \left\lfloor \frac{n}{pq} \right\rfloor^2, \; \left\| A_p \cap A_q \cap A_r \right\| = \left\lfloor \frac{n}{pqr} \right\rfloor^2, \; \ldots$ and the signs are $\begin{matrix}-\mu(pqr\cdots)\end{matrix}$ , hence the number of points with relatively prime coordinates is $\mu(1)\, n^2 \; + \; \sum_p \mu(p) \left\lfloor \frac{n}{p} \right\rfloor^2 \; + \; \sum_{p<q} \mu(p q) \left\lfloor \frac{n}{pq} \right\rfloor^2 \; + \; \sum_{p<q<r} \mu(p q r) \left\lfloor \frac{n}{pqr} \right\rfloor^2 \; + \; \cdots$ but this is precisely $\sum_{k=1}^n \mu(k) \left\lfloor \frac{n}{k} \right\rfloor^2$ and we have the claim.

Views

Interaction

Search