Find all pairs of positive integers $(k, m)$ such that for any positive integer $n$, the product\[(n+m)(n+2m)\cdots(n+km)\]is divisible by $k!$.
Problem
Source: BdMO 2024 Secondary National P9
Tags: number theory, factorial, Divisibility, p-adic
21.06.2024 17:30
Let \[ f(k,m,n) = \frac{ \prod_{l=1}^k (n+lm)}{k!} \]For a positive integer $n$, let $\hbox{lpf}(n)$ denote the least positive prime factor of $n$. For convenience, let $\hbox{lpf}(1) = \infty$. We claim that (*) $f(k,m,n)$ is integer if and only if $k<\hbox{lpf}(m)$. To show this, first, assume that $k<\hbox{lpf}(m)$. If $k=1$, there is nothing to prove. If $m=1$, $f(k,m,n) = \binom{n+k}{k}$ so is an integer. Now suppose that $m \ge 2$ and $k \ge 2$. The numerator of $f(k,m,n)$ is a product of \[ N=\left\{ n+m, n+2m, n+3m, \ldots , n+km \right\} \]Consider $p$, a positive prime number less than or equal to $k$ and $e = \nu_p (k!)$ be the valuation. Note that $m$ is relatively prime to $p$. Hence there are at least $\left \lfloor \frac{k}{p} \right \rfloor$ multiple of $p$ among elements in $N$ since every $p$ consecutive elements of $N$ contains at least one multiple of $p$, at least $\left \lfloor \frac{k}{p^2} \right \rfloor$ multiple of $p^2$ among elements in $N$ since every $p^2$ consecutive elements of $N$ contains at least one multiple of $p^2$, in general at least $\left \lfloor \frac{k}{p^l} \right \rfloor$ multiple of $p^l$ among elements in $N$ since every $p^l$ consecutive elements of $N$ contains at least one multiple of $p^l$. Hence if follows from the legendre's formula that $f(k,m,n)$ is an integer in this case. Now, conversely, suppose that $k \ge \hbox{lpf}(m)$. This forces that $m \ge 2$. Let $p=\hbox{lpf}(m)$. The numerator of $f(k,m,1)$ is a product of numbers of the form $1+lm$ which is relatively prime to $p$. However, $k!$ is a multiple of $p$. Therefore $f(k,m,1)$ is not an integer which completes the proof.
17.10.2024 02:47
Case 1: (k,1) And Case 2:(1,m) because if k=1 Then the equation become 1!|(n+m)
14.01.2025 18:24
I don't understand. Plash any one solve this question easily.