Maths Olympiad Prep

Library / /13 of 15

Number theory Difficulty 6.2 National olympiad Prove it Romania

a) There exists a unique sequence of positive integers a1,a2,a3,a_1, a_2, a_3, \dots such that
n=dnad,for all nN. n = \sum_{d|n} a_d, \quad \text{for all } n \in \mathbb{N}^*.
b) There exists a unique sequence of positive integers b1,b2,b3,b_1, b_2, b_3, \dots such that
n=dnbd,for all nN. n = \prod_{d|n} b_d, \quad \text{for all } n \in \mathbb{N}^*.

Solution

a) Euler's totient φ\varphi provides the desired sequence, since dnφ(d)=n\sum_{d|n} \varphi(d) = n. Indeed, consider the fractions 1n,2n,,nn\frac{1}{n}, \frac{2}{n}, \dots, \frac{n}{n} expressed in lowest terms. For each divisor dd of nn, the fractions with denominator equal to dd are precisely those having the numerators coprime with dd – in all, there are φ(d)\varphi(d) such fractions. Since there are nn fractions, the formula holds true. A simple inductive argument ensures the uniqueness of the sequence an=φ(n)a_n = \varphi(n). Indeed, given a1=1a_1 = 1 and all terms aka_k up to k=n1k = n-1, one has an=ndn, d<nada_n = n - \sum_{d|n,\ d<n} a_d.

b) Set bn=1b_n = 1 if n=1n = 1 or if nn has at least two distinct prime divisors. For n=pkn = p^k, pp prime and k1k \ge 1, set bn=pb_n = p. To show that the sequence (bn)n1(b_n)_{n \ge 1} satisfies the relation, consider n=p1a1pkakn = p_1^{a_1} \cdots p_k^{a_k}, the set AA of all divisors of nn having exactly one prime factor, and the set BB of the remaining divisors. Then
dnbd=(dAbd)(dBbd)=p1a1pkak=n, \prod_{d|n} b_d = \left( \prod_{d \in A} b_d \right) \cdot \left( \prod_{d \in B} b_d \right) = p_1^{a_1} \cdots p_k^{a_k} = n,
as needed. The uniqueness of the sequence can be proved as above.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.