Library / Bulgarian National Olympiad - Final Round /2 of 2

Bulgarian National Olympiad - Final Round

Number theory Difficulty 5.9 AIME, harder Prove it Bulgaria

Is it true that for any positive integer $n > 1$ , there exists an infinite arithmetic progression $M_n$ of positive integers, such that for any $m \in M_n$ , the number $n^m - 1$ is not a perfect power (a positive integer is a perfect power if it is of the form $a^b$ for positive integers $a, b > 1$ )?

Solution

(Victor Kostadinov) The answer is yes. Fix a positive integer $n$ and two large distinct primes $p, q > n$ . Let $d_p = \text{ord}_p(n)$ , $d_q = \text{ord}_q(n)$ , $c_p = \nu_p(n^{d_p} - 1)$ , $c_q = \nu_q(n^{d_q} - 1)$ and let $c = \nu_p(d_q)$ , $d = \nu_q(d_p)$ . Pick two sufficiently large constants $a, b$ , and let $M := d_p d_q p^{(a-1)c_p + bc_q - c} q^{ac_p + (b-1)c_q + 1 - d}$ and finally choose $M_n$ to consist of $m = M(1 + iM)$ for $i = 1, 2, \dots$ .

By LTE, we have
$\nu_p(n^m - 1) = \nu_p(n^{d_p} - 1) + \nu_p\left(\frac{m}{d_p}\right) = c_p + c + (a-1)c_p + bc_q - c = ac_p + bc_q$
(we used that $\text{gcd}(1 + iM, p) = 1$ ) and similarly $\nu_q(n^m - 1) = ac_p + bc_q + 1$ , which are consecutive, i.e. they can't have a common divisor greater than 1 and thus $n^m - 1$ can't be a perfect power. $\square$

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.