November 15, 2024
OC692 (from Crux Mathematicorum Vol. 50, No. 7)
Prove that for any positive integer \(n\), the number
\[n(2n + 1)(3n + 1) \cdot \ldots \cdot (1966n + 1)\]
is divisible by every prime number less than 1966.
We just need to prove that for each prime number \(p\) less than 1966, the product \[n(2n + 1)(3n + 1) \cdot \ldots \cdot (1966n + 1)\] is a multiple of \(p\) for any positive integer \(n\).
Since it is trivial when \(n\) is a multiple of \(p\), we only need to consider the case when \(n\) is not a multiple of \(p\), i.e. \(n\) and \(p\) are co-prime. In this case, by Bézout’s lemma, we can find a positive integer \(m\) less than \(p\) by Euclidean’s algorithm such that \(kp - nm = 1\) where \(k\) is a positive integer. Note that if \(m==1\), we can still have \((k+n)p - n(m+p)=1\) and \(m+p \le 1966\). Therefore when \(n\) and \(p\) are co-prime, there must be at least one term in \((2n + 1)(3n + 1) \cdot \ldots \cdot (1966n + 1)\) which is a multile of \(p\).