Maths Olympiad Prep

Library / /11 of 19

Number theory Difficulty 6.0 National Olympiad Prove it New Zealand

Problem:
Determine all positive integers nn less than 20242024 such that for all positive integers xx, the greatest common divisor of 9x+19x + 1 and nx+1nx + 1 is 11.

Solution

Solution:
Let m=n9m = n - 9 and for the sake of contradiction assume mm has a prime factor pp with p3p \neq 3. Express p=9q+rp = 9q + r where 0r80 \leq r \leq 8 (rr is the remainder when pp is divided by 99 and qq may be zero). Since gcd(9,p)=1\gcd(9, p) = 1 we must have r=1,2,4,5,7r = 1, 2, 4, 5, 7 or 88. For each of these possibilities we will use a different choice for xx to get our contradiction.

if r=1r = 1 then choose x=qx = q so that (9x+1)=9q+1=p(9x + 1) = 9q + 1 = p

if r=2r = 2 then choose x=5q+1x = 5q + 1 so that (9x+1)=45q+10=5p(9x + 1) = 45q + 10 = 5p

if r=4r = 4 then choose x=7q+3x = 7q + 3 so that (9x+1)=63q+28=7p(9x + 1) = 63q + 28 = 7p

if r=5r = 5 then choose x=2q+1x = 2q + 1 so that (9x+1)=18q+10=2p(9x + 1) = 18q + 10 = 2p

if r=7r = 7 then choose x=4q+3x = 4q + 3 so that (9x+1)=36q+28=4p(9x + 1) = 36q + 28 = 4p

if r=8r = 8 then choose x=8q+7x = 8q + 7 so that (9x+1)=72q+64=8p(9x + 1) = 72q + 64 = 8p

In any we can choose xx so that (9x+1)(9x + 1) is a multiple of pp. For this particular value of xx we have
(nx+1)=mx+(9x+1),(n x + 1) = m x + (9 x + 1),
and so (nx+1)(n x + 1) is a multiple of pp too (recall pmp \mid m). Therefore pp would be a common factor of (9x+1)(9x + 1) and (nx+1)(n x + 1). This is a contradiction so no such pp can exist.

So m=n9m = n - 9 cannot have any prime factors other than 33. Hence m=3km = 3^{k} or m=3km = -3^{k} for some integer k0k \geq 0. i.e.
n=9+m=9+3k or 93kn = 9 + m = 9 + 3^{k} \text{ or } 9 - 3^{k}
The positive integers of this form, less than 20242024 are: 6,8,10,12,18,36,90,252,7386, 8, 10, 12, 18, 36, 90, 252, 738.

To show all these work, we now assume n=9±3kn = 9 \pm 3^{k} for some integer k0k \geq 0, and let g=gcd(9x+1,nx+1)g = \gcd(9x + 1, nx + 1). Since 9x+19x + 1 is not a multiple of 33, we cannot have gg being a multiple of 33. However
g(nx+1)(9x+1)=±3k.g \mid (n x + 1) - (9 x + 1) = \pm 3^{k}.
The only divisors of 3k3^{k} which are not a multiple of 33 are 11 and 1-1. Therefore g=1g = 1 whenever n=9±3kn = 9 \pm 3^{k}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.