16. Let $p$ be the least prime number that does not divide $n$ : thus $a_{1}=1$ and $a_{2}=p$. Since $a_{2}-a_{1}=a_{3}-a_{2}=\cdots=r$, the $a_{i}$ 's are $1, p, 2 p-1,3 p-2, \ldots$ We have the following cases: $p=2$. Then $r=1$ and the numbers $1,2,3, \ldots, n-1$ are relatively prime to $n$, hence $n$ is a prime. $p=3$. Then $r=2$, so every odd number less than $n$ is relatively prime to $n$, from which we deduce that $n$ has no odd divisors. Therefore $n=2^{k}$ for some $k \in \mathbb{N}$. $p>3$. Then $r=p-1$ and $a_{k+1}=a_{1}+k(p-1)=1+k(p-1)$. Since $n-1$ also must belong to the progression, we have $p-1 \mid n-2$. Let $q$ be any prime divisor of $p-1$. Then also $q \mid n-2$. On the other hand, since $q<p$, it must divide $n$ too, therefore $q \mid 2$, i.e. $q=2$. This means that $p-1$ has no prime divisors other than 2 and thus $p=2^{l}+1$ for some $l \geq 2$. But in order for $p$ to be prime, $l$ must be even (because $3 \mid 2^{l}+1$ for $l$ odd). Now we recall that $2 p-1$ is also relatively prime to $n$; but $2 p-1=2^{l+1}+1$ is divisible by 3 , which is a contradiction because $3 \mid n$.