Problem 616

Solution. Note that 12346 is even, 3 and 5 divide 12345, and 7 divides 12348. Consider a 5 digit number $n=a b c d e$ with $0a>0$ and $S=e-(d-c)-(b-a)<e \leq 10$, so $S$ is not divisible by 11 and hence $n$ is not divisible by 11. Thus 11 is the smallest prime that does not divide any five-digit number whose digits are in a strictly increasing order.