Maths Olympiad Prep

Library / /7 of 27

, 2015

Number theory Difficulty 4.7 AIME Prove it Singapore

Let n3n \ge 3 be an integer. Prove that there exist positive integers 2\ge 2, a1,a2,,ana_1, a_2, \dots, a_n, such that a1a2a^ian1(modai)a_1 a_2 \cdots \hat{a}_i \cdots a_n \equiv 1 \pmod{a_i}, for i=1,,ni = 1, \dots, n. Here a^i\hat{a}_i means the term aia_i is omitted.

Solution

Let a1=2a_1 = 2, a2=3a_2 = 3. For i=3,,n1i = 3, \dots, n-1, let ai=a1a2ai1+1a_i = a_1 a_2 \cdots a_{i-1} + 1. Let an=a1a2an11a_n = a_1 a_2 \cdots a_{n-1} - 1. Clearly, a1a2an11(modan)a_1 a_2 \cdots a_{n-1} \equiv 1 \pmod{a_n}. Also ai+1ai+2an11(modai)a_{i+1} \equiv a_{i+2} \equiv \cdots \equiv a_{n-1} \equiv 1 \pmod{a_i}. For i=1,,n1i = 1, \dots, n-1, we have
a1a2a^ian=(a1ai1)(ai+1an1)an(1)(1)(1)1(modai). a_1 a_2 \cdots \hat{a}_i \cdots a_n = (a_1 \cdots a_{i-1})(a_{i+1} \cdots a_{n-1})a_n \equiv (-1)(-1)(-1) \equiv 1 \pmod{a_i}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.