Maths Olympiad Prep

Library / /9 of 43

Number theory Difficulty 7.7 National olympiad, round 2 Find the answer

Is the set of positive integers nn such that n!+1n!+1 divides (2012n)! finite or infinite?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution 1. Consider a positive integer nn with n!+1(2012n)n!+1 \mid(2012 n) !. It is well-known that for arbitrary nonnegative integers a1,,aka_{1}, \ldots, a_{k}, the number (a1++ak)\left(a_{1}+\ldots+a_{k}\right) ! is divisible by a1!ak!a_{1}!\cdot \ldots \cdot a_{k}!. (The number of sequences consisting of a1a_{1} digits 1,,ak1, \ldots, a_{k} digits kk, is (a1++ak)!a1!ak!\frac{\left(a_{1}+\ldots+a_{k}\right)!}{a_{1}!\ldots \ldots a_{k}!}.) In particular, (n!)2012(n!)^{2012} divides (2012n)!(2012 n)!. Since n!+1n!+1 is co-prime with (n!)2012(n!)^{2012}, their product (n!+1)(n!)2012(n!+1)(n!)^{2012} also divides (2012n)(2012 n) !, and therefore (n!+1)(n!)2012(2012n)!(n!+1) \cdot(n!)^{2012} \leq(2012 n)! By the known inequalities (n+1e)n<n!nn\left(\frac{n+1}{e}\right)^{n}<n!\leq n^{n}, we get (ne)2013n<(n!)2013<(n!+1)(n!)2012(2012n)!<(2012n)2012n\left(\frac{n}{e}\right)^{2013 n}<(n!)^{2013}<(n!+1) \cdot(n!)^{2012} \leq(2012 n)!<(2012 n)^{2012 n} Therefore, n<20122012e2013n<2012^{2012} e^{2013}. Therefore, there are only finitely many such integers nn. Solution 2. Assume that n>2012n>2012 is an integer with n!+1(2012n)n!+1 \mid(2012 n) !. Notice that all prime divisors of n!+1n!+1 are greater than nn, and all prime divisors of (2012n)! are smaller than 2012n2012 n. Consider a prime pp with n<p<2012nn<p<2012 n. Among 1,2,,2012n1,2, \ldots, 2012 n there are [2012np]<2012\left[\frac{2012 n}{p}\right]<2012 numbers divisible by pp; by p2>n2>2012np^{2}>n^{2}>2012 n, none of them is divisible by p2p^{2}. Therefore, the exponent of pp in the prime factorization of (2012n)(2012 n) ! is at most 2011. Hence, n!+1=gcd(n!+1,(2012n)!)<n<p<2012pp2011n!+1=\operatorname{gcd}(n!+1,(2012 n)!)<\prod_{n<p<2012 p} p^{2011}. Applying the inequality pXp<4X\prod_{p \leq X} p<4^{X}, n!<n<p<2012pp2011<(p<2012np)2011<(42012n)2011=(420122011)nn!<\prod_{n<p<2012 p} p^{2011}<\left(\prod_{p<2012 n} p\right)^{2011}<\left(4^{2012 n}\right)^{2011}=\left(4^{2012 \cdot 2011}\right)^{n} Again, we have a factorial on the left-and side and a geometric progression on the right-hand side.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.