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

Даны простое число $p$ и натуральные $k$ и $r$, причем $r < p$. Известно, что $p^p + 1$ делится на $pk + r$. Докажите, что $k$ делится на $r$. ( Ануарбеков Т. )

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

Комментарии от администратора Комментарии от администратора №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$