Maths Olympiad Prep

Library / /214 of 520

Number theory Difficulty 6.0 AIME, harder Prove it

15. Let f(n)f(n) be a number-theoretic function with period kk, and denote e(θ)=e2πiθe(\theta)=\mathrm{e}^{2 \pi i \theta}. Prove:
f(n)=l=1kale(nlk),f(n)=\sum_{l=1}^{k} a_{l} e\left(-n \frac{l}{k}\right),

where al=1km=1kf(m)e(lmk)a_{l}=\frac{1}{k} \sum_{m=1}^{k} f(m) e\left(l \frac{m}{k}\right). In particular, when f(n)=χ(n;k)f(n)=\chi(n ; k), al=(1/k)G(l;χ)a_{l}=(1 / k) G(l ; \chi), where G(l;χ)G(l ; \chi) is given by equation (67).

Solution

15. Direct verification. This is the finite Fourier expansion of a periodic number-theoretic function.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.