2003 Indonesia MO Problems/Problem 7

Revision as of 23:44, 11 August 2018 by Rockmanex3 (talk | contribs) (Solution to Problem 7 -- awesome number theory problem)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

See Also

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
Invalid username
Login to AoPS