Maths Olympiad Prep

Library / /84 of 101

Number theory Difficulty 7.2 National olympiad, round 2 Prove it Estonia

How many integers kk are there for which 1kn1 \le k \le n and the sum 1+2++k1 + 2 + \dots + k is divisible by nn, if

a) n=20232024n = 2023^{2024};
b) n=20242023n = 2024^{2023}?

Solution

Note that 1+2++k=k(k+1)21+2+\dots+k = \frac{k(k+1)}{2}.

a) Since nn is odd, the number k(k+1)2\frac{k(k+1)}{2} is divisible by nn if and only if k(k+1)k(k+1) is divisible by nn.

Since 2023=71722023 = 7 \cdot 17^2, the number nn can be expressed as p1α1p2α2p_1^{\alpha_1} p_2^{\alpha_2}, where p1=7p_1 = 7, p2=17p_2 = 17 and α1,α2\alpha_1, \alpha_2 are positive integers. The number k(k+1)k(k+1) is divisible by nn iff k(k+1)k(k+1) is divisible by p1α1p_1^{\alpha_1} and p2α2p_2^{\alpha_2}. Since kk and k+1k+1 have no common factor, their product is divisible by piαip_i^{\alpha_i} iff one of the factors is divisible by this number. If kk is divisible by piαip_i^{\alpha_i} then k0(modpiαi)k \equiv 0 \pmod{p_i^{\alpha_i}}, if k+1k+1 is divisible by piαip_i^{\alpha_i} then k1(modpiαi)k \equiv -1 \pmod{p_i^{\alpha_i}}.

By Chinese Remainder Theorem the congruence system
{kd1(modp1α1)kd2(modp2α2) \begin{cases} k \equiv d_1 \pmod{p_1^{\alpha_1}} \\ k \equiv d_2 \pmod{p_2^{\alpha_2}} \end{cases}
has exactly one solution in the interval 1kp1α1p2α2=n1 \le k \le p_1^{\alpha_1} \cdot p_2^{\alpha_2} = n for any integers d1d_1 and d2d_2. The solution kk satisfies the conditions of the problem iff d1,d2{0,1}d_1, d_2 \in \{0, -1\}. There are 4 ways to choose such a vector of the right hand sides, each of them gives a different solution kk.

b) The number k(k+1)2\frac{k(k+1)}{2} is divisible by nn iff k(k+1)k(k+1) is divisible by 2n2n.

Since 2024=2311232024 = 2^3 \cdot 11 \cdot 23, the number nn can be expressed as 2β0q1β1q2β22^{\beta_0} q_1^{\beta_1} q_2^{\beta_2}, where q1=11q_1 = 11, q2=23q_2 = 23 and β0,β1,β2\beta_0, \beta_1, \beta_2 are positive integers. The number k(k+1)k(k+1) is divisible by 2n2n iff k(k+1)k(k+1) is divisible by 2β0+12^{\beta_0+1}, q1β1q_1^{\beta_1} and q2β2q_2^{\beta_2}. Since kk and k+1k+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)k(k+1) is divisible by 2β0+12^{\beta_0+1} iff k0(mod2β0+1)k \equiv 0 \pmod{2^{\beta_0+1}} or k1(mod2β0+1)k \equiv -1 \pmod{2^{\beta_0+1}}, and by qiβiq_i^{\beta_i} (i{1,2}i \in \{1, 2\}) iff k0(modqiβi)k \equiv 0 \pmod{q_i^{\beta_i}} or k1(modqiβi)k \equiv -1 \pmod{q_i^{\beta_i}}.

By Chinese Remainder Theorem the congruence system
{kd0(mod 2β0)kd1(mod q1β1)kd2(mod q2β2) \left\{ \begin{array}{ll} k \equiv d_0 & (\text{mod } 2^{\beta_0}) \\ k \equiv d_1 & (\text{mod } q_1^{\beta_1}) \\ k \equiv d_2 & (\text{mod } q_2^{\beta_2}) \end{array} \right.
has exactly one solution in the interval 1k2β0q1β1q2β2=n1 \le k \le 2^{\beta_0} \cdot q_1^{\beta_1} \cdot q_2^{\beta_2} = n for any integers d0,d1d_0, d_1 and d2d_2. The solution kk satisfies the conditions of the problem iff d0,d1,d2{0,1}d_0, d_1, d_2 \in \{0, -1\} and kd0(mod2β0+1)k \equiv d_0 \pmod{2^{\beta_0+1}}. Note that if d0=d1=d2=0d_0 = d_1 = d_2 = 0 then k=n0(mod2β0+1)k = n \ne 0 \pmod{2^{\beta_0+1}}, and if d0=d1=d2=1d_0 = d_1 = d_2 = -1 then k=n11(mod2β0+1)k = n - 1 \ne -1 \pmod{2^{\beta_0+1}}. Otherwise let di=1did'_i = -1 - d_i and define kk' as the solution of the congruence system
{kd0(mod 2β0)kd1(mod q1β1)kd2(mod q2β2) \left\{ \begin{array}{ll} k' \equiv d'_0 & (\text{mod } 2^{\beta_0}) \\ k' \equiv d'_1 & (\text{mod } q_1^{\beta_1}) \\ k' \equiv d'_2 & (\text{mod } q_2^{\beta_2}) \end{array} \right.
in the interval 1kn1 \le k' \le n. Note that k+k1(modn)k + k' \equiv -1 \pmod{n}; since 1k,kn21 \le k, k' \le n-2, we have 1<k+k<2n1-1 < k + k' < 2n-1, hence k+k=n1k + k' = n-1. Also note that kd0(mod2β0)k \equiv d_0 \pmod{2^{\beta_0}} means that exactly one of claims kd0(mod2β0+1)k \equiv d_0 \pmod{2^{\beta_0+1}} and kn+d0(mod2β0+1)k \equiv n+d_0 \pmod{2^{\beta_0+1}} is true, the same holds for kk'. It follows that exactly one of claims kd0(mod2β0+1)k \equiv d_0 \pmod{2^{\beta_0+1}} and kd0(mod2β0+1)k' \equiv d'_0 \pmod{2^{\beta_0+1}} is true. Indeed, if both were true then n1=k+kd0+d0=1(mod2β0+1)n-1 = k+k' \equiv d_0+d'_0 = -1 \pmod{2^{\beta_0+1}}, if neither of them were valid, then n1=k+k2n+d0+d0=2n1(mod2β0+1)n-1 = k+k' \equiv 2n+d_0+d'_0 = 2n-1 \pmod{2^{\beta_0+1}} – a contradiction in both cases. Consequently there are 822=3\frac{8-2}{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.