ISL 1982 Problem 38

Numbers $u_{n,k} \ (1\leq k \leq n)$ are defined as follows $$u_{1,1}=1, u_{n,k}=\binom{n}{k} - \sum_{d \mid n, d \mid k, d>1} u_{n/d, k/d}.$$ (the empty sum is defined to be equal to zero). Prove that $n \mid u_{n,k}$ for every natural number $n$ and for every $k \ (1 \leq k \leq n).$