Республиканская олимпиада по математике, 2002 год, 11 класс

Докажите, что существует множество $A$ состоящее из 2002 различных натуральных чисел, удовлетворяющее условию: для каждого $a\in A$ произведение всех чисел из $A$, кроме $a$, при делении на $a$ дает остаток 1.

Комментарий/решение

Обобщим: Возьмем такую последовательность получаемую из первых двух $a_{1}=2, a_2=3$ дальше умножать их и добавлять $1$ то есть $a_{n-1} = \left( \prod \limits_{i=1}^{n-2}{a_i} \right)+1$ и последний $a_{n} = \left( \prod \limits_{i=1}^{n-1}{a_i} \right)-1$ тогда набор из таких последовательностей подходит.

Доказательство : пусть $P=a_1 \cdot a_2 \cdot a_3 \cdot ... a_{n-2} \cdot a_{n-1} \cdot a_{n}$ тогда в силу построения

$$\dfrac{P}{a_{k}}= (a_1 \cdot a_2 \cdot ... \cdot a_{k-1}) \cdot (a_{k+1} \cdot ...a_{n-1}) \cdot a_{n} \equiv (-1) \cdot (1) \cdot (-1) \equiv 1 \ \mod \ a_{k}$$