linguistic:translation, structural:scholar_edition
Fourier transform

The totient is the discrete Fourier transform of the gcd, evaluated at 1. Let

where x = gcd(k, n) for k ∈ {1,..., n }. Then

The real part of this formula is

For example, using cos π 5 = 5 + 1 4 {\displaystyle \cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}} and cos 2 π 5 = 5 − 1 4 {\displaystyle \cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}}: φ (10) = gcd (1, 10) cos 2 π 10 + gcd (2, 10) cos 4 π 10 + gcd (3, 10) cos 6 π 10 + ⋯ + gcd (10, 10) cos 20 π 10 = 1 ⋅ (5 + 1 4) + 2 ⋅ (5 − 1 4) + 1 ⋅ (− 5 − 1 4) + 2 ⋅ (− 5 + 1 4) + 5 ⋅ (− 1) + 2 ⋅ (− 5 + 1 4) + 1 ⋅ (− 5 − 1 4) + 2 ⋅ (5 − 1 4) + 1 ⋅ (5 + 1 4) + 10 ⋅ (1) = 4. {\displaystyle {\begin{array}{rcl}\varphi (10)&=&\gcd(1,10)\cos {\tfrac {2\pi }{10}}+\gcd(2,10)\cos {\tfrac {4\pi }{10}}+\gcd(3,10)\cos {\tfrac {6\pi }{10}}+\cdots +\gcd(10,10)\cos {\tfrac {20\pi }{10}}\\&=&1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+5\cdot (-1)\\&&+\ 2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+10\cdot (1)\\&=&4.\end{array}}} Unlike the Euler product and the divisor sum formula, this one does not require knowing the factors of n. However, it does involve the calculation of the greatest common divisor of n and every positive integer less than n, which suffices to provide the factorization anyway.