Note that 1 is relatively prime to all positive integers. Therefore, the definition of $a_{n}$ can equivalently be stated as: "$a_{n}$ is the smallest nonnegative integer such that for all integers $x, 2 \leq x \leq n$, $x$ shares a prime factor with at least one of $n, n+1, \ldots n+a_{n}$." The condition is equivalent the statement that the integers from $n$ to $n+a_{n}$ must include multiples of all primes less than $n$. Therefore, if $p$ is the largest prime satisfying $p<n$, then $n+a_{n} \geq 2 p$. We now claim that $a_{n}=2 p-n$ works for all $n>11$. For all primes $q$ at most $a_{n}+1$, it is apparent that $n, n+1, \ldots, n+a_{n}$ indeed contains a multiple of $q$. For primes $a_{n}+1<q \leq p$, we then find that $2 q \leq n+a_{n}$. To finish, we claim that $2 q \geq n$, which would be implied by $2\left(a_{n}+2\right) \geq n \Longleftrightarrow p \geq 3 n / 4-1$. This is indeed true for all $11<n<100$. We therefore wish to maximize $n-a_{n}=n-(2 p-n)=2(n-p)$. Therefore, the answer is twice the largest difference between two primes less than 100. This difference is 8 (from 89 to 97), so the answer is 16. Since this is greater than 11, we have not lost anything by ignoring the smaller cases.