NMO Selection Tests for the Junior Balkan Mathematical Olympiad

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

b) Set $b_n = 1$ if $n = 1$ or if $n$ has at least two distinct prime divisors. For $n = p^k$, $p$ prime and $k \ge 1$, set $b_n = p$. To show that the sequence $(b_n)_{n \ge 1}$ satisfies the relation, consider $n = p_1^{a_1} \cdots p_k^{a_k}$, the set $A$ of all divisors of $n$ having exactly one prime factor, and the set $B$ of the remaining divisors. Then
$$\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.