Singapur, 2015

Number theory Difficulty 4.7 AIME Prove it Singapore

Let $n \ge 3$ be an integer. Prove that there exist positive integers $\ge 2$ , $a_1, a_2, \dots, a_n$ , such that $a_1 a_2 \cdots \hat{a}_i \cdots a_n \equiv 1 \pmod{a_i}$ , for $i = 1, \dots, n$ . Here $\hat{a}_i$ means the term $a_i$ is omitted.

Solution

Let $a_1 = 2$ , $a_2 = 3$ . For $i = 3, \dots, n-1$ , let $a_i = a_1 a_2 \cdots a_{i-1} + 1$ . Let $a_n = a_1 a_2 \cdots a_{n-1} - 1$ . Clearly, $a_1 a_2 \cdots a_{n-1} \equiv 1 \pmod{a_n}$ . Also $a_{i+1} \equiv a_{i+2} \equiv \cdots \equiv a_{n-1} \equiv 1 \pmod{a_i}$ . For $i = 1, \dots, n-1$ , we have
$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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.