Suppose that $a$ is an integer and that $n! + a$ divides $(2n)!$ for infinitely many positive integers $n$. Prove that $a = 0$.
Problem
Source:
Tags: number theory
fractals
11.08.2015 21:40
I like this problem.
We have $n! + a$ divides $(2n)!$ for infinitely many $n$. Suppose that $a \not= 0$.
For all $n \ge |a|$, $\gcd(n!, n! + a) = a$. Furthermore, for $n$ large enough, say $n \ge 2|a|$, we have $\gcd\left(n!, \frac{n!}{a} + 1\right) = 1$.
Thus only primes from $n$ to $2n$, exclusive, can divide $\frac{n!}{a} + 1$. Furthermore, each can only divide it once, since they all only appear in $(2n)!$ precisely once. So $n! + a|a(2n - 1)(2n - 3)\ldots(n + o)$, where $n + o$ is the smallest odd number greater than $n$. Let $n + e$ be the smallest even number greater than $n$.
Then $(2n)! = n!\cdot (2n)(2n - 1)\ldots(n + 1) = n!2^{\frac{n - e + 2}{2}}(n)(n - 1)\ldots\left(\frac{n + e}{2}\right)\cdot (2n - 1)(2n - 3)\ldots(n + o) \ge n!2^{\frac{n}{2}}\left(\frac{n}{2}\right)^{\frac{n}{2}}\cdot\left(\frac{n!}{a} + 1\right)$.
So $\frac{(2n)!}{2^nn!} \ge \left(\frac{n}{4}\right)^{\frac{n}{2}}\cdot\left(\frac{n!}{a} + 1\right) \ge 4^n\left(\frac{n!}{a}\right)$ for $n \ge 64$.
The LHS is the product of the odd numbers from one to $2n - 1$, clearly at most $2^nn!$, while the RHS clearly exceeds that for large enough $n$.
We have a contradiction!