Find all pairs of integers $ \left(m,n\right) $ such that $ \left(m,n+1\right) = 1 $ and $$ \sum\limits_{k=1}^{n}{\frac{m^{k+1}}{k+1}\binom{n}{k}} \in \mathbb{N} $$
Problem
Source: 2018 Taiwan TST Round 1
Tags: number theory
Aryan-23
30.11.2019 20:18
JustPostTaiwanTST wrote: Find all pairs of integers $ \left(m,n\right) $ such that $ \left(m,n+1\right) = 1 $ and $$ \sum\limits_{k=1}^{n}{\frac{m^{k+1}}{k+1}\binom{n}{k}} $$ The question seems to be incomplete Did you mean that the sum is an integer ?
Math-wiz
01.12.2019 06:58
It is a well known result using calculus that the given expression equals $$\frac{(m+1)^{n+1}+1}{n+1}-m$$Now, the problem is reduced to finding all natural numbers $m,n$ with $(m,n+1)=1$ sucht that
$n+1|(m+1)^{n+1}+1$
Now, observe that if $n+1$ is odd, and $m+1=k(n+1)-1$, then after binomial expansion, the 1 in the numerator vanishes, and all other terms are multiples of $n+1$.
Hence, $\{m,n\}=\{kn+k-2,n\}$ works for all even $n$. Now, from the condition $(m,n+1)=1$, we find the exceptions.
$(m,n+1)=(k(n+1)-2,n+1)=(n-1,n+1)$
As $n$ is even, $(n-1,n+1)=1$ without any exceptions
Hence, a set of solutions is
$(m,n)=(kn+k-2, n)$ for all even $n$ and all $k\in\mathbb{N}$
Math-wiz
01.12.2019 07:36
Actually I am quite weak at solving such questions of NT. The solution is basically solving for $(m+1)^{n+1}\equiv -1\pmod{n+1}$, with the condition, $(m,n+1)=1$
Rickyminer
21.02.2021 17:43
Actually @above messed up with calculations, the right value is \begin{align*} \sum\limits_{k=1}^{n}{\frac{m^{k+1}}{k+1}\binom{n}{k}} &=\sum\limits_{k=1}^{n}{\frac{m^{k+1}}{n+1}\binom{n+1}{k+1}} \\ &=\frac{1}{n+1} \sum\limits_{k=2}^{n+1} m^k\binom{n+1}{k} \\ &=\frac{(1+m)^{n+1}-1-m\binom{n+1}{1}}{n+1} \end{align*}So the problem boils down to solving $$(m+1)^{n+1}\equiv \color{red}1 \color{black}\pmod{n+1},$$with $\gcd(m,n+1)=1$. Let $p$ be the smallest prime divisor of $n+1$. By FLT we have $$1+m=(1+m)^{\gcd(n+1,p-1)} \equiv 1 \pmod{p}$$So $p \mid \gcd(n+1,m)$, absurd. Hence there is no solution.