Prove that for an arbitrary prime p≥3 the number of positive integers n, for which p|n!+1 does not exceed cp2/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 ((k+t)!+1)−(k!+1)=k!((k+1)⋯(k+t)−1).Since k is a good integer, gcd, 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