IMO 2019 Shortlisted Problems

We first show that $b$ is $a$-good if and only if $b$ is even, and $p\mid a$ for all primes $p⩽b$. To start with, the condition that $an+1\left|\right(\genfrac{}{}{0ex}{}{an}{b})-1$ can be rewritten as saying that $$\frac{an(an-1)\cdots (an-b+1)}{b!}\equiv 1(\mathrm{mod}an+1).$$ Suppose, on the one hand, there is a prime $p⩽b$ with $p\nmid a$. Take $t=v_p(b!)$. Then there exist positive integers $c$ such that $ac\equiv 1\left(\mathrm{mod}{p}^{t+1}\right)$. If we take $c$ big enough, and then take $n=(p-1)c$, then $an=a(p-1)c\equiv p-1\left(\mathrm{mod}{p}^{t+1}\right)$ and $an⩾b$. Since $p⩽b$, one of the terms of the numerator $an(an-1)\cdots (an-b+1)$ is $an-p+1$, which is divisible by $p^{t+1}$. Hence the $p$-adic valuation of the numerator is at least $t+1$, but that of the denominator is exactly $t$. This means that $p\left|(\genfrac{}{}{0ex}{}{an}{b}\right)$, so $p\nmid \left(\genfrac{}{}{0ex}{}{an}{b}\right)-1$. As $p\mid an+1$, we get that $an+1\nmid \left(\genfrac{}{}{0ex}{}{an}{b}\right)-1$, so $b$ is not $a$-good. On the other hand, if for all primes $p⩽b$ we have $p\mid a$, then every factor of $b!$ is coprime to $an+1$, and hence invertible modulo $an+1$ : hence $b!$ is also invertible modulo $an+1$. Then equation above reduces to: $$an(an-1)\cdots (an-b+1)\equiv b!(\mathrm{mod}an+1).$$ However, we can rewrite the left-hand side as follows: $$an(an-1)\cdots (an-b+1)\equiv (-1)(-2)\cdots (-b)\equiv (-1{)}^{b}b!(\mathrm{mod}an+1).$$ Provided that $an>1$, if $b$ is even we deduce $(-1{)}^{b}b!\equiv b!$ as needed. On the other hand, if $b$ is odd, and we take $an+1>2(b!)$, then we will not have $(-1{)}^{b}b!\equiv b!$, so $b$ is not $a$-good. This completes the claim. To conclude from here, suppose that $b$ is $a$-good, but $b+2$ is not. Then $b$ is even, and $p\mid a$ for all primes $p⩽b$, but there is a prime $q⩽b+2$ for which $q\nmid a$ : so $q=b+1$ or $q=b+2$. We cannot have $q=b+2$, as that is even too, so we have $q=b+1$ : in other words, $b+1$ is prime.

---

Alternative solution.

We show only half of the claim of the previous solution: we show that if $b$ is $a$-good, then $p\mid a$ for all primes $p⩽b$. We do this with Lucas' theorem. Suppose that we have $p⩽b$ with $p\nmid a$. Then consider the expansion of $b$ in base $p$; there will be some digit (not the final digit) which is nonzero, because $p⩽b$. Suppose it is the $p^t$ digit for $t⩾1$. Now, as $n$ varies over the integers, $an+1$ runs over all residue classes modulo $p^{t+1}$; in particular, there is a choice of $n$ (with $an>b$ ) such that the $p^0$ digit of $an$ is $p-1$ (so $p\mid an+1)$ and the $p^t$ digit of $an$ is 0. Consequently, $p\mid an+1$ but $p\mid \left(\genfrac{}{}{0ex}{}{an}{b}\right)$ (by Lucas' theorem) so $p\nmid \left(\genfrac{}{}{0ex}{}{an}{b}\right)-1$. Thus $b$ is not $a$-good. Now we show directly that if $b$ is $a$-good but $b+2$ fails to be so, then there must be a prime dividing $an+1$ for some $n$, which also divides $(b+1)(b+2)$. Indeed, the ratio between $\left(\genfrac{}{}{0ex}{}{an}{b+2}\right)$ and $\left(\genfrac{}{}{0ex}{}{an}{b}\right)$ is $(b+1)(b+2)/(an-b)(an-b-1)$. We know that there must be a choice of $an+1$ such that the former binomial coefficient is 1 modulo $an+1$ but the latter is not, which means that the given ratio must not be $1\mathrm{mod}an+1$. If $b+1$ and $b+2$ are both coprime to $an+1$ then the ratio is 1, so that must not be the case. In particular, as any prime less than $b$ divides $a$, it must be the case that either $b+1$ or $b+2$ is prime. However, we can observe that $b$ must be even by insisting that $an+1$ is prime (which is possible by Dirichlet's theorem) and hence $\left(\genfrac{}{}{0ex}{}{an}{b}\right)\equiv (-1{)}^b=1$. Thus $b+2$ cannot be prime, so $b+1$ must be prime.