Bulgarian National Olympiad - Final Round

Question

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 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)?

Accepted Answer

(Victor Kostadinov) The answer is yes. Fix a positive integer

n

and two large distinct primes

p, q > n

. Let

d_{p} = ord_{p} (n)

,

d_{q} = ord_{q} (n)

,

c_{p} = ν_{p} (n^{d_{p}} - 1)

,

c_{q} = ν_{q} (n^{d_{q}} - 1)

and let

c = ν_{p} (d_{q})

,

d = ν_{q} (d_{p})

. Pick two sufficiently large constants

a, b

, and let

M := d_{p} d_{q} p^{(a - 1) c_{p} + b c_{q} - c} q^{a c_{p} + (b - 1) c_{q} + 1 - d}

and finally choose

M_{n}

to consist of

m = M (1 + i M)

for

i = 1, 2, \dots

.

By LTE, we have

ν_{p} (n^{m} - 1) = ν_{p} (n^{d_{p}} - 1) + ν_{p} (\frac{m}{d _{p}}) = c_{p} + c + (a - 1) c_{p} + b c_{q} - c = a c_{p} + b c_{q}

(we used that

gcd (1 + i M, p) = 1

) and similarly

ν_{q} (n^{m} - 1) = a c_{p} + b c_{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.

□