2003 Indonesia MO Problems/Problem 7

Problem

Let $k,m,n$ be positive integers such that $k > n > 1$ and the greatest common divisor of $k$ and $n$ is $1$. Prove that if $k-n$ divides $k^m - n^{m-1}$, then $k \le 2n-1$.

Solution

If $k-n$ divides $k^m - n^{m-1}$, then we have $$k^m \equiv n^{m-1} \pmod{k-n}.$$ Because $k = (k-n)+n$, $k \equiv n \pmod{k-n}$. That means $$k^m \equiv k^{m-1} \pmod{k-n}.$$ Since $\gcd(k,n) = 1$, $k-n$ does not share any factors with $k$. We can multiply both sides by the modular multiplicative inverse, so $$k \equiv 1 \pmod{k-n}.$$ Thus, $k = (k-n)a + 1$, where $a$ is an integer. After rearranging terms, we have $$k(a-1) = an-1$$ If $a = 1$, then $n = 1$. This can not happen, so we can divide both sides by $a-1$ without losing any solutions. \begin{align*} k &= \frac{an-1}{a-1} \\ &= \frac{a}{a-1}n - \frac{1}{a-1} \end{align*} To finish the proof that $k \le 2n-1$, we will use induction. For the base case, letting $a = 2$ results in $k = 2n - 1$, which satisfies the inequality.

For the inductive step, assume $\frac{a}{a-1}n - \frac{1}{a-1} \le 2n-1$. Multiplying both sides by $a-1$ and dividing both sides by $a$ results in $$\frac{a}{a}n - \frac{1}{a} \le (2n-1)\frac{a-1}{a}$$ Adding both sides by $\frac{n}{a}$ results in \begin{align*} \frac{a+1}{a}n - \frac{1}{a} &\le \frac{2an -2n - a + 1}{a} + \frac{n}{a} \\ &\le \frac{2an-n-a+1}{a} \\ &\le 2n - 1 + \frac{1-n}{a} \end{align*} Because $n,a > 1$, the value $\tfrac{1-n}{a}$ is less than 0. Thus, $2n - 1 + \frac{1-n}{a} < 2n - 1,$ so we have $$\frac{a+1}{a}n - \frac{1}{a} < 2n - 1$$ The inductive step is complete, so we have proven that $k \le 2n-1$.