The largest such integer is $a b-a-b$. To see it’s not a nonnegative integer linear combination, suppose $a b-a-b=a x+b y$ with $x, y \in \mathbb{Z}_{\geq 0}$. Then $a(b-1-x)=b(y+1)$. And since $(a, b)=1$ we have $a \mid y+1$ (and $b \mid b-1-x$ ). This forces $y \geq a-1$ because $y+1 \geq 1$. So
$$
a x+b y \geq a \cdot 0+b(a-1)=a b-b>a b-a-b
$$
contradicting $a b-a-b=a x+b y$.
On the other hand, suppose $n>a b-a-b$. Since $\operatorname{gcd}(a, b)=1$ we can write $n=a x+b y$ with $x, y \in \mathbb{Z}$ (not necessarily nonnegative). Now note that $n=a(x-b k)+b(y+a k)$ for any integer $k$. By the division algorithm, there exists an integer $k$ such that $0 \leq x-b k<b$. Let $x^{\prime}=x-b k$ and $y^{\prime}=y+a k$. Then we have $n=a x^{\prime}+b y^{\prime}$ with $0 \leq x^{\prime} \leq b-1$, so
$$
b y^{\prime}=n-a x^{\prime} \geq(a b-a-b+1)-a(b-1)=-(b-1)
$$
Therefore $y^{\prime} \geq \frac{-(b-1)}{b}$, and since $y^{\prime}$ is an integer, we get $y^{\prime} \geq 0$. This shows that $n=a x^{\prime}+b y^{\prime}$ is a nonnegative integer linear combination.

Suppose $n$ is prime. Then, since the binomial coefficients in the middle vanish mod $p$,
$$
\begin{aligned}
(x-a)^n & \equiv x^n+(-a)^n \
& \equiv x^n+(-a) \quad(\bmod n) .
\end{aligned}
$$
Now for the converse. The polynomial congruence in particular means that $n$ must divide $\left(\begin{array}{l}n \ i\end{array}\right)$ for $i=1, \ldots, n-1$. We’ll see first that this implies $n$ must be a power of a prime.

Let $p$ be any prime dividing $n$. If $n$ is not a power of $p$, then the base $p$ expansion of $n$ does not look like 1 followed by a bunch of zeroes, so it’s either $n_r 0 \cdots 0$ with $n \geq 2$, or $n_r n_{r-1} \cdots n_i \cdots n_0$ with some $n_i \geq 1$ for $i<r$. In any case, let $k$ have the base $p$ expansion $10 \cdots 0$ (i.e., $k=p^r$ ). Then subtracting $k$ from $n$ in base $p$ doesn’t involve any carries, so $p \nmid\left(\begin{array}{l}n \ k\end{array}\right)$ and therefore $n \nmid\left(\begin{array}{l}n \ k\end{array}\right)$, contradiction. So $n$ must be a power of $p$.

Let’s assume $n$ is not a prime, so we now have $n=p^r$ with $r \geq 2$. Then it’s clear that subtracting $p^{r-1}$ (whose base $p$ expansion is $010 \cdots 0$ ) from $n$ in base $p$ will involve only one carry. So $p |\left(\begin{array}{c}r \ p^{r-1}\end{array}\right)$, and thus $n=p^r$ cannot divide this binomial coefficient, contradiction. Therefore, $n$ is indeed a prime.

We have.
$$
p^e \mid\left(x^2-1\right)=(x-1)(x+1)
$$
Suppose $p$ is odd. Then $p$ can’t divide both $x+1$ and $x-1$, since their difference 2 isn’t divisible by $p$, so $\left(p^e, x+1\right)=1$ or $\left(p^e, x-1\right)=1$. Hence $p^e \mid x-1$ or $p^e \mid x+1$, and the only two solutions are $x \equiv \pm 1$ $\left(\bmod p^3\right)$
Now suppose $p=2$. Then $x^2 \equiv 1\left(\bmod 2^c\right)$ means $x$ must be odd, so let $x=2 y+1$. We have
$$
2^e \mid(x-1)(x+1)=4 y(y+1)
$$
Note that if $p=2$ then $x=1$, and if $p=4$ then $x=1,3$. So let’s assume $e \geq 3$. Since $y$ and $y+1$ are obviously coprime, we have $2^{e-2} \mid y$ or $2^{e-2} \mid y+1$, i.e., $y \equiv 0\left(\bmod 2^{\varepsilon-2}\right)$ or $y \equiv-1\left(\bmod 2^{c-2}\right)$. Then, modulo $2^{c-1}$, the possible solutions for $y$ are $0,2^{c-2}, 2^{e-2}-1,-1$, and the corresponding solutions for $x$ are $1,-1,2^{e-1}+1,2^{e-1}-1$. It’s easy to verify that all of these work and are distinct modulo $2^e$.