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

Число $1\underbrace{33 \ldots3}_{k - \text{раз}}$ — простое, $k > 1$. Докажите, что $k^2-2k+3$ кратно 6. ( А. Васильев )

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

$p=1\underbrace{33 \ldots 3}_k=10^k+\underbrace{33 \ldots 3}_k=10^k+\cfrac{\overbrace{99 \ldots 9}^k}{3}=10^k+\cfrac{10^k-1}{3}=\cfrac{4 \cdot 10^k-1}{3}$.

Пусть $k=2n$, тогда $p=\cfrac{4 \cdot 10^{2n}-1}{3}=\cfrac{(2 \cdot 10^n-1)(2 \cdot 10^n+1)}{3}$, но $p$ - простое, значит $k$ не может быть четным.

Пусть $k=6n+1$, тогда $p=\cfrac{4 \cdot 10^{6n+1}-1}{3}=\cfrac{40 \cdot 10^{6n}-1}{3}=\cfrac{(39+1) \cdot 10^{6n}-1}{3}=\cfrac{39 \cdot 10^{6n}+10^{6n}-1}{3}$.

Докажем, что $10^{6n}\equiv 1\pmod{39}$. Так как $(10,39)=1$, то по h_теореме Эйлера@https://ru.wikipedia.org/wiki/Теорема_Эйлера_(теория_чисел)_h получим:

$10^{\phi(39)}\equiv 1\pmod{39}$

$10^{24}\equiv 1\pmod{39}$

$10^{6}\equiv 1\pmod{39}$

$10^{6n}\equiv 1\pmod{39}$.

Значит, $p \, \vdots \, 13$ , но $p$ - простое, значит $k$ не может быть $6n+1$.

Пусть $k=6n+3$, тогда получим:

$k^2-2k+3=(6n+3)^2-2(6n+3)+3=36 n^2+24 n+6 \, \vdots \, 6$.

Пусть $k=6n+5$, тогда получим:

$k^2-2k+3=(6n+5)^2-2(6n+5)+3=36 n^2+48 n+18 \, \vdots \, 6$.

Если $k=6a+1$

$k^2-2k+3=0(mod 6)$

Если $k=6a+3$

$k^2-2k+3=9-6+3=0(mod 6)$

Если $k=6a+5$

$k^2-2k+3=25-10+3=0(mod 6)$

Значит рассмотрим что произойдёт если k - чётное.

Тогда докажем что:

$133...3$ делится на $66..67$, где троек $2s$, а шестёрок $s-1$.

$666...7×200..0=133...340..0$, где нулей $s$ штук.

$133..3400...0-66..67=1333...3$, 4 превратится в 3, один из нулей заснёт 7 станет 3, а все другие 0 станут 6. Доказано