Number TheoryElaborations about Euler's Totient Function

mathbalarka

Well-known member
MHB Math Helper
Now, being an analytic and algebraic number theorist, I cannot help state another proof at this point.

Let $C_k$ be the cyclic group of order $k$. All number that is coprime to $k$ are then order of the generators of the cyclic group. As for any $n$, $C_n$ is the union of the cyclic groups $C_k$ for some $k$ that divides $n$ (to prove this, consider each element of $C_n$ as generators of some cyclic group). Using the fact that $\varphi(k)$ is the number of generators of $C_k$, it is now easy to arrive at Euler's formula

$$\sum_{k | n} \varphi(k) = n$$

Now calculations afterwards is the tricky part. We need something far more strong and powerful than just elementary number theory. What we actually need is Mobius inversion theorem. I think a proof would be off topic at this point, so I just jump in to the argument and results instead. The theorem states that if

$$g(n) = \sum_{d|n} f(d)$$

for $n \in \mathbb{N}$ then

$$f(n) = \sum_{d|n} \mu(d) g\left(\frac{n}{d}\right)$$

where $\mu$ is the Mobius function. Well, if we apply it to the Euler's formula,

$$\varphi(n) = n \sum_{d|n} \frac{\mu(d)}{d}$$

Now the left side looks familiar. This is essentially dual to the Mobius-dirchlet series for $\zeta$! Using this fact, one could actually derive an Euler-like product for $\zeta$, applied to $\varphi$ instead, which is essentially the same mentioned above

Last edited:

johng

Well-known member
MHB Math Helper
Re: Find the cardinality of a set

Here's a small correction to mathbalarka's post. A cyclic group Cn of order n is not the union of the cyclic subgroups Ck where k divides n, unless you include Cn itself.

However, let Sk be the set of elements of order k in Cn. Then Cn is the disjoint union of the various Sk where k divides n. Since Cn contains a unique cyclic subgroup Ck, Sk is contained in Ck. Thus the cardinality of Sk is $$\displaystyle \phi(k)$$. So the conclusion is certainly correct:

$$\displaystyle \sum_{k|n}\phi(k)=n$$

mathbalarka

Well-known member
MHB Math Helper
Re: Find the cardinality of a set

Yes, thank you johng. I guess I have to refrain from posting at 3:00 AM.

Deveno

Well-known member
MHB Math Scholar
Re: Find the cardinality of a set

Here's a small correction to mathbalarka's post. A cyclic group Cn of order n is not the union of the cyclic subgroups Ck where k divides n, unless you include Cn itself.

However, let Sk be the set of elements of order k in Cn. Then Cn is the disjoint union of the various Sk where k divides n. Since Cn contains a unique cyclic subgroup Ck, Sk is contained in Ck. Thus the cardinality of Sk is $$\displaystyle \phi(k)$$. So the conclusion is certainly correct:

$$\displaystyle \sum_{k|n}\phi(k)=n$$
Indeed, I prefer to think of the set $S_k$ as the possible generators of the unique subgroup $C_k$, which makes it clear this set has cardinality $\phi(k)$

(using the fact that if we have $a^t \in \langle a \rangle$, where $a$ has order $k$, then $a^t$ generates $\langle a \rangle$ if and only if $\text{gcd}(t,k) = 1$).

One useful feature of this formula, is that if we know $\phi(k)$ for all $k|n$ where $k < n$, it allows us to calculate $\phi(n)$ as:

$\displaystyle \phi(n) = n - \sum_{k|n,\ k < n} \phi(k)$.

For example, say we wanted to calculate $\phi(12)$. We have:

$\phi(12) = 12 - \phi(1) - \phi(2) - \phi(3) - \phi(4) - \phi(6)$.

Clearly, $\phi(1) = 1, \phi(2) = 1, \phi(3) = 2$, so this becomes:

$\phi(12) = 8 - \phi(4) - \phi(6)$.

If the latter 2 totients are not already known, we can derive them the same way:

$\phi(4) = 4 - \phi(1) - \phi(2) = 4 - 1 - 1 = 2$.
$\phi(6) = 6 - \phi(1) - \phi(2) - \phi(3) = 6 - 1 - 1 - 2 = 2$.

Thus, $\phi(12) = 8 - 2 - 2 = 4$.

This can be formalized into an algorithm that always finds $\phi(n)$ in a finite number of steps (although it is, admittedly, not the most EFFICIENT algorithm), in a manner similar to finding gcd's (the "smaller" totients we need to find are always at least "one prime factor" less than our previous totient, until we reach just totients of primes or of 1).

mathbalarka

Well-known member
MHB Math Helper
Deveno said:
although it is, admittedly, not the most EFFICIENT algorithm
Right. The one with optimal efficiency is almost definitely

$$\varphi(n) = n \prod_{p|n} \left ( 1 - \frac{1}{p}\right)$$

as calculating $\varphi(n)$ is computationally as hard as factoring $n$, conditionally on RH.

Bacterius

Well-known member
MHB Math Helper
Right. The one with optimal efficiency is almost definitely

$$\varphi(n) = n \prod_{p|n} \left ( 1 - \frac{1}{p}\right)$$

as calculating $\varphi(n)$ is computationally as hard as factoring $n$, conditionally on RH.
How do you get the "conditionally on RH" part? If you have the totient then you instantly have the factors of $n$, and vice versa, so calculating the totient is unconditionally as hard as factoring $n$, no?

mathbalarka

Well-known member
MHB Math Helper
bacterius said:
If you have the totient then you instantly have the factors of n
As $\omega(n)$ (or $\Omega(n)$) grows, you get high-degree polynomials with roots being factors of $n$. I cannot recall the complexity for the best algorithm for polynomial factoring just now, but it would surely show that how much "instantly" it is.

Nevertheless, this does not really show that there aren't better algorithms to calculate totient than factoring the argument. If you want a proof, see Miller, for example.

Bacterius

Well-known member
MHB Math Helper
As $\omega(n)$ (or $\Omega(n)$) grows, you get high-degree polynomials with roots being factors of $n$. I cannot recall the complexity for the best algorithm for polynomial factoring just now, but it would surely show that how much "instantly" it is.

Nevertheless, this does not really show that there aren't better algorithms to calculate totient than factoring the argument. If you want a proof, see Miller, for example.
Yes, indeed, my mistake - I was thinking of only two primes (as we usually do in cryptography). It would become harder with more factors, though note you are given the additional constraint that the roots multiply to a known value (which would probably help). By the way, $\omega(n)$ grows rather slowly, and as it grows, the cost of factoring $n$ goes down proportionately quite fast. For instance, the (naive) cost of factoring $n$ is $O(n^\frac{1}{\omega(n)})$ (or something similar). Modern algorithms can do considerably better than that. I cannot think of a totient-finding algorithm with similar characteristics that would not constructively reveal the prime factors of $n$ in the process, but of course that does not discount the existence of such an algorithm...

mathbalarka

Well-known member
MHB Math Helper
Bacterius said:
Yes, indeed, my mistake - I was thinking of only two primes
I suspected so.

$\omega(n)$ grows very slowly, yes. An actual heuristic of error about $\left ( \log \log n \right)^{1/2}$ with $\log \log n$ is derived from Hardy-Ramanujan theorem.

I don't really have account of complexity of prime factorization algorithms, but as far as I know the best is still exponential, so doesn't matter anyways.

Bacterius said:
but of course that does not discount the existence of such an algorithm...
Ah, but that is the whole point of my previous post! There is no algorithm that gives (considerably) better complexity the prime factoring algorithm.