IMO 2019 Problem N5 Solution 2 IMO 2019 Problem N5 Solution 2.
https://www.imo-official.org/problems/IMO2019SL.pdf

Let $a$ be a positive integer. We say that a positive integer $b$ is $a$-good if $\binom{an}{b}-1$ is divisible by $an+1$ for all positive integers $n$ with $an\geqslant b$. Suppose $b$ is a positive integer such that $b$ is $a$-good, but $b+2$ is not $a$-good. Prove that $b+1$ is prime.Solution 2. $\quad$ 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\leqslant b$. We do this with Lucas' theorem.$\quad$ Suppose that we have $p\leqslant b$ with $p\not\mid a$. Then consider the expansion of $b$ in base $p$; there will be some digit (not the final digit) which is nonzero, because $p\leqslant b$. Suppose it is the $p^t$ digit for $t\geqslant 1$.$\quad$ 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\gt 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 \binom{an}{b}$ (by Lucas’ theorem) so $p\not\mid\binom{an}{b}-1$. Thus $b$ is not $a$-good.$\quad$ 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 $\binom{an}{b+2}$ and $\binom{an}{b}$ 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\ \text{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.$\quad$ 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 $\binom{an}{b}\equiv (-1)^b=1$. Thus $b+2$ cannot be prime, so $b+1$ must be prime.

I struggle with "$an+1$ is prime (which is possible by Dirichlet’s theorem)". For Dirichlet's theorem to be applicable here, there has to be an arithmetic progression of numbers $an+1$ for which $\binom{an}{b}\equiv1$ and $\binom{an}{b+2}\not\equiv1$ modulo $an+1$. Because $b$ is $a$-good and $b+2$ is not, we are guaranteed that at least one such $n$ exists. But I don't see how a single $n$ leads to a whole arithmetic progression of such numbers.
Any ideas? Thanks.
 A: 
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 | an+1$) and the $p^t$ digit of $an$ is $0$.

The possible values of $n$ here are in an arithmetic progression. Indeed every $n$ denotes a class here.

*

*class 0: $1 \pmod{p^{t+1}}$

*class 1: $a+1 \pmod{p^{t+1}}$

*class 2: $2a+1 \pmod{p^{t+1}}$

*class 3: $3a+1 \pmod{p^{t+1}}$

*...

*class S: $(????0????????(p-1))\pmod{p^{t+1}}$ where the $p^t$ digit of $an$ is 0

*...

The class S above satisfies the hypothesis of Dirichlet's theorem: it is an arithmetic progression with step $p^t$ and first term coprime with $p^t$.
Then we can choose $aS+1$ as our class. Every term of it - including the (infinitely many) prime terms of it - satisfies the construction.
A: I think that if $n$ satisfies $an\ge b+2,\binom{an}{b}\equiv 1\pmod{an+1}$ and $\binom{an}{b+2}\not\equiv 1\pmod{an+1}$, then $an+1$ is a composite number.
To prove this, it is sufficient to prove that if $n$ is such that $an+1$ is prime satisfying $an\ge b+2$ and $\binom{an}{b}\equiv 1\pmod{an+1}$, then $\binom{an}{b+2}\equiv 1\pmod{an+1}$.
We can have
$$(an+1)\mid (b+1)(b+2)\bigg(\binom{an}{b+2}-1\bigg)\tag1$$
since we have
$$\begin{align}&(b+1)(b+2)\bigg(\binom{an}{b+2}-1\bigg)
\\\\&=(b+1)(b+2)\cdot\frac{an(an-1)\cdots (an-b+1)(an-b)(an-b-1)}{(b+2)(b+1)b!}-(b+1)(b+2)
\\\\&=(an-b)(an-b-1)\cdot\frac{an(an-1)\cdots (an-b+1)}{b!}-(b+1)(b+2)
\\\\&=(an-b)(an-b-1)\binom{an}{b}-(b+1)(b+2)
\\\\&\equiv (-1-b)(-b-2)\times 1-(b+1)(b+2)\pmod{an+1}
\\\\&\equiv (b+1)(b+2)-(b+1)(b+2)\pmod{an+1}
\\\\&\equiv 0\pmod{an+1}\end{align}$$
It follows from $an+1\ge b+3$ that $(an+1)\not\mid (b+1)(b+2)$.
So, from $(1)$, we get $(an+1)\mid (\binom{an}{b+2}-1)$, i.e.
$$\binom{an}{b+2}\equiv 1\pmod{an+1}.\quad\blacksquare$$
