Given an non-negative integer $k$, show that there are infinitely many positive integers $n$ such that the product of any $n$ consecutive integers is divisible by $(n+k)^2+1$.
Problem
Source: Romanian 2018 TST Day 1 Problem 4
Tags: number theory, pell equation, Sophie Germain identity, factorial
25.05.2020 18:56
It suffices to prove that there exist infinitely many positive integers $n$ such that for a fixed $k$, we have \[ (n+k)^2 + 1 | n! \]Just take $n = 2a^2 - k$ for $a \equiv 1 \ (\text{mod} \ 5)$ large enough. This gives us $(n+k)^2 + 1 = 4a^4 + 1 = (2a^2 - 2a + 1)(2a^2 + 2a + 1) =5 \cdot \frac{2a^2 + 2a + 1}{5} (2a^2 - 2a + 1) $ But $5 < \frac{2a^2 + 2a + 1}{5} < 2a^2 - 2a + 1 < 2a^2 - k$ for large enough $a$. Done!
11.02.2022 18:47
IndoMathXdZ wrote: It suffices to prove that there exist infinitely many positive integers $n$ such that for a fixed $k$, we have \[ (n+k)^2 + 1 | n! \]Just take $n = 2a^2 - k$ for $a \equiv 1 \ (\text{mod} \ 5)$ large enough. This gives us $(n+k)^2 + 1 = 4a^4 + 1 = (2a^2 - 2a + 1)(2a^2 + 2a + 1) =5 \cdot \frac{2a^2 + 2a + 1}{5} (2a^2 - 2a + 1) $ But $5 < \frac{2a^2 + 2a + 1}{5} < 2a^2 - 2a + 1 < 2a^2 - k$ for large enough $a$. Done! What about the other product of n consecutive integer , like (n+1)(n+2)...2n
11.02.2022 19:06
Product of any consecutive $n$ integers is divisible by $n!$.
12.02.2022 04:10
From $n! \mid (a+1)(a+2)(a+3) \ldots (a+n)$ $\forall a =0,1,2, \ldots$, which is observed by considering the exponents as \[{v_p}(n!) = \sum\limits_{k = 1}^\infty {\left\lfloor {\frac{n}{{{p^k}}}} \right\rfloor } \le \sum\limits_{k = 1}^\infty {\left( {\left\lfloor {\frac{{a + n}}{{{p^k}}}} \right\rfloor - \left\lfloor {\frac{a}{{{p^k}}}} \right\rfloor } \right)} = {v_p}((a + n)!) - {v_p}(a!) = {v_p}((a + 1)(a + 2)(a + 3) \ldots (a + n))\]Now we only have to prove that there are infinitely many $n$ such that \[ (n+k)^2 + 1 | n! \]Or there are infinitely many $n$ such that \[ n^2 + 1 | (n-k)! \]Consider the Pell Equation $x^2-5y^2=-1$, which has solutions since ($2 \ne 3$), with all the solutions $(x_n,y_n)$ Taking $n= x_i $ for an sufficiently large $i$, then there exists $ a >5 $ such that $n^2+1=5a^2$ Also we have \[\frac{n-k}{2} \ge \frac{{n }}{{\sqrt 5 }} + 1 > a \text{ for a sufficiently large n } \]Hence $5< a < 2a < n-k$, which leads to $$ n^2+1 = 5a^2 = 5\cdot a \cdot a \mid 5 \cdot a \cdot 2a \mid (n-k)! $$And we are done!!