Editing Euler's totient function (section)

===Fourier transform===

The totient is the [[discrete Fourier transform]] of the [[Greatest common divisor|gcd]], evaluated at 1.<ref>{{harvtxt|Schramm|2008}}</ref> Let

:<math> \mathcal{F} \{ \mathbf{x} \}[m] = \sum\limits_{k=1}^n x_k \cdot e^{{-2\pi i}\frac{mk}{n}}</math>

where {{math|''x<sub>k</sub>'' {{=}} gcd(''k'',''n'')}} for {{math|''k'' ∈ {1, ..., ''n''}<nowiki/>}}. Then

:<math>\varphi (n) = \mathcal{F} \{ \mathbf{x} \}[1] = \sum\limits_{k=1}^n \gcd(k,n) e^{-2\pi i\frac{k}{n}}.</math>

The real part of this formula is

:<math>\varphi (n)=\sum\limits_{k=1}^n \gcd(k,n) \cos {\tfrac{2\pi k}{n}}
.</math>

For example, using <math>\cos\tfrac{\pi}5 = \tfrac{\sqrt 5+1}4
</math> and <math>\cos\tfrac{2\pi}5 = \tfrac{\sqrt 5-1}4
</math>:<math display="block">\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{\sqrt5+1}4)  + 2\cdot(\tfrac{\sqrt5-1}4) + 
1\cdot(-\tfrac{\sqrt5-1}4) + 2\cdot(-\tfrac{\sqrt5+1}4) + 5\cdot (-1) \\
&& +\  2\cdot(-\tfrac{\sqrt5+1}4) + 1\cdot(-\tfrac{\sqrt5-1}4) + 2\cdot(\tfrac{\sqrt5-1}4) +
1\cdot(\tfrac{\sqrt5+1}4) + 10 \cdot (1) \\
&=& 4 .
\end{array}
</math>Unlike the Euler product and the divisor sum formula, this one does not require knowing the factors of {{mvar|n}}. However, it does involve the calculation of the greatest common divisor of {{mvar|n}} and every positive integer less than {{mvar|n}}, which suffices to provide the factorization anyway.