HMMT-Nov 2022 team, Problem 9

Call an ordered pair $(a, b)$ of positive integers fantastic if and only if $a, b \leq 10^{4}$ and \[ \operatorname{gcd}(a \cdot n !-1, a \cdot(n+1) !+b)>1 \] for infinitely many positive integers $n$. Find the sum of $a+b$ across all fantastic pairs $(a, b)$.

Solution: Solution: We first prove the following lemma, which will be useful later. Lemma: Let $p$ be a prime and $1 \leq n \leq p-1$ be an integer. Then, $n !(p-1-n) ! \equiv(-1)^{n-1}(\bmod p)$. Proof. Write \[ \begin{aligned} n !(p-n-1) ! & =(1 \cdot 2 \cdots n)((p-n-1) \cdots 2 \cdot 1) \\ & \equiv(-1)^{p-n-1}(1 \cdot 2 \cdots n)((n+1) \cdots(p-2)(p-1)) \quad(\bmod p) \\ & =(-1)^{n}(p-1) ! \\ & \equiv(-1)^{n-1} \quad(\bmod p) \end{aligned} \] (where we have used Wilson's theorem). This implies the result. Now, we begin the solution. Suppose that a prime $p$ divides both $a \cdot n !-1$ and $a \cdot(n+1) !+b$. Then, since \[ -b \equiv a \cdot(n+1) ! \equiv(n+1) \cdot(a \cdot n !) \equiv(n+1) \quad(\bmod p) \] we get that $p \mid n+b+1$. Since we must have $n<p$ (or else $p \mid n$ !), we get that, for large enough $n$, $n=p-b-1$. However, by the lemma, \[ a(-1)^{b-1} \equiv a \cdot b !(p-1-b) !=a \cdot b ! n ! \equiv b ! \quad(\bmod p) \] This must hold for infinitely many $p$, so $a=(-1)^{b-1} b$ !. This forces all fantastic pairs to be in form $((2 k-1) !, 2 k-1)$. Now, we prove that these pairs all work. Take $n=p-2 k$ for all large primes $p$. Then, we have \[ \begin{aligned} a \cdot n ! & \equiv(2 k-1) !(p-2 k) ! \\ & \equiv(-1)^{2 k} \equiv 1 \quad(\bmod p) \\ a \cdot(n+1) ! & \equiv(n+1) \cdot(a \cdot n !) \\ & \equiv(p-2 k+1) \cdot 1 \equiv-(2 k-1) \quad(\bmod p) \end{aligned} \] so $p$ divides the gcd. The answer is $(1+1)+(6+3)+(120+5)+(5040+7)=5183$. $\fbox{5183}$.

Answer: 5183