The point of the problem is the following classification. Claim: A pair $(a,b)$ is weird if and only if $b$ even and for all primes $p\le b$, we have $p\mid a$. Proof: First, suppose $(a,b)$ is weird. Suppose for the sake of contradiction that we had some prime $p\le b$ such that $p\nmid a$. Pick $X>0$ such that \begin{align*} X &\equiv 0\pmod{a} \\ X &\equiv p-1\pmod{p^{v_p(b!)+100}}. \end{align*}Then, \[v_p\left(\binom{X}{b}\right)\ge v_p(X-p+1)-v_p(b!)=100,\]so $p\mid\binom{X}{b}$. We have $p\mid X+1$, and since $(a,b)$ is weird, we have \[p\mid X+1\mid \binom{X}{b}-1,\]which is a clear contradiction. Thus, for all primes $p\le b$, we have $p\mid a$. Now, for $a\mid X$, we have $\binom{X}{b}\equiv 1\pmod{X+1}$. By the thing we just proved, we actually have $\gcd(X+1,b!)=1$, so in fact \[\binom{X}{b}\equiv(-1)^b\pmod{X+1},\]so we must have $b$ even, as desired. Now we show that if $(a,b)$ satisfies the conditions stated, the pair is weird. Indeed, we have $\gcd(an+1,b!)=1$, so \[\binom{an}{b}\equiv (-1)^b\equiv 1\pmod{an+1},\]as desired. $\blacksquare$ The problem is now immediate, since if we assume $b+1$ composite and $(a,b)$ weird, then both $b+1$ and $b+2$ are not prime, and $b+2$ is even, so we're done.

We will first prove the following lemmas. Lemma 1: If $b$ is $a$-good, then $b$ is even. Proof: Let $p > 2$ be a prime number greater than both $a$ and $b$. Then $(a, p) = 1$ which means there are infinitely many positive integers $m$ such that $am + 1 \equiv 0 \pmod p$. Choose one of such $m$ so that $am \geq b$. Since $$p\mid am + 1 \mid \binom{am}{b} - 1$$we get \begin{align*} 1 \equiv \binom{am}{b} &= \frac{(am)(am-1)(am-2)\cdots(am - b + 1)}{b(b-1)(b-2)\cdots 1}\equiv \frac{(-1)(-2)(-3)\cdots(- b)}{b(b-1)(b-2)\cdots 1} \equiv (-1)^b \pmod{p} \end{align*}Since $p > 2$ this is possible only if $b$ is even. The next to lemmas are similar and follow the same proof method. Lemma 2: If $b$ is $a$-good number such that $b+1$ is not prime, then every prime divisor of $b+1$ is also a divisor of $a$. Proof: For a contradiction suppose there is a prime number $p$ that divides $b+1$ but not $a$. Since $b+1$ is not prime we have $b + 1 \neq p$. If $\alpha = v_p(b+1 - p)$, then we can write $$b + 1 = p + rp^{\alpha} \pmod{p^{\alpha + 1}}$$where $\alpha \geq 1$ and $1 \leq r \leq p-1$. Since $(a, p) = 1$, numbers $\{an\}_{n=1}^{\infty}$ give all residues modulo $p^{\alpha + 1}$ and each of them infinitely many times. In particular, we can choose $m$ such that $am \geq b$ and $$am \equiv p - 1 \pmod{p^{\alpha + 1}}$$Then $$\left\lfloor \frac{am}{p^{\alpha + 1}} \right\rfloor = \frac{am + 1 - p}{p^{\alpha + 1}} \qquad \text{and} \qquad\left\lfloor \frac{b}{p^{\alpha + 1}} \right\rfloor = \frac{b+1 - p-rp^{\alpha}}{p^{\alpha + 1}}.$$Moreover, \begin{align*} \left\lfloor \frac{am - b}{p^{\alpha + 1}} \right\rfloor &= \left\lfloor \frac{(am + 1 - p) - (b + 1 - p - rp^{\alpha}) - rp^{\alpha}}{p^{\alpha + 1}} \right\rfloor = \frac{(am + 1 - p) - (b + 1 - p - rp^{\alpha})}{p^{\alpha + 1}} - 1 \end{align*}So $$\left\lfloor \frac{am}{p^{\alpha + 1}} \right\rfloor = \left\lfloor \frac{b}{p^{\alpha + 1}} \right\rfloor + \left\lfloor \frac{am - b}{p^{\alpha + 1}} \right\rfloor + 1$$Since we also have $$\left\lfloor \frac{am}{p^{k}} \right\rfloor \geq \left\lfloor \frac{b}{p^{k}} \right\rfloor + \left\lfloor \frac{am - b}{p^{k}} \right\rfloor$$for all $k \geq 0$, we get $$v_p((am)!) \geq v_p(b!) + v_p((am-b)!) + 1$$Therefore $$\binom{am}{p} \equiv 0 \pmod{p}$$Since $$p\mid am+1 \mid \binom{am}{p} - 1$$we get $p\mid 1$ which is a contradiction. Lemma 3: If $b$ is $a$-good number, then every prime divisor of $b+2$ is also a divisor of $a$. Proof: For a contradiction suppose there is a prime number $p$ that divides $b+2$ but not $a$. From Lemma 1 we know that $b+2$ is not prime which means $b + 2 \neq p$. If $\alpha = v_p(b+2 - p)$, then we can write $$b + 2 = p + rp^{\alpha} \pmod{p^{\alpha + 1}}$$where $\alpha \geq 1$ and $1 \leq r \leq p-1$. Since $(a, p) = 1$, there is a positive integer $m$ such that $am \geq b$ and $$am \equiv p - 1 \pmod{p^{\alpha + 1}}$$Then $$\left\lfloor \frac{am}{p^{\alpha + 1}} \right\rfloor = \frac{am + 1 - p}{p^{\alpha + 1}} \qquad \text{and} \qquad\left\lfloor \frac{b}{p^{\alpha + 1}} \right\rfloor = \frac{b+2 - p-rp^{\alpha}}{p^{\alpha + 1}}.$$Moreover, \begin{align*} \left\lfloor \frac{am - b}{p^{\alpha + 1}} \right\rfloor &= \left\lfloor \frac{(am + 1 - p) - (b + 2 - p - rp^{\alpha}) + 1 - rp^{\alpha}}{p^{\alpha + 1}} \right\rfloor= \frac{(am + 1 - p) - (b + 1 - p - rp^{\alpha})}{p^{\alpha + 1}} - 1 \end{align*}So $$\left\lfloor \frac{am}{p^{\alpha + 1}} \right\rfloor = \left\lfloor \frac{b}{p^{\alpha + 1}} \right\rfloor + \left\lfloor \frac{am - b}{p^{\alpha + 1}} \right\rfloor + 1$$Since we also have $$\left\lfloor \frac{am}{p^{k}} \right\rfloor \geq \left\lfloor \frac{b}{p^{k}} \right\rfloor + \left\lfloor \frac{am - b}{p^{k}} \right\rfloor$$for all $k \geq 0$, we get $$v_p((am)!) \geq v_p(b!) + v_p((am-b)!) + 1$$Therefore $$\binom{am}{p} \equiv 0 \pmod{p}$$Since $$p\mid am+1 \mid \binom{am}{p} - 1$$we get $p\mid 1$ which is a contradiction. From Lemma 1 and Lemma 2 we see that if $b$ is $a$-good and $b+1$ is not prime, then $$(an + 1, b + 1) = (an+1, b+2) = 1$$for all integers $n$. Observe that $$(an - b)(an - b - 1) \equiv (-1 - b)(-b-2) = (b+1)(b+2) \pmod{an + 1}$$Since $(an+1, (b+1)(b+2)) = 1$, we get $$\frac{(an - b)(an - b - 1)}{(b+1)(b+2)} \equiv 1 \pmod{an+1}$$Since $b$ is $a$-good we also have $$\binom{an}{b} \equiv 1 \pmod{an+1}$$Then $$\binom{an}{b+2} = \binom{an}{b}\cdot\frac{(an - b)(an - b - 1)}{(b+1)(b+2)} \equiv 1 \pmod{an+1}$$This means $b+2$ is also $a$-good which is a contradiction.

Comment: Wonderful medium-hard divisibility problem. I wished this was on the IMO . First, we look at polynomial division and observe the following. Claim: The polynomial $$F_b(x) = b!\frac{\binom{x}{b}-(-1)^b}{x+1}$$is in $\mathbb{Z}[x]$. Proof: First, check that $\tbinom{-1}{b} = (-1)^b$ so it's actually polynomial. The numerator is clearly in $\mathbb{Z}[x]$ hence the claim is true. $\blacksquare$ The claim eliminates the case $b$ is odd. Indeed, we have $x\mid b!\left(\tbinom{x}{b}+1\right)$ which fails for all large $x$. Therefore any odd $b$ is never $a$-good for any $a$. Now we turn our attention to even $b$. The key claim is Claim: $b$ is $a$-good if and only if $\prod\limits_{p<b} p$ divides $a$ (where the product runs through all primes less than $b$.) Proof: The "if" part is obvious; we have $$b!\frac{\binom{an}{b}-(-1)^b}{an+1} = F_b(an)\in\mathbb{Z}$$and we have $\gcd(an+1,b!)=1$ from the condition. Now we prove the only if part. Suppose that $p\nmid a$ for some $p<b$. By CRT, pick $x>b$ such that \begin{align*} x &\equiv 0\pmod a \\ x &\equiv p-1 \pmod{p^{\nu_p(b!)}}. \end{align*}If $b$ is $a$-good, then $$\mathbb{Z}\ni\frac{\binom{x}{b}-1}{x+1} = \frac{F_b(x)}{b!}.$$However, compute \begin{align*} F_b(x) \equiv F_b(p-1) = b!\frac{\binom{p-1}{b}-1}{p} = -\frac{b!}{p}\pmod{p^{\nu_p(b!)}} \end{align*}hence $\nu_p(F_b(x)) < \nu_p(b!)$, contradiction. $\blacksquare$ The claim obviously imply the problem.

We present two lemmas that kill off the problem: Claim: $b$ is $a$-good iff $p<b \implies p\vert a$ Proof : Assume to the contrary that there exists some $p<b$ that doesnt divide $a$. Hence there exists large $n$ such that $p\vert an+1$. Consider the base $p$ representation of $b$. It must have a non-zero digit other than the last digit (well because $p<b$). Suppose the digit corresponding to $p^k$ is non-zero. We will construct $n$ such that the base $p$ representation of $an$ has a zero corresponding to the $p^k$ index and $p\mid an+1$. This is easy, note that $an+1$ sweeps all residues modulo $p^{k+1}$, so the fact that such a choice exists is obvious. Hence by Lucas' theorem we conclude that $p \vert \tbinom {an}b$ and hence $p \nmid \tbinom {an}b-1$ We now prove the "only if" direction. This is easy. Note that we have $\gcd(an+1,b!)=1$, so\[\binom{an}{b}\equiv (-1)^b\equiv 1\pmod{an+1},\]as desired. Hence the claim stands proven. $\blacksquare$ Claim: If $b$ is $a$-good for some $a$, then $b$ must be even. Proof : Pick a huge prime $p >> a,b$. Note that there exists sufficiently large $n$ such that $p\mid an+1$. Henec $p \mid \tbinom {an}b$. We have : $$ 1 = \frac {(an)(an-1)\dots (an-b+1)}{b(b-1)\dots 1} = \frac { (-1)\cdot (-2) \cdots (-b)}{b(b-1)\dots 1} = (-1)^b \pmod p$$ This directly gives $b$ is even. Hence since $(b+2)$ is not $a$-good hence there exists a prime $<b+2$ and $>b$ which is a non divisor of $a$. The only possible choice is $b+1$ and we conclude. $\blacksquare$

Also Bulgaria EGMO TST 2020 Problem 6

Not too sure if it's me, but I felt this easy since the key lemma was natural for me (haven't tried N2-4 yet, but my guts say this is prolly easier than all three problems, at least for me). With this said, I'll explain the motivation behind establishing $\forall p\le b, p\mid a$. Suppose, now, $p\nmid a$ for some prime $p\le b$. Then for any $m, k\ge 0$ we can always choose $n$ such that $an+1\equiv m\pmod{p^k}$, and $an+1>b$. In addition, we need the condition $\gcd(\tbinom{an}{b}, an+1)=1$ for all $n$, so if $p$ is a prime such that $p\mid an+1$ then $p\nmid \tbinom{an}{b}$. The next thing is to determine $\tbinom{an}{b}\pmod{p}$ assuming $p\mid an+1$. We'll use Lucas' theorem on $\tbinom{an}{b}$. If $p\le b$, then $b$ has at least two digits in base $p$. Let the $i>0$-th digit position to be nonzero. Since $\gcd(a, p)=1$, we can choose $n$ such that $an$ has $i$-th position = 0 and $0$-th position = $p-1$, so $p\mid an+1$ but given the $i$-th position of $an$ is less than that of $b$, we have $p\mid \tbinom{an}{b}$. This gives a contradiction. Now that we have established $p\mid a$ for all primes $p\le b$ (which tbh is the key to the solution), any prime dividing $an+1$ are greater than $b$ so $\gcd(b!, an+1)=1$ for all $n$. Therefore, we have the following congruence: $$ \tbinom{an}{b}=\frac{an(an-1)\cdots (an-b+1)}{b!}\equiv\frac{(-1)(-2)\cdots (-b)}{b!}=(-1)^b\pmod{an+1} $$so in this case, $b$ is $a$-good iff $b$ is even. Now it's easy to complete the solution. Since $b$ is $a$-good but $b+2$ is not, $b$ and $b+2$ are both even, and $p\le a$ for all $p\le b$ but there exists a prime $q\le b+2$ with $q\nmid a$. This $q$ must be greater than $b$ but at most $b+2$, and since $b+2$ is even (hence cannot be prime), $q=b+1$. Thus $b+1$ is prime.

$\textrm{Really Cool Problem}$ Crucial Claim :- $b$ is $a-$good $\iff$ $\begin{cases} b \text{ is even} \\ \forall \: p \text{ (prime)} \leq b : \; p \mid a \end{cases}$ Proof : $\implies$ Suppose not, let $p \leq b$ s.t $p \nmid a$ . Suppose $v_p(b!)=s-1$. Put $n = (p-1)a^{\star} \; \text{ (mod } p^s )$ which $a^{\star}a = 1 \: ( \text{ mod }p^s )$ So $v_p \left({an \choose b}\right) =v_p \left(\frac{(an)(an-1)\dots (an-b+1)}{b(b-1)\dots (1)}\right) \geq v_p\left(an-(p-1)\right) -v_p\left(b!\right) \geq 1$ But $p \mid an+1 \mid {an \choose b} -1 $ $\implies $ Contradiction . Now get $n$ s.t $an+1$ is divisible by $q$ prime greater than $b$, then ${an \choose b} -1 = (-1)^b -1 \implies (-1)^b =1$ (mod $q$ ) so $b$ is even. $\blacksquare$ $\longleftarrow$ way Consider a prime divisor of $an+1$ like $p$ s.t $p >b$ , suppose $v_p(an+1) =s$ ${an \choose b} = (-1)^b -1 = 0 $ (mod $p^s$ ). So now consider a prime $p \leq b$ , Since $p \mid a$ so $p \nmid an+1$ . No problem here $\textbf{Back to the main Problem :-}$ Since $b$ is $a-$good so $b$ is even and every prime $p \leq b$ divides $a$. $b+2$ is not $a-$good but since $b$ is even so $b+2$ is even so we should have there is a prime $p \leq b+2$ s.t $p \nmid a$ but every $p \leq b$ divides $a$ so it should be either $b+1$ or $b+2$ . but $b+2$ is even and greater than $2$ , we conclude $b+1$ is prime. $\boxed{\mathcal{Q.E.D}}$

Our team solution. Sorry for pic and Russian language.

Funny. Claim: If $b$ is $a$-good then $b$ is even. Proof: If $an + 1 \mid \tbinom{an}{b} - 1$ then $an + 1 \mid an \ldots (an - (b - 1)) - b! \implies an \ldots (an - (b - 1)) \equiv b! \pmod{an+1}$. Note that for all positive integers $k$ in modulo $an + 1$ it follows that $k \equiv -(an - (k - 1)) \pmod{an + 1}$ hence if $b$ is odd then\[b! \equiv -b! \pmod{an + 1} \implies 2b! \equiv 0 \pmod{an + 1}\]and selecting sufficiently large $n$ that makes $an + 1$ prime (possible by Dirichlet) makes this impossible. So indeed, $b$ must be even. $\square$ Next, we show that $b$ is $a$-good if and only if all primes $p \leq b$ divide $a$. The only if direction is easy: since $\text{gcd}(an + 1, b!) = 1$, it follows that\[[an \ldots (an - (b - 1))]\cdot [b \ldots 1]^{-1} \equiv (-1)^b \equiv 1 \pmod{an + 1}\]as desired. The inverse step is possible by $\text{gcd}(an + 1, b!) = 1$. The other direction (if direction) is harder and is the bulk of the problem. FTSoC Suppose that there exists some prime $p \leq b$ for which $p \nmid a$. I claim that we can select $n$ so that $an + 1 \nmid \tbinom{an}{b} - 1$. Select $n$ satisfying\[an \equiv p - 1 \pmod{p^{v_p[b!] + 1}}.\]Note that since $an - (b - 1) \leq an - (p - 1) \leq an$,\[v_p\left[\binom{an}{b}\right] \geq v_p[an - (p - 1)] - v_p[b!] \geq 1\]hence $p \mid \tbinom{an}{b}$. But note that $an + 1 \equiv p \pmod{p^{v_p[b!] + 1}}$ hence $p \mid an + 1$. If $b$ is $a$-good, then $an + 1 \mid \tbinom{an}{b} - 1 \implies p \mid \tbinom{an}{b} - 1$ which is a clear contradiction. Thus, if $b$ is $a$-good, then all primes $p \leq b$ must divide $a$. If $b + 2$ is not $a$-good, then some prime $p \leq b + 2$ must not divide $a$. Finally, note that $b + 2$ cannot be prime since $b$ is even (since $b$ is $a$-good), so that prime must be $b + 1$. $\blacksquare$

In this proof $p$ always denotes a prime number. First of all $b$ has to be even. By Dirichlet, we can have $an+1=p >b!$ for large $n$. Hence we can divide by $b! \mod an+1$ $${an \choose b} - 1 \equiv \frac{an(an-1) \cdots (an-b+1)}{b!} \equiv\frac{(-1)^bb!}{b!} -1 \equiv (-1)^b -1 \mod an+1$$This is $0 \mod an+1$ iff $b$ is even. Now, the main claim. Claim: $b$ is $a$-good $\iff p \leq b \implies p \mid a$ and $b$ is even. First, suppose $b$ is $a$-good. Then $b$ is even from above. Suppose there exists a prime $p \le b$ such that $p \nmid a$. Let $u=\nu_p(b!)$. Then choose $$n \equiv \frac{p-1}{a} \mod p^{u+1}$$Then $an+1 \equiv p \mod p^{u+1}$. So $an-p+1 \equiv 0 \mod p^{u+1}$ and $an-p+1 \geq an-b+1$. So $p \mid {an \choose b} = \frac{an(an-1) \cdots (an-b+1)}{b!} $ since the numerator has a higher p-adic valuation than the denominator. But $p \mid an+1 \mid {an \choose b}-1 \implies p \mid 1$. Contradiction. Now suppose for all primes $p \le b$, $p \mid a$ and $b$ is even. Then $p \nmid an+1$. So $(b!, an+1)=1$. Hence $${an \choose b} - 1 \equiv \frac{an(an-1) \cdots (an-b+1)}{b!} \equiv\frac{(-1)^bb!}{b!} -1 \equiv 0 \mod an+1$$completing the proof of the claim. Now, suppose $b+1$ is not prime. Clearly, $b+2$ is not prime either since it's even and greater than $b$. So $p \le b+2 \implies p \le b \implies p \mid a \implies b+2$ is $a$-good. Contradiction.

Nice problem. Main Claim: $b$ is $a$-good number if and only if $\text{rad}(b!)|a$ and $b$ is even. Proof: If $\text{rad}(b!)|a$ and $b$ is even, then $\gcd(an+1, b!)=1$, $$ \binom{an}{b} = \frac{(am)(am-1)(am-2)\cdots(am - b + 1)}{b!} \equiv \frac{(-1)(-2)\cdots (-b)}{b!} \equiv (-1)^b \equiv 1 \pmod {an+1}$$We now prove the necessity. If $b$ is odd, use Chinese Remainder Theorem to pick $n$ such that $\gcd(an+1, b!)=1$, then $\binom{an}{b} -1 \equiv -2 \pmod{an+1}$, contradiction. Hence $b$ is even, and if there exist a prime $p \le b$ and $p\nmid a$. Pick $n$ such that $an \equiv p-1 \pmod {p^{\lceil \log_p b \rceil}}$, then in base $p$ expansions, the least $\lceil \log_p b\rceil$ number of $an$ is $000\cdots 00(p-1)$, and since $p\le b$, there exist an $i$ digit ($i>0$) of $b$ is not zero, by Lucas' Theorem, $p| \binom{an}{b}$, contradict with $an+1|\binom {an}{b}-1$. $\blacksquare$ The rest is just some easy argument. Since $b$ is $a$-good, $b$ is even and $\text{rad}(b!)|a$. However, $b+2$ is not $a$-good, that mean $\text{rad}((b+2)!) \nmid a$, hence one of $b+1, b+2$ is prime. But $b+2$ is an even number, so $b+1$ is a prime number, we're done. $\square$

dame dame

Another cool NT that requires a good setup - I found this relatively easier than most recent N5's. $\textbf{Lemma 1:}$ $gcd(b!,an+1) = 1$ for all $n \in \mathbb{N}$ $\textbf{Proof)}$ We will prove this by proving that if $p \leq b$ is a prime then $p \mid a$. Assume FTSOC the contrary, then we have that there exist a sufficiently large $n \in \mathbb{N}$ such that $p \mid an+1$. Then, notice that $$v_p(b!) = v_p(an(an-1)...(an-b+1))$$because we have that $$p \mid an+1 \mid {an \choose b} -1$$Now let $t,s \in \mathbb{F}_p$ be the inverse $a \pmod{p}$ and $s \equiv b \pmod{p}$, respectively. Then let $n = t + pk$ for some $k \in \mathbb{N}$ and notice that $$v_p(an(an-1)...(an-b+1)) \geq v_p(an+1-b+s)$$because $b \geq p \geq s \geq 0$ let $at-b+s = pm-1$ for some $m \in \mathbb{N}$, notice that $$v_p(p(ak+m)$$as $k$ varies among all sufficiently large $k$ meaning that we will ultimately get that $$v_p(b!) = v_p(an(an-1)...(an-b+1)) \geq v_p(an+1-b+s) \geq c$$for all $c \in \mathbb{N}$ which is a contradiction. $\square$ Now, notice that $$\frac{(-1)^b \cdot b!}{b!} \equiv 1 \pmod{an+1}$$meaning that $b$ is even and consequently $b+2$ is not prime. Then, if we assume FTSOC that $b+1$ is not prime, we get that for all $n$ such that $an \geq b+2 \geq b$, $${an \choose b+2} ={an \choose b} \cdot \frac{(an-b)(an-b-1)}{(b+1)(b+2)} \equiv 1 \pmod{an+1}$$as $gcd(b+1,an+1) = gcd(b+2, an+1) = 1$ with the assumption that $b+1$ is not prime and $\textbf{Lemma 1}$ which is a contradiction. $\blacksquare$

ilovemath04 wrote: Let $a$ be a positive integer. We say that a positive integer $b$ is $a$-good if $\tbinom{an}{b}-1$ is divisible by $an+1$ for all positive integers $n$ with $an \geq 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. Call a pair $(a,b)$ bad if it doesn't satisfy the relation. $\color{black} \rule{25cm}{2pt}$ Claim: $b$ is even. Proof: By dirchlet's theorem on primes,there must exist infinitely many primes of the form $an+1$ Pick a large prime of this form and by the generalized Wilson Theorem,$\binom{an}{b} \equiv (-1)^b \equiv 1 \pmod {an+1}$ or $b$ is even.$\blacksquare$ $\color{black} \rule{25cm}{2pt}$ Claim: A pair $(a,b)$ is good if and only if $\prod_{p<b,p=\text{prime}} p|a$ Proof: Suppose $(a,b)$ is good. For the sake of contradiction that we had some prime $p\le b$ such that $p\nmid a$. Pick $X>0$ such that\begin{align*} X &\equiv 0\pmod{a} \\ X &\equiv p-1\pmod{p^{v_p(b!)+L}}. \end{align*}for some sufficiently large $L$ Then,$v_p\left(\binom{X}{b}\right)\ge v_p(X-p+1)-v_p(b!)=L$,so $p\mid\binom{X}{b}$. We have $p\mid X+1$, and since $(a,b)$ is good, we have\[p\mid X+1\mid \binom{X}{b}-1,\]which is a clear contradiction. Thus, for all primes $p\le b$, we have $p\mid a$. $\color{black} \rule{25cm}{2pt}$ Now for the sake of contradiction assume that $b+1$ is not prime,then the set of primes less than $b$ and $b+2$ is same implying $b+2$ is $a-$good,a contradiction.$\blacksquare$

ilovemath04 wrote: Let $a$ be a positive integer. We say that a positive integer $b$ is $a$-good if $\tbinom{an}{b}-1$ is divisible by $an+1$ for all positive integers $n$ with $an \geq 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. Take a prime $p$ such that $p\nmid a$ and $p\le b$. Then we know that there exist infinitely many $n$ such that $p\mid an+1$. Now choose one large enough $n$. $p\mid an+1\mid \binom{an}{b}-1\implies p\nmid \binom{an}{b}$. Due to the choice of $n$ we must have $\nu_p(b!)=\nu_p(an\cdot (an-1)\cdot \ldots \cdot (an-b+1))$. Now observe that the left side of the equation is fixed for a fixed prime. But we can make the right hand side as big as we want by choosing suitable $n$. A contradiction. Thus we must have $p\mid a$ for all $p\le b$. Now since $b+2$ is not $a$-good, there must exist a $N$ such that $aN+1\nmid \binom{aN}{b+2}-1$. But $\binom{aN}{b+2}=\binom{aN}{b}\frac{(aN-b)(aN-b-1)}{(b+1)(b+2)}$. If $\gcd(b+1, aN+1)=\gcd(b+2, aN+1)=1$, then we have $aN+1\mid \binom{aN}{b+2}-1$, a contradiction. Now if $b+1$ and $b+2$ are not primes, then their prime divisors are $\le b$, hence divides $a$. This forces them to be relatively prime with $aN+1$. Thus at-least one between $b+1$ and $b+2$ is prime and it divides $aN+1$. Suppose $b+2=q$ is a prime. Now we know $q\mid aN+1\mid \binom{aN}{q-2}-1$. If $q=aN+1$, then we use the fact that $\binom{p-1}{k}=(-1)^k\pmod p$ tells us $b$ is even, thus $b+2$ can not be a prime. Thus $q>aN+1$. But we observe that $ \binom{aN}{q-2}= \frac{(aN-q+3)(aN-q+4)\ldots (aN)}{(q-2)!}\equiv 2\cdot 3 \cdot \ldots (q-1) \equiv -1\pmod q$. this again forces $q=2$. But this isn't possible. This forces $b+1$ is a prime. Remark: I didn't prove that $b$ is even, instead only proved that $b+2$ can't be a prime. Other than that, I feel that all the solutions are isomorphic to each other.

The main thing is to classify $b$ being $a$ good as just $b$ being even and every prime at most $b$ dividing $a$. If this is true, then since $an+1$ is coprime to $b!$, we have that $(an)(an-1)(an-2) \cdots (an-b+1) \equiv b! (-1)^b \equiv b! \pmod{an+1}$ so the divisibility follows. Now I'll show its necessary. By dirichlet pick $an+1$ to be a prime to get that $an+1 | (-1)^b - 1$ so $b$ is even. Suppose $p \le b$ but $p \nmid a$, then pick $an+1$ to be divisible by an extremely large power of $p$ bigger than $v_p(b!)^{10000} + 1000$, then $\binom{an}{b}$ is divisible by $p$ and so $an+1$ cannot divide $\binom{an}{b}$ so indeed we require every prime at most $b$ to divide $a$. For the problem, since $b$ is $a$ good, but not $b+2$, there must be some new prime among $b, b+1, b+2$ but since $b$ is even, we must have that $b+1$ is prime, as desired. $\blacksquare$

The idea is to characterise all $a$-good numbers. Main claim: A number $x$ is $a$-good if and only if $p \hspace{0.3em} | \hspace{0.3em} a$ for each prime number $p \le b$ and $b$ is even. From this, it is easy to see that if $b$ is $a$-good but not $b+2$, then there must be a prime number between $b$ and $b+2$, in other words $b+1$ is prime. Now we prove the main claim. If-direction: Consider a prime factor $p$ of $an+1$. By the condition, $p>b$. Now let $t=v_p(an+1)$ and write $an+1$ as $kp^{t}$. We have the following computation $\mod p^t$: \[{an \choose b} \equiv \frac{(kp^t-1)\cdot (kp^t-2) \cdots (kp^t-b) }{b \cdot b-1 \cdots 1} \equiv \frac{(-1) \cdot (-2) \cdots (-b)}{b \cdot b-1 \cdots 1} \equiv (-1)^b \equiv 1 \mod p^t \]so $p^t \hspace{0.3em} | \hspace{0.3em} {an \choose b}-1$, as desired. Only if-direction: Suppose the condition does not hold. Pick a prime number $p \le b$ with $p \nmid a$. Let $r= \lceil \log_p(b) \rceil$. We may choose a number $n \equiv a^{-1} \cdot (p-1) \mod p^r$. It follows that $p \hspace{0.3em} | \hspace{0.3em} an+1$. However, the trailing $r$ digits of $an$ in base $p$ are all $0$s except for the last one. We can apply Lucas' Theorem and observe that there is a ${0 \choose t}$ term, where $t>0$ is the first digit of $b$. Thus, \[p \hspace{0.3em} | \hspace{0.3em} {an \choose b} \implies p \hspace{0.3em} \nmid \hspace{0.3em} {an \choose b} +1 \implies an+1 \hspace{0.3em} \nmid \hspace{0.3em} {an \choose b}+1\]so $b$ is not $a$-good, as desired.

Suppose not. Consider ${an \choose b+2} - {an \choose b}.$ We claim it is divisible by $an+1$ if $b+1$ is composite. \[{an \choose b+2} - {an \choose b} = {an \choose b} \left(\frac{(an-b)(an-b-1)}{(b+1)(b+2)}-1\right)\]\[={an \choose b}\frac{a^2n^2-(2b+1)an+b^2+b-(b^2+3b+2)}{(b+1)(b+2)}\]\[={an \choose b}\frac{a^2n^2-(2b+1)an-2b-2}{(b+1)(b+2)} \]\[={an \choose b}\frac{(an+1)(an-2b-2)}{(b+1)(b+2)}.\] Since ${an \choose b}\equiv 1 \pmod {an+1},$ $an+1$ divides ${an \choose b+2} - {an \choose b}$ if and only if it divides the numerator of \[\frac{(an+1)(an-2b-2)}{(b+1)(b+2)}\]when expressed as an irreducible fraction. Let $p$ be a prime such that $p\mid an+1$. I claim $p$ does not divide $(b+1)(b+2)$. Note that \[\nu_p{an \choose b} = 0 \implies \nu_p(an(an-1)\dots(an-b+1)) = \nu_p(b!) \] I claim all primes smaller than $b+1$ divide $a$. Indeed, if $p$ contradicts this, taking $an\equiv p-1 \pmod {p^{\nu_p(b!)+1}}$ yields a contradiction on the above equation. So the only case remaining is if $b+2=p\mid an+1$. But then, \[{an\choose b}\equiv \frac{(-1)(-2)\dots(-b)}{b!}\equiv (-1)^b = -1 \pmod {b+2}\]since $b+2>2$ so it it odd. So we are done.

The following classification solves the problem. Claim: $b$ is $a$-good if and only if $b$ is even and $\mathrm{rad}(b!) \mid a$. Proof: It is clearly necessary to have $an+1 \mid \tbinom{an}{b}-1$ in the polynomial sense, so $\tbinom{-1}{b}-1=0$, which clearly implies $b$ is even. Furthermore, this means that we can write $\tfrac{P(an)(an+1)}{b!}=\tbinom{an}{b}-1$ as a polynomial identity for some polynomial $P$ with integer coefficients; $b$ is $a$-good iff $b!$ divides $P(an)$ for all large enough $n$, which is equivalent to it dividing $P(an)$ for all $n$. If $\mathrm{rad}(b!) \mid a$, then $\gcd(an+1,b!)=1$ for all $n$. Since we also have $b! \mid P(an)(an+1)$, this is enough to imply $b! \mid P(an)$ always. Otherwise, fix a prime $p \leq b$ such that $p \nmid a$. Then $an+1$ is surjective modulo prime powers of $p$, hence we may pick some $n$ such that $an \equiv p-1 \pmod{p^{\nu_p(b!)+8729}}$. Then $$P(an)(an+1) \equiv pP(p-1) \equiv b!\left(\binom{p-1}{b}-1\right) \equiv -b! \pmod{p^{\nu_p(b!)+8729}},$$since $p-1<b$, hence $\nu_p(P(p-1))=\nu_p(b!)-1 \implies b! \nmid P(an)$. $\blacksquare$

Claim: $b$ is $a$-good iff for all primes $p \le b$, $p \mid a$ and $b$ is even. First we prove that $b$ must be even. Take large $n$ such that $an+1$ is prime, as this is possible by Dirichlet's. Notice that we have $$\binom{an}{b} \equiv \frac{-1}{(an-b)! \cdot b!} \pmod {an+1}$$and $(b)! \cdot (-1)^b \equiv \frac{-1}{(an-b)!} \pmod {an+1}$, so after simple manipulation we receive $(-1)^b \equiv 1 \pmod {an+1}$, which gives the desired result. Now, take a prime $p < b$, and note that in the base-$p$ representation of $b$, there must be a nonzero spot that is not the rightmost digit. Assume $p$ does not divide $a$. Let this spot be the $k+1$th spot from the right. Now we can infinitely many $n$ such that $an+1 \equiv p^k \pmod{p^{k+1}}$. This implies that the digit in the $k+1$th spot of the base-$p$ representation of $an$ is $0$. By Lucas Theorem this implies that $\binom{an}{b} \equiv 0 \pmod p$, which gives a contradiction as $p \mid an+1$. This proves the "only-if" direction. Finally, we will prove the "if" direction. Simply note that $\operatorname{gcd}(b!, an+1) = 1$, which implies that $$1 \equiv \binom{an}{b} \equiv \frac{(an-b) \cdot (an-b+1) \dots (an-1) \cdot an}{b!} \implies b! \equiv (an-b) \cdot (an-b+1) \dots (an-1) \cdot an \pmod{an+1}$$which is true because $b$ is even. Now, since $b+2$ is not $a$-good and $b$ is $a$-good, there must be a prime between $b$ and $b+2$, implying that $b+1$ is prime.

We claim that $b$ is $a$-good if and only if $b$ is even and for all $p\le b$, $p\mid a$. Note that this claim immediately finishes. It is evident that this is a sufficient condition for $a$-goodness because $\gcd(an+1,b!)=1$ and so \[\binom{an}{b}\equiv \frac{(an)!}{b!(an-b)!}\equiv \frac{an(an-1)\dots(an-b+1)}{b!}\equiv \frac{(-1)(-2)\dots (-b)}{b!}\equiv 1\pmod{an+1}\]as desired. Now we prove necessary. Suppose there exists $p\le b$ and $p\nmid a$. Then, consider a number $n$ such that $an\equiv p-1 \pmod p^{\nu_p(b!)+1}$. Thus, \[p\mid an+1\mid \binom{an}{b}-1\]but also we have $p\mid \tbinom{an}{b}$ by Krummer's theorem, which we can apply because in base-$p$, the digit of value $p^{\nu_p(b!)}$ is $0$ in $an$ but not in $b$. This is a clear contradiction. $~$ Now, suppose $b$ is odd. Then, let $an+1$ be a very very large prime. We have \begin{align*} an+1&\mid \binom{an}{b}-1\\ an+1&\mid (an)(an-1)\dots(an-b+1))-b!\\ an+1&\mid (-1)(-2)\dots(-b)-b!\\ an+1&\mid -2b! \end{align*}which cannot be true for large enough $an+1$. We are done.

Basicly the same solution as in #5 Firstly, we will prove that always $(an+1,b!)=1$ Suppose it is false. Then for some $n$ $an+1,b! \vdots p$. Then $\tbinom{an}{b}$ is not a multiple of $p$, from which by Lucas' theorem we conclude that for all $n$ such that $an+1 \vdots p$, that is $n \equiv r$ (mod $p$) for some $r$, $an$ has all digits in base $p$ $\geq$ digits of $b$. Remove the last digit from $an$ in base $p$, we get $\frac{an-(p-1)}{p}=\frac{a(pk+r)-(p-1)}{p}=ak+\frac{a+1-p}{p}$, this can be anything mod $p^f$ for any $f$, thus all digits except for the last one can be anything, so they can be zeros, thus $b$ is only one-digit, so $b<p$, which contradicts $b! \vdots p$ Now for any prime $p \leq b$, $b! \vdots p$, hence $an+1 \vdots p$ never occurs, so $a \vdots p$ Now I want to prove that $b$ is $a$-good is equivalent to the previous condition and $b$ is even. $\tbinom{an}{b}-1=\frac{(an+1-1)\ldots(an+1-b)}{1*2*\ldots*b}-1 \equiv (-1)^b-1$ (mod $an+1$), because $n$ can be big we must have $b \vdots 2$. Note that if $b \vdots 2$ and the condition proven above is true then we also showed that $b$ is $a$-good Now we know that $a$ is divisible by all primes $\leq b$, but not all $\leq b+2$. Because $b+2 \vdots 2$ is not a prime, $b+1$ must be a prime

Claim: $b$ is $a$-good iff $b$ is even and $a$ is divisible by all primes less than or equal $b$ . We first prove $b$ is even and $a$ is divisible by all primes less than $b$ . implies that $b$ is $a$-good . we basically want to show $t | \frac{(t-1)....(t-b)}{b!}-1$ whenever $t \equiv 1(mod a)$ and $t > b$[if $t=b$ it obviously always works] as $t$ and $b!$ are obviouslly coprime so we can invert it baiscally we want to show $t | \frac{(-1)^b b!}{b!}-1 \iff t| (-1)^b-1$ which obviously holds We now prove the other direction, say we have some prime $p|b!$ such that $p$ does not divide $a$ . Pick some $t \equiv 1$(mod $a$) such that $p^{v_p(b!)+1}|(t-p)$ which must exist by CRT this also would imply $p|t$ But then $p|\frac{(t-1)....(t-b)}{b!}-1$ But $p|pk-1$ where $k$ is some positive integer then which is not possible And proving $b$ is even is easily just choose $n$ such that $b|n$ using this the problem is trivial

First, we present a small claim. Claim: If $b$ is $a$-good, then $b$ is even. Proof. Take $p>b$ with $p\mid an+1$ which is possible since the set of prime divisors of $a$ is finite. Then, apply Lucas' theorem. $\blacksquare$ Now we get to the main claim. Claim: If $b$ is $a$-good, then for all $p<b$, $p \mid a$. Proof. Suppose that $p\nmid a$, so there is an $n$ with $p\mid an+1$ and $n\geq b$. As $b>p$, some digit, say the $k$th in the base $0$ representation of $b$ is nonero. But chooising $a(n+cp^k)$ for suitable $c$ gives the $k$th digit of $a(n+cp^k)$ to be $0$, implying $p\mid \binom{an}{b}$, a contradiction. $\blacksquare$ If $b+1$ was not prime, then every prime dividing $b+2$ divides $a$. Thus for a $p^k\mid an+1$ for some $n$, we have \[\binom{an}{b+2}\equiv \frac{an(an-1)\dots(an-b-1)}{(b+2)!}\equiv (-1)^{b+2}\equiv 1 \pmod{p^k}\]so $b+2$ is $a$-good. We thus conclude. Remark. Feels easy for an N5. I hope I didn't fakesolve

Very interesting Number Theory Question i'd say... Core Claim: if $b$ is $a$-good then for all primes $p \le b$ we have that $p \mid a$. Proof: First we show that $b$ has to be even always by considering: \[P_k(x)=k! \cdot \frac{\binom{x}{k}-(-1)^k}{x+1} \in \mathbb Z[x] \]The reason being that $\binom{-1}{k}=(-1)^k$ and for other values just expand and get everything cancels nicely. So now if $b$ was odd then notice that $an+1 \mid b! \left(\binom{an}{b}+1 \right)$ which would imply that $an+1 \mid 2b!$ so for large $n$ this can't happen clearly. Now that we saw $b$ has to be even in addition note that we now have $b! \mid P_b(an)$, so suppose FTSOC that for some $p \le b$ we had that $p \not \; \mid a$ then in such case we have that $\gcd(a,p)=1$ so we can spam all residues $\pmod p$ which implies $p \mid P_b(x)$ for all $x \in \mathbb Z$, however we now make this pick $x=c \cdot p^{\ell}+1$ for $\ell>1434b! \cdot v_p(b!)$ and large enouh constant $c$, so that $v_p(x-\kappa)<v_p(b!)+1$ for $1 \le \kappa \le b$ (after expanding the poly you see why we need this...from this pick you get $v_p(P_b(x))<1$, a clear contradiction to a previous statement, therefore the claim is proven. Now we prove that the condition that if $p \le b$ for prime $p$ then $p \mid a$ and $b$ being even, then that's enough to conclude that $b$ is $a$-good. Indeed if this assumption was true then $\gcd(an+1,b!)=1$ which automatically gives the desired divisbility from the existence of $P_b(x)$. To finish note that if $b$ was $a$-good but $b+2$ wasn't $a$-good then there is a prime between $b+2,b$ which forcefully is $b+1$ thus we are done .

Suppose there exists a prime $p\leq b$ such that $p\nmid a$. Let the maximum power that divides a value $\leq b$ be $k$. We can choose $n$ such that $an\equiv -1\pmod p^{k+1}$. Thus we get that $\nu_p(\binom{an}{b})=0$. However we have that $p\nmid an+1$ which is a contradicition. Thus we get that all primes $p\leq b$ must divide $b$. Thus we get that $\binom{an}{b}\equiv (-1)^b\pmod an+1$, so we must have that $b$ is even. Thus if $b$ is $a$-good and $b+2$ is not $a$-good we must have a prime $p\leq b+2$ and $>b$ that does not divide $a$, as $b+2$ is even this prime must be $b+1$ which suffices.