Maths Olympiad Prep

Library / /14 of 16

, 2024

Number theory Difficulty 6.7 National olympiad Prove it Saudi Arabia

On the board, there are written numbers 1,2,3,,202320241, 2, 3, \dots, 2023^{2024}. At each step, it is allowed to erase any two numbers a,ba, b on the board and then replace them with gcd(2024ab,a2+254ab+b2)\gcd(2024ab, a^2 + 254ab + b^2), keep doing this until there is only one number xx left. Find all possible values of xx.

On the board, there are written numbers 1, 2, 3, ..., 202320242023^{2024}. At each step, it is allowed to erase any two numbers a,ba, b on the board and then replace them with gcd(2024ab,a2+254ab+b2)\text{gcd}(2024ab, a^2 + 254ab + b^2). Keep doing this until there is only one number xx left, find all possible values of xx.

Solution

Let f(a,b)=gcd(2024ab,a2+254ab+b2)f(a, b) = \text{gcd}(2024ab, a^2 + 254ab + b^2) then for 2 numbers a,ba, b on the board, the new number generated will be f(a,b)f(a, b). We consider some cases:
* If a,ba, b are same parity then f(a,b)f(a, b) is even.
* If a,ba, b are different from parity then f(a,b)f(a, b) is odd.
This means that the number of odd numbers either remains the same or decreases by 2 units; but initially, there are odd numbers, so the final number xx must be odd. Suppose that x>1x > 1, let pp be some prime divisor of xx.
Note that
254=1123+1 and 2024=231123. 254 = 11 \cdot 23 + 1 \text{ and } 2024 = 2^3 \cdot 11 \cdot 23.
If p=11p = 11, since 11gcd(2024ab,a2+254ab+b2)11|\text{gcd}(2024ab, a^2 + 254ab + b^2) then 11a2+ab+b211|a^2 + ab + b^2. Similarly, if p=23p = 23 then there is also 23a2+ab+b223|a^2 + ab + b^2. We have the following familiar lemma derived from Fermat's little theorem or quadratic residue:
Lemma. If pp is a prime of form 3k+23k + 2 and pa2+ab+b2p|a^2 + ab + b^2 then pa,bp|a, b.
Since 11 has the form 3k+23k + 2, according to the above lemma, one can get 11a,b11|a, b. Continuing like that, the previous numbers on the board that generated a,ba, b also be divisible by 11, making all the original numbers divisible by 11, contradiction. Similarly for the case p=23p = 23.
Finally, if p11,23p \neq 11, 23 then pab,pa2+506ab+b2p|ab, p|a^2 + 506ab + b^2 entails pab,pa2+b2p|ab, p|a^2 + b^2. Obviously from pabp|ab, we get that pp is a divisor of one of aa or bb, but pa2+b2p|a^2 + b^2 then pa,bp|a, b. We get the similar contradiction as the above argument.
Therefore xx is odd and has no odd prime divisors, proving that x=1x = 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.