Республиканская олимпиада по математике, 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. Доказано

Если k=6a+1=>$k^2\equiv 1 \pmod 6; -2k \equiv -2 \pmod 6\Longrightarrow k^2-2k+3\equiv 1-2+3\equiv 2 \pmod 6$

$$3p=4\cdot 10^k-1 \quad k^2-2k+3=(k-1)^2+2$$

Достаточно показать что $k \not\equiv 1 \pmod 3, ~ k \not\equiv 0 \pmod 2$. Для $k \equiv 0 \pmod 2$ противоречие:

$$3p=(2\cdot 10^{\frac{k}{2}}-1)(2 \cdot 10^{\frac{k}{2}}+1) \Longleftrightarrow 1<\dfrac{p}{2\cdot 10^{\frac{k}{2}}-1}=\dfrac{2 \cdot 10^{\frac{k}{2}}+1}{3} \in \mathbb{N},\quad 1<2 \cdot 10^{\frac{k}{2}}-1<p$$

Для $k \equiv 1 \pmod 3$ тоже противоречие:

$$4\cdot 10^k-1 \equiv 4\cdot 10\cdot (-27)^{\frac{k-1}{3}} -1 \equiv 40-1\equiv 0\pmod {13}$$

используя что $k-1 \equiv 0 \pmod 2$.

Следовательно $(k-1)^2+2 \equiv 0 \pmod 6$, что требовалось $\square$.