Prove that for an arbitrary prime $p \ge 3$ the number of positive integers $n$, for which $p | n! +1$ does not exceed $cp^{2/3}$, where c is a constant that does not depend on $p$.
Problem
Source: Ukraine TST 2014 p12
Tags: prime, number theory, Divisibility
01.05.2020 01:17
Interesting, assuming I did this problem correctly (which I'm not 100% sure of). Call an integer $n$ good if $p$ divides $n! + 1$; observe that $p-1$ is the largest good integer. The key to this problem lies in the following lemma. Lemma 1: For each positive integer $t$, there are at most $t$ good integers $k$ such that $k+t$ is also good. Proof. If $p$ divides both $(k+t)! + 1$ and $k! + 1$, then $p$ must also divide \[ \big((k+t)! + 1\big) - \big(k! + 1\big) = k!\big((k+1)\cdots(k+t) - 1\big). \]Since $k$ is a good integer, $\gcd(p,k!) = 1$, so in fact \[ p\mid (k+1)\cdots (k+t) - 1. \]But the right hand side is a polynomial of degree $t$, which has at most $t$ solutions in $\mathbb F_p$ by Lagrange. $\square$ Let \[ n_1 < n_2 < \cdots < n_m = p-1 \]denote the set of good integers. For each $1\leq j\leq p$, let $a_j$ denote the number of integers $1\leq k\leq m$ such that $n_k - n_{k-1} = j$. By the lemma, $a_j\leq j$ for each $j$. Furthermore, we are given that \[ a_1 + 2a_2 + \cdots + pa_p = \sum_{k=1}^m(n_k - n_{k-1}) = n_m - n_1\leq p, \]and we wish to maximize $a_1 + \cdots + a_p$. The rest of this problem is encoded in the following purely algebraic lemma. Lemma 2. Suppose $b_1,\ldots, b_n$ are nonnegative real numbers such that \[ b_1 + 2b_2 + \cdots + nb_n \leq n\qquad\qquad(*) \]and $b_i\leq i$ for all $i$. Then there exists a constant $c > 0$ such that \[ b_1 + b_2 + \cdots + b_n \leq cn^{2/3}. \] Proof. Throughout this proof, we will use the notation $a\lesssim b$ to denote "less than or equal to up to a constant". Without loss of generality we may replace $(*)$ with the stricter condition $b_1 + 2b_2 + \cdots + nb_n = n$. Consider an arbitrary $n$-tuple $(b_1,\ldots, b_n)$ of nonnegative real numbers satisfying the given conditions. If there exist integers $r < s$ with $b_r < r$ but $b_s > 0$, then we may replace $(b_1,\ldots, b_n)$ by the tuple \[ (b_1',\ldots, b_n') = (b_1,\ldots, b_{r-1},b_r + \tfrac{s\varepsilon}r,b_{r+1},\ldots, b_{s-1},b_s - \varepsilon,b_{s+1},\ldots), \]where $\varepsilon$ is chosen small enough that $b_r + \tfrac{s\varepsilon}r < r$ and $b_s > \varepsilon$. (In other words, we adjust the values of $b_r$ and $b_s$ slightly while fixing all other elements in the tuple.) Then \[ b_1' + 2b_2' + \cdots + nb_n' = b_1 + 2b_2 + \cdots + nb_n = n, \]but the sum $b_1 + b_2 + \cdots + b_n$ increases. This means that $(b_1,\ldots,b_n)$ does not achieve our maximum. In particular, our maximum is achieved when \[ b_j = \begin{cases}j&\text{if }1\leq j\leq t,\\ 0&\text{if }j\geq t+2, \end{cases} \]where $t$ is some positive integer at most $n$. Finally, observe that \[ n = b_1 + 2b_2 + \cdots + nb_n \geq 1^2 + 2^2 + \cdots + t^2 \gtrsim t^3, \]and hence $t \lesssim n^{1/3}$. Then \[ b_1 + b_2 + \cdots + b_n = b_1 + \cdots + b_{t+1} \leq 1 + \cdots + (t+1) \lesssim t^2 \lesssim n^{2/3}, \]and so $b_1 + \cdots + b_n\leq cn^{2/3}$ for some constant $c$. $\square$ The problem falls upon applying Lemma 2 to the sequence $(a_1,\ldots, a_p)$. $\blacksquare$
01.05.2020 02:13
This was also on China TST 2009 https://artofproblemsolving.com/community/c6h268921p3009343