Elaborations about Euler's Totient Function

[mathbalarka]

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 into 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

 

[johng1]

Re: Find the cardinality of a set

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

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

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

 

[mathbalarka]

Re: Find the cardinality of a set

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

 

[Deveno]

Re: Find the cardinality of a set

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

However, let S_k be the set of elements of order k in C_n. Then C_n is the disjoint union of the various S_k where k divides n. Since C_n contains a unique cyclic subgroup C_k, S_k is contained in C_k. Thus the cardinality of S_k 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]

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.

 

[Nono713]

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]

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.

 

[Nono713]

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]

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.

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.