NMO Selection Tests for the Junior Balkan Mathematical Olympiad

a) Euler's totient $\phi$ provides the desired sequence, since ${\sum }_{d|n}\phi (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 $\phi (d)$ such fractions. Since there are $n$ fractions, the formula holds true. A simple inductive argument ensures the uniqueness of the sequence $a_n=\phi (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.