Number theoryDifficulty 7.2National olympiad, round 2Prove itEstonia
How many integers k are there for which 1≤k≤n and the sum 1+2+⋯+k is divisible by n, if
a) n=20232024; b) n=20242023?
Solution
Note that 1+2+⋯+k=2k(k+1).
a) Since n is odd, the number 2k(k+1) is divisible by n if and only if k(k+1) is divisible by n.
Since 2023=7⋅172, the number n can be expressed as p1α1p2α2, where p1=7, p2=17 and α1,α2 are positive integers. The number k(k+1) is divisible by n iff k(k+1) is divisible by p1α1 and p2α2. Since k and k+1 have no common factor, their product is divisible by piαi iff one of the factors is divisible by this number. If k is divisible by piαi then k≡0(modpiαi), if k+1 is divisible by piαi then k≡−1(modpiαi).
By Chinese Remainder Theorem the congruence system {k≡d1(modp1α1)k≡d2(modp2α2) has exactly one solution in the interval 1≤k≤p1α1⋅p2α2=n for any integers d1 and d2. The solution k satisfies the conditions of the problem iff d1,d2∈{0,−1}. There are 4 ways to choose such a vector of the right hand sides, each of them gives a different solution k.
b) The number 2k(k+1) is divisible by n iff k(k+1) is divisible by 2n.
Since 2024=23⋅11⋅23, the number n can be expressed as 2β0q1β1q2β2, where q1=11, q2=23 and β0,β1,β2 are positive integers. The number k(k+1) is divisible by 2n iff k(k+1) is divisible by 2β0+1, q1β1 and q2β2. Since k and k+1 have no common factor, their product is divisible by each of the powers of the primes iff one of the factors is divisible by this number. So k(k+1) is divisible by 2β0+1 iff k≡0(mod2β0+1) or k≡−1(mod2β0+1), and by qiβi (i∈{1,2}) iff k≡0(modqiβi) or k≡−1(modqiβi).
By Chinese Remainder Theorem the congruence system ⎩⎨⎧k≡d0k≡d1k≡d2(mod 2β0)(mod q1β1)(mod q2β2) has exactly one solution in the interval 1≤k≤2β0⋅q1β1⋅q2β2=n for any integers d0,d1 and d2. The solution k satisfies the conditions of the problem iff d0,d1,d2∈{0,−1} and k≡d0(mod2β0+1). Note that if d0=d1=d2=0 then k=n=0(mod2β0+1), and if d0=d1=d2=−1 then k=n−1=−1(mod2β0+1). Otherwise let di′=−1−di and define k′ as the solution of the congruence system ⎩⎨⎧k′≡d0′k′≡d1′k′≡d2′(mod 2β0)(mod q1β1)(mod q2β2) in the interval 1≤k′≤n. Note that k+k′≡−1(modn); since 1≤k,k′≤n−2, we have −1<k+k′<2n−1, hence k+k′=n−1. Also note that k≡d0(mod2β0) means that exactly one of claims k≡d0(mod2β0+1) and k≡n+d0(mod2β0+1) is true, the same holds for k′. It follows that exactly one of claims k≡d0(mod2β0+1) and k′≡d0′(mod2β0+1) is true. Indeed, if both were true then n−1=k+k′≡d0+d0′=−1(mod2β0+1), if neither of them were valid, then n−1=k+k′≡2n+d0+d0′=2n−1(mod2β0+1) – a contradiction in both cases. Consequently there are 28−2=3 integers satisfying the conditions.
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.