Number Theory
Computing and Visualising Euler’s Totient
Computing Euler’s totient function φ(n) for the integers up to a chosen bound and visualising its distribution, in which the scattered values expose the arithmetic structure of the integers.
Definition
Euler’s totient function φ(n) counts the integers in the range 1 to n that are coprime to n, that is, those sharing no common factor with n other than 1. For a prime p, every smaller positive integer is coprime to it, so φ(p) = p − 1. For composite numbers the value is smaller and depends on the prime factorisation.
Computation
The value is computed directly from the prime-factorisation formula φ(n) = n·∏(1 − 1/p), taken over the distinct primes p dividing n. The implementation realises this by trial division:
def phi(n):
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
p += 1
if n > 1:
result -= result // n
return result
The function is evaluated for every integer up to a chosen bound N. Results are cached to a CSV file so that repeated runs are inexpensive, and φ is then plotted against n using Plotly.
Observations
When plotted, φ(n) does not form a smooth curve but a structured scatter of points. The prime numbers lie along the upper boundary at φ(n) = n − 1; integers with many small prime factors fall well below it; and the overall pattern exhibits a self-similar texture that reflects the distribution of divisibility among the integers.
Relevance to cryptography
The totient function is central to the RSA cryptosystem. For a modulus n = p·q, the value φ(n) = (p − 1)(q − 1) is precisely what permits the private exponent to be derived from the public exponent. Euler’s theorem, which states that aφ(n) ≡ 1 (mod n) for any a coprime to n, underlies the correctness of the scheme. An intuition for the behaviour of φ is therefore an intuition for the arithmetic foundation of public-key cryptography.