Maths Olympiad Prep

Library / /16 of 27

Number theory Difficulty 5.8 AIME, harder Prove it Austria

Determine the maximal number of consecutive positive integers such that each of these integers has a common divisor with 20242024 greater than 11.

Solution

We observe that 2024=2311232024 = 2^3 \cdot 11 \cdot 23. An integer has a common divisor greater than 11 with 20242024 if and only if it is divisible by 22, 1111 or 2323.
Let NN be the desired maximal number. Only each 1111th integer is divisible by 1111. That means that if zz is divisible by 1111, then z+1,z+2,,z+10z+1, z+2, \dots, z+10 are not divisible by 1111. Analogously, 2323 divides only every 2323rd integer. Six consecutive integers contain exactly three odd numbers. At most one of them is divisible by 1111 and at most one of them is divisible by 2323. This shows that N5N \le 5.

Now, we try to find five consecutive integers n,n+1,n+2,n+3,n+4n, n+1, n+2, n+3, n+4 that have a common divisor greater than 11 with 20242024.
We can do that in the following way:

nevenn+1divisible by 11n+2evenn+3divisible by 23n+4even \begin{array}{c|l} n & \text{even} \\ n + 1 & \text{divisible by } 11 \\ n + 2 & \text{even} \\ n + 3 & \text{divisible by } 23 \\ n + 4 & \text{even} \end{array}

That means that we want n+1=11kn + 1 = 11k and n+3=23ln + 3 = 23l with kk and ll odd. If we subtract the second equation from the first, we get
2=23l11k=l+11(2lk). \begin{aligned} 2 &= 23l - 11k \\ &= l + 11(2l - k). \end{aligned}
We obtain l2(mod11)l \equiv 2 \pmod{11}. We see that l=13l = 13 works, since we get n+3=23l=299n + 3 = 23l = 299 and therefore n=296n = 296 and the five consecutive integers 296,297,298,299,300296, 297, 298, 299, 300, which have the desired property.
Therefore, N=5N = 5.

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.