Maths Olympiad Prep

Library / /8 of 18

Number theory Difficulty 6.1 National olympiad Prove it Belarus

After division of a positive integer nn by 2929, 4141, and 5959 one has three nonzero remainders such that their sum is equal to nn.
Find all possible values of nn.

Solution

Let, by condition,
n=29q1+r1=41q2+r2=59q3+r3=r1+r2+r3, n = 29q_1 + r_1 = 41q_2 + r_2 = 59q_3 + r_3 = r_1 + r_2 + r_3,
r1<29r_1 < 29, r2<41r_2 < 41, r3<59r_3 < 59. From these inequalities it follows that 59q3=r1+r228+40=6859q_3 = r_1 + r_2 \le 28 + 40 = 68, so q3=1q_3 = 1. Then
r1+r2=59.(1) r_1 + r_2 = 59. \quad (1)

Further, 41q2=r1+r328+58=8641q_2 = r_1 + r_3 \le 28 + 58 = 86, so q22q_2 \le 2. Consider two cases:
1)q2=1.Thenr1+r3=41.(2) 1) \quad q_2 = 1. \quad \text{Then} \qquad r_1 + r_3 = 41. \qquad (2)
From (1) and (2) it follows that
100=59+41=r1+r2+r1+r3=n+r1=29q1+2r1, 100 = 59 + 41 = r_1 + r_2 + r_1 + r_3 = n + r_1 = 29q_1 + 2r_1,
i.e., 29q1+2r1=10029q_1 + 2r_1 = 100. Hence q1q_1 is even and 29q1<10029q_1 < 100, so q1=2q_1 = 2. Then r1=12(100229)=21r_1 = \frac{1}{2}(100 - 2 \cdot 29) = 21, r2=38r_2 = 38, r3=20r_3 = 20, and n=21+38+20=79n = 21 + 38 + 20 = 79, which satisfies the problem condition.

2) q2=2q_2 = 2. Then
r1+r3=nr2=41q2=82.(3) r_1 + r_3 = n - r_2 = 41q_2 = 82. \qquad (3)
From (1) and (3) it follows that 29q1+2r1=14129q_1 + 2r_1 = 141, so q1q_1 is odd and 29q1<14129q_1 < 141. Hence either q1=1q_1 = 1 or q1=3q_1 = 3. If q1=1q_1 = 1, then 2r1=1222r_1 = 122, i.e., r1=61r_1 = 61, a contradiction. If q1=3q_1 = 3, then r1=27r_1 = 27, r2=32r_2 = 32, r3=55r_3 = 55, and n=27+32+55=114n = 27 + 32 + 55 = 114, which satisfies the problem condition.

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.