Maths Olympiad Prep

Track / Stage 6 / 318 of 400 #1798 of 2444

Problem 1798

National Olympiad, first round
Number theory Difficulty 6.7 Prove it Russia — Regional Round · Russia

A triple of positive integers (a,b,c)(a, b, c) is called quadratic if a,b,ca, b, c is a nondecreasing arithmetic progression, gcd(b,a)=gcd(b,c)=1\gcd(b, a) = \gcd(b, c) = 1, and abcabc is a perfect square. Prove that for any quadratic triple, there exists some other quadratic triple containing at least one number from the first triple.

Назовем тройку натуральных чисел (a,b,c)(a, b, c) квадратной, если они образуют неубывающую арифметическую прогрессию (именно в таком порядке), число bb взаимно просто с каждым из чисел aa и cc, а число abcabc является точным квадратом. Докажите, что для любой квадратной тройки найдётся другая квадратная тройка, имеющая с ней хотя бы одно общее число.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Если b=1b = 1, то a=c=1a = c = 1, и в качестве другой тройки можно выбрать (1,25,49)(1, 25, 49). Если же b1b \neq 1, то из взаимной простоты разность прогрессии dd не может оказаться нулевой. Тогда без ограничения общности d=ba=cb>0d = b - a = c - b > 0.

Поскольку bb взаимно просто как с aa, так и с cc, то оно взаимно просто как с acac. Далее, произведение взаимно простых чисел acac и bb является квадратом, поэтому и каждое из них — также квадрат, то есть b=f2b = f^2, ac=m2=(bd)(b+d)=b2d2ac = m^2 = (b-d)(b+d) = b^2 - d^2 для некоторых натуральных ff и mm. При этом mdm \neq d, так как в противном случае b2=m2+d2=2m2b^2 = m^2 + d^2 = 2m^2, что невозможно.

Рассмотрим теперь тройку (bm,b,b+m)(b-m, b, b+m). Ее члены образуют арифметическую прогрессию, являются натуральными числами (так как b2m2=d2>0b^2 - m^2 = d^2 > 0), и их произведение (bm)b(b+m)=f2(b2m2)=(df)2(b-m)b(b+m) = f^2(b^2 - m^2) = (df)^2 является квадратом. Кроме того, gcd(b,m2)=gcd(b,ac)=1\gcd(b, m^2) = \gcd(b, ac) = 1, откуда 1=gcd(b,m)=gcd(b,bm)=gcd(b,b+m)1 = \gcd(b, m) = \gcd(b, b-m) = \gcd(b, b+m). Значит, эта тройка — квадратная, она имеет общий элемент bb с исходной и отлична от нее (ибо bmbdb-m \neq b-d), что и требовалось.

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