Welcome to Episode 8 of A Small Taste from My New Book.
In this episode, we venture into the heart of number theory by exploring
Euler’s totient function and its deep relationship with the roots of unity. The
totient function, which counts the positive integers up to 
that are coprime to , is not only a fundamental object in arithmetic but also
reveals surprising connections to the geometry of the complex plane through
primitive roots of unity.
But the story doesn’t end there. The totient function is
intimately linked to one of the most celebrated objects in mathematics: the
Riemann zeta function. Through elegant identities and Dirichlet series, we’ll
see how the sum of totients over all positive integers can be expressed in
terms of products involving the zeta function, bridging combinatorics,
analysis, and the deep structure of the integers. This connection underpins
powerful results in analytic number theory and highlights the unity between seemingly
disparate areas of mathematics.
Whether you’re a seasoned mathematician or a curious
explorer, this episode offers a clear and insightful look at how algebraic and
analytic ideas come together—revealing the hidden symmetries and profound links
that make the totient function a cornerstone of modern mathematics
▪▪▪
If 
the Euler totient
function is defined as the number of positive integers not exceeding which are relatively
prime to
The first ten values of 
are: 
, 
, 
, 
, 
, 
, 
, 
, 
, 
.
Euler’s totient function and the roots of unity share a
remarkable connection.
Adapting from The Riemann Hypothesis Revealed a
root of unity, occasionally called a de Moivre number, is any complex number
that yields 
when raised to some positive integer power . An th root of unity, where is a positive integer is a number satisfying
the equation 
. The th roots of unity are:
A primitive th root
of unity is an th root
of unity that is not a 
th root
of unity for any 
. In other words, it is the root of unity that generates all
other th roots
of unity when raised to successive powers.
Any integer power of an th root of unity is also an th root of unity, as 
. This is also true for negative exponents. In particular, the
reciprocal of an th root of unity is its complex conjugate and is also an th root of unity 
.
If 
is an th root of unity and 
that is, divides 
, then 
. Indeed, by the definition of congruence modulo , 
for some integer , and hence 
. Therefore, given a power 
of , one has 
where 
is the remainder of the
Euclidean division of 
by .
Let be a primitive th root of unity. A power 
of is a primitive th root of unity if
where 
is the greatest common
divisor of and . This results from the following:
If 
is to be a primitive th root of unity then 
. This means that 
. For to be a primitive th root of unity, 
must be a multiple of . Thus, 
for some integer 
. The smallest positive integer for which this is true is the largest number that divides both and , ensuring that 
is an integer.
Condition 
ensures that 
cycles through all th roots of unity without repeating until it completes one full
cycle, making it primitive.
In essence, the formula gives the exact order of the root of unity
formed by raising to the power , ensuring it is the smallest positive integer such that 
.
Moreover, is the smallest multiple
of that is also a multiple
of . In other words, is the least common
multiple of and . Thus,
And if and are coprime, substituting
into the formula for , we get 
. This implies is also a primitive th root of unity because it satisfies the condition for being a
primitive root (it cycles through all th roots of unity exactly once before repeating) and therefore
there are 
distinct primitive th roots of unity. This implies that if is a prime number, 
, all the roots except are primitive.
In other words, if 
is the set of all the th roots of unity and 
is the set of primitive
ones for a divisor 
of , these are th roots of unity that are not th roots of unity for any 
, then is a disjoint union of
the sets , for all divisors of , i.e., 
. Since the cardinality of is and that of is 
we have proven the following:
The sum of the Euler’s
totient function values over all divisors of 
gives:
Obviously, 
.
It is well known (see The Hidden
Oscillations Behind Prime Numbers: Mertens Function Revealed) that the Möbius function 
satisfies the following
identity for any positive integer :
From this, it follows that for any
positive integers and :
Substitution in the definition of yields
For a fixed divisor of we must sum over all
those in the range of 
which are multiples of . If we write, 
then implies 
. Hence the last sum for can be written as
Combining this with the identity 
we get
Note:
If is prime then 
.
Dirichlet Series Products, Convolution, and Euler’s Totient
Function
Given two Dirichlet series,
their product can be written as:
Because absolute convergence (see the
section Dirichlet Series in The Riemann HypothesisRevealed) allows us to freely multiply and rearrange the terms of the series
without affecting its sum, we group together all terms where the product 
equals a fixed value , considering every possible value of
. This approach leads us to the
following result:
Thus, we define the convolution of
two sequences 
and 
by
This operation, known as Dirichlet
convolution, combines the values of 
and 
over all divisors of . It plays a central role in analytic
number theory, especially when expressing products of Dirichlet series as
single series involving convolutions of their coefficients.
As a result, we write:
Let 
and 
.
The series 
converges for 
(
) and since
we have
Therefore,
Exercise: Expand in a
sum of powers of the sum of the series
Find the radius of convergence of the
series obtained.
Prove that for 
Solution: I’ll do it in
three steps. Expand, find the radius of convergence, then specialize to 
.
1. Expanding
as a power series.
Assume , Then for each fixed ,
So
Now sum over :
Does this double series converges
absolutely?
Write 
. Then
The convergence of this series cannot
be determined without assumptions on 
.
For example, if 
the series converges for every 
. Indeed, for we have 
so
Hence it can be compared to a
geometric series:
If next 
then again
converges for all 
.
If 
for some 
then 
for all 
. Also, for
Combining these for , it follows that
So, we compare 
to the
series
This series converges for any and any (it’s a polynomial factor times a geometric
decay), e.g. by the ratio test:
So: polynomial growth is more than
tame enough; the exponential damping 
wins.
The curious reader may investigate
other cases.
Assuming one of the above holds we
can rearrange and group by powers of . A term appears whenever 
, i.e. whenever divides . Thus, the coefficient of is
So we obtain the power series
expansion
2. Radius of convergence of the
resulting series
The resulting series has the form
From the construction, for we already know it converges (under mild
assumptions that make the original series meaningful). The natural boundary
from the geometric expansions 
is 
, so the radius of convergence is at
least , and typically equal to unless the are special.
In particular, in the concrete case bellow, we will see directly that the
resulting series is
whose radius of convergence is
exactly .
So, for the second part, the radius of
convergence of the series you get .
3. Specializing to 
and proving the identity
Now take , Euler’s totient function. Then the
coefficient of in the expanded series is
However, the identity
for gives
This is times the derivative of the geometric series
for concluding that the radius of convergence is .
Computation
You can compute all values of Euler’s
totient function efficiently using a modified sieve (very similar to the sieve
of Eratosthenes).
Use a vector to store the calculated values:
- Start with phi[i] = i for all i.
- For every prime p, update multiples of p using
which in integer arithmetic is:
The sieve naturally finds primes
along the way: when phi[p] == p, p is prime.
C++ implementation (totients from 1
to n)
#include
<bits/stdc++.h>
using
namespace std;
// Compute phi[1..n] using a sieve in O(n log log
n)
vector<int>
totients(int n) {
vector<int> phi(n + 1);
// initialize
for (int i = 0; i <= n; ++i) {
phi[i] = i;
}
for (int p = 2; p <= n; ++p) {
if (phi[p] == p) {
// p is prime
for (int k = p; k <= n; k += p)
{
phi[k] -= phi[k] / p; // phi[k] *= (1 - 1/p)
}
}
}
return phi;
}
int main() {
int n = 2000;
vector<int> phi = totients(n);
cout << "Euler's totient values
phi(1..n):\n";
for (int i = 1; i <= n; ++i) {
cout << "phi(" <<
i << ") = " << phi[i] << '\n';
}
return 0;
}
Epilogue
In this episode, we explored how
Euler’s totient function connects arithmetic, algebra, and analysis. By
examining its relationship with primitive roots of unity, we uncovered classic
identities and saw how the totient function links directly to the Riemann zeta
function through Dirichlet series and convolution formulas.
These results illustrate how
number-theoretic functions can reveal deeper patterns in mathematics, bridging
discrete and continuous perspectives. The interplay between combinatorics,
complex analysis, and special functions like the zeta function highlights the
versatility and relevance of these classical ideas in modern mathematical
research.
If you enjoyed this exploration, you
may wish to delve further into the detailed discussions and examples found in
the referenced books, where these connections are developed with full
transparency and step-by-step clarity
Comments
Post a Comment