Республиканская олимпиада по математике, 2020 год, 9 класс
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1. Утверждение задачи, очевидно, верно при $r = 1$. Пусть $r > 1$, тогда $p \ge r + 1 \ge 3$. Введем обозначения: \[A = \dfrac{p^p + 1}{p + 1}, \ d = \text{НОД}(A, \ pk + r), \ x = \dfrac{pk + r}{d}.\] Пусть $q$ — произвольный простой делитель $A$. Если $q \ | \ p + 1$, то \[0 \equiv A \equiv p^{p-1} - p^{p-2} + \ldots - p + 1 \equiv p \pmod{q}\] --- противоречие. В частности, $q \ne 2$. Пусть $\alpha$ — показатель числа $p$ по модулю $q$. \[p^p \equiv -1 \pmod{q} \implies p^{2p} \equiv 1 \pmod{q}.\] По свойству показателя имеем, что $\alpha \ | \ 2p$ и $\alpha \ne p$. Но так как числа $p + 1$ и $p - 1$ не делятся на $q$, то $\alpha = 2p$. По малой теореме Ферма, $p^{q-1} \equiv 1 \pmod{q}$, следовательно, по свойству показателя, $2p \ | \ q - 1$. Значит, любой простой делитель $q$ числа $A$ имеет вид $q \equiv 1 \pmod{p}$. Так как $d \ | \ A$, то $d \equiv 1 \pmod{p}$. Из условия имеем, что $x \ | \ p + 1$, а следовательно $x \le p + 1 < p + r$ и из равенства $pk + r = dx$ получаем, что $r \equiv x \pmod{p}$. Так как $1 < r < p$, то $x = r$. Значит, $pk + r = dr$, откуда $r \ | \ k$, что и требовалось доказать.
Если $p=2,$ то $p^p+1=2^2+1=5,$ откуда
$2k+r=pk+r=1$ или $2k+r=pk+r=5,$ тогда $(k,r)=(2,1).$
Далее $p>2.$
Рассмотрим простой делитель $q$ числа в $p^p+1.$ Очевидно, что $q\ne p.$
Заметим, что $$p^p\equiv -1\pmod q\implies p^{2p}\equiv 1\pmod q$$
По Малой Теореме Ферма: $$p^{q-1}\equiv 1\pmod q$$
Пусть $d-$показатель числа $p$ по модулю $q$: $$p^d\equiv 1\pmod q$$ Тогда $d\mid 2p$ и $d\mid q-1.$ Значит $d\in\{1,2,p,2p \}$
$\\$
Лемма 1: Если $q>p,$ то $q\equiv 1 \pmod p.$
Доказательство:
Если $d\in\{1,2\},$ то $q\mid p^2-1=(p-1)(p+1),$ значит либо $q\mid p-1,$ либо $q\mid p+1,$ откуда $p+1\ge q>p\implies p+1=q,$ но тогда $2\mid p+1=q>2,$ что невозможно.
Тогда $d\in\{p,2p\}\implies p\mid d\mid q-1\implies q\equiv 1\pmod p.$ $\blacksquare$
$\\$
Лемма 2: Если $q<p,$ то $q\mid p+1$
Доказательство:
Если $d\in\{p,2p\}\implies p\mid d\mid q-1\implies p>q-1\ge p,$ что невозможно.
Значит $d\in\{1,2\}\implies d\mid 2\implies q\mid p^2-1=(p-1)(p+1).$
Тогда либо $q\mid p+1,$ либо $q\mid p-1.$ Если $q\mid p+1,$ то Лемма 2 доказана.
Если $q\mid p-1,$ то $$-1\equiv p^p\equiv 1^p\equiv 1\pmod q\implies 2\equiv 0\pmod q,$$ значит $q=2\mid p+1.$ $\blacksquare$
Заметим, что $1<pk+r$. Пусть $pk+r=q_1^{a_1}\ldots q_s^{a_s}-$каноническое разложение числа. Пусть $$\large{\prod\limits_{\forall q_i>p}q_i^{a_i}=A,\quad\prod\limits_{\forall q_j<p}q_j^{a_j}=B.}$$
Тогда $pk+r=A\cdot B.$
Из Леммы 1: $q_i\equiv 1\pmod p,\forall q_i>p$ $$\implies A=\prod\limits_{\forall q_i>p}q_i^{a_i}\equiv 1\pmod p.$$
Так как $p-$нечетное, то $$p^p+1=(p+1)(p^{p-1}-p^{p-2}+\ldots -p+1)=(p+1)\cdot X.$$
Легко понять, что $$X\equiv p^{p-1}-p^{p-2}+\ldots -p+1\equiv 1+1\ldots +1+1\equiv p\pmod{p+1}$$
откуда $gcd(X,p+1)=1.$
Из Леммы 2: $q_j\mid p+1,\forall q_j<p.$ Заметим, что $q_j^{a_j}\mid p^p+1=(p+1)\cdot X,$ но так как $gcd(X,p+1)=1\implies q_j^{a_j}\mid p+1,\forall q_j<p$ $$\implies B=\prod\limits_{\forall q_j<p}q_j^{a_j}\mid p+1.$$
Тогда $B\le p+1.$ Если $B=p+1$ $$\implies pk+r=A\cdot B\equiv 1\cdot 1=1\pmod p,$$
откуда $r=1\mid k.$
Если $B<p+1\implies B<p,$ ведь $gcd(B,p)=1$ $$\implies pk+r=A\cdot B\equiv 1\cdot B\equiv B\pmod p $$
откуда $r=B,$ ведь $1\le r,B<p\implies r=B\mid A\cdot B=pk+r,$
значит $r\mid pk,$ но так как $gcd(p,r)=1\implies r\mid k.\quad\square$
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.