Maths Olympiad Prep

Library / /114 of 397

Number theory Difficulty 5.4 AIME, harder Prove it Taiwan

Find all pairs of positive integers (m,n)(m, n) such that mm and (n+1)(n + 1) are relatively prime, and
k=1nmk+1k+1(nk) \sum_{k=1}^{n} \frac{m^{k+1}}{k+1} \binom{n}{k}
is an integer.

Solution

There exists no such (m,n)(m, n).
Suppose (m,n)(m, n) is a solution. By the fact that (n+1)(nk)=(k+1)(n+1k+1)(n + 1) \binom{n}{k} = (k + 1) \binom{n+1}{k+1},
we have
k=1nmk+1k+1(nk)=k=1nmk+1n+1(n+1k+1)=1n+1l=0n+1ml(n+1l)=1n+1((1+m)n+11). \begin{aligned} \sum_{k=1}^{n} \frac{m^{k+1}}{k+1} \binom{n}{k} &= \sum_{k=1}^{n} \frac{m^{k+1}}{n+1} \binom{n+1}{k+1} = \frac{1}{n+1} \sum_{l=0}^{n+1} m^l \binom{n+1}{l} \\ &= \frac{1}{n+1} ((1+m)^{n+1} - 1). \end{aligned}
Since this is an integer, we must have
(1+m)n+11(modn+1). (1+m)^{n+1} \equiv 1 \pmod{n+1}.
This ensures that when mm is odd, (n+1)(n+1) must be odd. On the other hand, since gcd(m,n+1)=1\gcd(m, n + 1) = 1, if mm is even, (n+1)(n + 1) would also be odd. So, in any case, (n+1)(n + 1) is odd.
Let pp be the smallest prime divisor of (n+1)(n + 1), then pp is odd, and
(1+m)n+11(modp). (1+m)^{n+1} \equiv 1 \pmod{p}.
However, by Fermat's little theorem, we have (1+m)p11(modp)(1+m)^{p-1} \equiv 1 \pmod{p}.
This means that
(1+m)gcd(n+1,p1)1(modp). (1+m)^{\gcd(n+1,p-1)} \equiv 1 \pmod{p}.
However, since pp is the smallest prime divisor of n+1n+1, gcd(n+1,p1)=1\gcd(n+1, p-1) = 1, so we get (1+m)1(modp)(1+m) \equiv 1 \pmod{p}, which means that pmpgcd(m,n+1)p|m \Rightarrow p|\gcd(m, n+1).
Contradiction!

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from the original; metadata (topic, difficulty) added by this project.