Solution:

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 to 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 2p$.

We now claim that $a_{n} = 2p - 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 $2q \leq n + a_{n}$. To finish, we claim that $2q \geq n$, which would be implied by $2(a_{n} + 2) \geq n \Longleftrightarrow p \geq 3n/4 - 1$. This is indeed true for all $11 < n < 100$.

We therefore wish to maximize $n - a_{n} = n - (2p - 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.