Maths Olympiad Prep

Library / /1 of 2

Number theory Difficulty 8.0 Shortlist Prove it Romania

Given an integer k2k \ge 2, determine all positive integers n1,n2,,nkn_1, n_2, \dots, n_k satisfying
n22n11,n32n21,,nk2nk11,n12nk1. n_2 \mid 2^{n_1-1}, \quad n_3 \mid 2^{n_2-1}, \quad \dots, \quad n_k \mid 2^{n_{k-1}-1}, \quad n_1 \mid 2^{n_k-1}.

Solution

The required numbers are n1=n2==nk=1n_1 = n_2 = \dots = n_k = 1.

For every integer m>1m > 1, let p(m)p(m) denote the least prime divisor of mm. We show that, if mm and \ell are integers greater than 11, and m21m \mid 2^{\ell} - 1, then p(m)<p()p(m) < p(\ell). Since p(m)p(m) is odd, p(m)2p(m)11p(m) \mid 2^{p(m)-1} - 1, and since p(m)21p(m) \mid 2^{\ell} - 1, it follows that p(m)2gcd(,p(m)1)1p(m) \mid 2^{\gcd(\ell, p(m)-1)} - 1. Notice that gcd(,p(m)1)>1\gcd(\ell, p(m)-1) > 1, since p(m)>1p(m) > 1, to infer that \ell has a prime divisor not exceeding p(m)1p(m) - 1, and conclude thereby that p(m)<p()p(m) < p(\ell).

Suppose now, if possible, that n1>1n_1 > 1. Then nk>1n_k > 1, so nk1>1n_{k-1} > 1, and so on and so forth all the way down to n2>1n_2 > 1. Hence p(n1)<p(n2)<<p(nk)<p(n1)p(n_1) < p(n_2) < \dots < p(n_k) < p(n_1) which is a contradiction. Consequently, n1=1n_1 = 1, so n2=1n_2 = 1, and so on and so forth all the way up to nk=1n_k = 1.

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.