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$ .

2003 Indonesia MO (Problems)
Preceded by Problem 6	1 • 2 • 3 • 4 • 5 • 6 • 7 • 8	Followed by Problem 8
All Indonesia MO Problems and Solutions

Page

Toolbox

Search

2003 Indonesia MO Problems/Problem 7

Problem

Solution

See Also