IX математическая олимпиада «Шелковый путь», 2010 год

Обозначим $N = 2010!+1$. Докажите, что
a) $N$ не делится на $4021$;
b) $N$ не делится на $2027, 2029, 2039$;
c) $N$ имеет простой делитель, больший $2050$.

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

a) Заметим, что $4021 \in \mathbb{P}$. Значит по теореме Вильсона $4020! + 1 \equiv 0 \pmod {4021}$. Пусть $4021 \, | \, N$. Заметим, что $4020! \equiv (2010!)^2 \pmod {4021}$. Тогда $1 \equiv (2010!)^2 \equiv 4020! \equiv -1 \pmod {4021}$, что невозможно.

б) Приведем доказательство для $2027$, для остальных чисел оно аналогично. Заметим, что $2027 \in \mathbb{P}$, тогда $2026! \equiv -1 \pmod {2027}$. Если $2010! \equiv -1 \pmod {2027}$, то $2011 \cdot 2012 \cdot .... \cdot 2026 \equiv 16! \equiv 1 \pmod {2027}$. Значит $16!$ должен быть квадратичным вычетом по модулю $2027$. Покажем, что это не так. Воспользуемся для этого символом Лежандра: $$ (\frac {16!}{2027}) = (\frac {2 \cdot 5 \cdot 11 \cdot 13 }{2027}) = (\frac {2}{2027}) \cdot (\frac {5}{2027}) \cdot (\frac {11}{2027}) \cdot (\frac {13}{2027})$$ Воспользуемся квадратичным законом взаимности и получим: $$ (\frac{2}{2027}) = -1$$ $$ (\frac{5}{2027}) = (\frac{2027}{5}) = (\frac{2}{5}) = -1$$ $$ (\frac{11}{2027}) = -(\frac{2027}{11}) = (\frac{-3}{11}) = (\frac{2}{3}) = -1$$ $$ (\frac{13}{2027}) = (\frac{2027}{13}) = (\frac{12}{13}) = (\frac{3}{13}) = (\frac{1}{3}) = 1$$ Отсюда $16!$ не квадратичный вычет по модулю $2027$.

в) Заметим, что в каноническом разложении $N$ присутствуют простые числа большие $2010$. Если у $N$ нет простого делителя большего чем 2050, то $N$ это степень $2011$. Так как между $2010$ и $2050$ простыми числами являются только $2011, 2017, 2027, 2029, 2039$. Мы уже показали что $N$ не делится на $2027, 2029, 2039$. Заметим, что если $2010! + 1 \equiv 0 \pmod{2017} \Rightarrow 6! = 720 \equiv 1 \pmod {2017}$, что невозможно. Значит $N = (p-1)! + 1 = p^m, \, p=2011$. Тогда $q = \frac{p-1}{2} < p-2 \Rightarrow q \, | \, (p-2)!$ Тогда $q \, | \, (p-2)! = \frac{p^m - 1}{p - 1} = p^{m-1} + ... + 1$. Заметим, что $p \equiv 1 \pmod q \Rightarrow q \, | \, m$. Если $m > q \Rightarrow (p-1)!+1=p^m \geq p^{2q} = p^{p-1} > (p-1)! + 1$. Тогда $m = q, \, (p-1)!+1=p^{\frac{p-1}{2}}$. Заменяя $p=2011$ получаем, что $2010! + 1 = 2011^{1005} \equiv (-1)^{1005} \equiv -1 \equiv 1 \pmod{4}$, что невозможно. Значит у $N$ есть простой делитель больший $2050$.