$x_1x_2\ldots x_{n+1}-1$ is divisible by an odd prime.

contest-mathnumber theory

Let $m$ and $n$ be positive integers such that $m>n$. Define $x_k=\frac{m+k}{n+k}$ for $k=1,2,\ldots,n+1$. Prove that if all the numbers $x_1,x_2,\ldots,x_{n+1}$ are integers, then $x_1x_2\ldots x_{n+1}-1$ is divisible by an odd prime.

I couldn't proceed but I got we have that $n+k\mid m+k$, which implies that $n+k\mid m-n$ for all $k=1,2,…,n+1$.

Any walkthroughs?

Best Answer

Almost-complete sketch of a solution.
If you're stuck, show what you've tried.

  1. Let $ \operatorname{LCM} (n+1, n+2, \ldots, 2n+1) = L$.
    Show that $m -n = ML$ for some integer $M > 0 $, which follows from what you have shown (with a bit more work). This is a crucial observation.

  2. Show that $ x_k = 1 + M\frac{L}{n+k}$.

  3. Show that (first, make sense of this, but it should be clear when you start writing it out.) $$ \left(\prod x_k\right) - 1 = \sum_{i=1}^{n+1} \sum_{\sigma_i \in S_n} \left( M^i \prod_{j=1}^i \frac{L}{n+\sigma_i (j) } \right) $$

  4. Let $ 2^r \mid \mid M$ be the highest power of $2$ that divides $M$.
    Show that the RHS is divisible by $2^r$, but not by $ 2^{r+1}$. This is the other crucial observation, so try it first before reading on.

Show that $n+k$ must be a power of $2$ for some $k \in [1, n+1]$. (Bonus: Show that this is unique.)
What is the parity of $ \frac{L}{n+k}$ when $n+k$ is the highest (only) power of 2?
What is the parity of $ \frac{L}{n+k}$ when $n+k$ otherwise?
Now focus on $ i = 1$, to show that $ \sum \frac{L}{n+k} $ is odd.

  1. Hence, the RHS is not a power of $2,$ so it has an odd factor per Peter's comment.

Notes.

  • As a corollary, $\prod x_i$ has the opposite parity of $M$.
  • It's common to test with $M = 1$ [EG $(n, m) = (2, 14), (3, 63)$], which makes us think that $\prod x_i$ must be even so the expression must be odd. This is a mistake that I made initially.
  • Using $ M = 2$ will show that the expression could be even, and hence we will need to tweak the approach.
Related Question