Problem OM 75.1.2

% NumberTheory, Algebra, DiophantineEquations, Primes

\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{fancyhdr}
\usepackage{lastpage} 
\usepackage{polski}
\usepackage{float}
\usepackage{fontspec}
\setmainfont{Linux Libertine O}

\usepackage[left=2cm, top=2cm, right=2cm, bottom=1cm, includeheadfoot, headheight=50pt, a4paper]{geometry}

\newcommand{\Name}{Hostek}                
\newcommand{\Email}{your.email@example.com}   
\newcommand{\ProblemNumber}{LXXV OM, etap 1, zadanie 2}               

\pagestyle{fancy}
\fancyhf{} 
\fancyhead[L]{\Name \\ \Email}
\fancyhead[C]{\ProblemNumber}
\fancyfoot[C]{\thepage/\pageref{LastPage}}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\begin{document}
\fontsize{16}{17}\selectfont

\section*{Problem Statement}
Wyznaczyć wszystkie dodatnie liczby całkowite $x$, dla których liczba
$$1+x+x^2+x^3+x^4+x^5+x^6+x^7$$
jest potęgą liczby pierwszej.
\bigskip

\noindent\textbf{Solution:}

Najpierw przekształćmy nasze wyrażenie:
$$1+x+x^2+x^3+x^4+x^5+x^6+x^7=$$
$$1+x+x^2+x^3+x^4(1+x+x^2+x^3)=$$
$$(x^3+x^2+x+1)(x^4+1)=$$
$$(x+1)(x^2+1)(x^4+1)$$

Okej, więc chcemy, żeby to było potęgą liczby pierwszej.

Najpierw rozpatrzmy przypadek, że $x+1=p$, a następnie ogólniejszy przypadek $x+1=p^k,k\in\mathbb{Z}$.

Podstawiając $x = p - 1$ otrzymujemy:
$$p(p^2-2p+2)(\ldots)$$
$\rightarrow$ więc chcemy, żeby to było potęgą liczby pierwszej.

Zauważmy, że 
$f(p)=p^2-2p+2$ nie ma miejsc zerowych.
$$\Delta=4-4\cdot2=-4$$
$$x_w=1, y_w = f(x_w) = 1$$

Dobrze, więc chcemy, żeby to było potęgą liczby pierwszej $p$.

Czyli chcemy przyrównać: $f(p) = p^{k_1}, k_1\in\mathbb{Z}_{\geq0}$.

Zauważmy, że funkcja postaci $x^{k_1}$ zawsze przechodzi przez punkt $A=(1,1)$

Ale czy mają coś więcej wspólnego poza tym punktem?

Patrzymy jedynie na $x > 0$, a zatem udowodnimy, że wykresy funkcji $f(x)$ i $g(x) = x^{k_1}$ po dotknięciu się w punkcie $A$ potem już nigdy się nie zetkną, dla $k_1 \geq 2$.

Dla $k_1 = 2$ jest to oczywiste ze względu na to, że funkcja \\$f(x)-g(x)=-2x+2$ jest funkcją liniową więc ma jedno miejsce zerowe.

Żeby dowieść, że dla $k_1 > 2$ też ma dokładnie jedno miejsce zerowe (przypominam, że rozważamy $x>0$) zauważmy, że:
$$h(x) = f(x)-g(x)=0 \Leftrightarrow -x^{k_1} + x^2 - 2x + 2 = 0$$
gdy $x \rightarrow +\infty$ dla $k_1 > 2$ wartość $-x^{k_1}$ dominuje, więc $h(x) \rightarrow -\infty$

Monotoniczność $h(x)$:

pochodna: $$h^\prime(x)=2x-2-k_1x^{k_1-1}$$

\begin{table}[H]
    \centering
    \renewcommand{\arraystretch}{1.7}
    \fontsize{15}{15}\selectfont
    \begin{tabular}{|c|c|p{8cm}|}
        \hline
        \textbf{Zakres $x$} & \textbf{Wartość $h'(x)$} & \textbf{Uzasadnienie} \\
        \hline
        $x \in (0,1)$ & $h'(x) < 0$ & Widać, że pochodna jest ujemna. \\
        \hline
        $x = 1$ & $h'(1) = -k_1 < 0$ & Dla $x=1$: $h^\prime(1)=2 - 2 - k_1 = -k_1$. \\
        \hline
        $x > 1$ & $h'(x) < 0$ & Składnik $-k_1 x^{k_1 - 1}$ dominuje, więc pochodna jest ujemna. \\
        \hline
    \end{tabular}
\end{table}

Ponieważ $h(x)$ jest ciągła, ściśle malejąca, przyjmuje wartość 0 tylko raz (w $x=1$) oraz zmienia znak z dodatniego na ujemny, to jedyne rozwiązanie $h(x) = 0$ jest dla $x=1$.

Więc, skoro dla $k_1 \geq 2$ mają tylko jeden punkt wspólny $A = (1, 1)$ to wystarczy sprawdzić co się stanie gdy $f(p)=1$ oraz $f(p)=p$. (Przy czym od razu widać, że $f(p) = 1 \Rightarrow p = 1$)

$$f(p)=1$$
$$p^2-2p+2=1$$
$$p^2-2p+1=0$$
$$(p-1)^2=0$$
$$p=1$$

$1$ nie jest liczbą pierwszą.

$$f(p)=p$$
$$p^2-2p+2=p$$
$$p^2-3p+2=0$$
$$(p-1)(p-2)=0$$
$$p=1 \vee p=2$$

Jako iż $p=2$ jest liczbą pierwszą, więc potencjalnie daje to nam dobrą odpowiedź. $x=p-1 \rightarrow x=1$

Sprawdźmy podstawiając do oryginalnego równania czy jest to dobre. Otrzymujemy $8 = 2^3$ co jak najbardziej jest dobre!

Dlatego $x=1$ jest jedną z odpowiedzi.

Zajmijmy się teraz przypadkiem, gdy $x=p^k-1,\ k > 1$.

Podstawiając do tamtego wcześniejszego wyrażenia $x=p^k-1$ otrzymujemy: $p^k(p^{2k}-2p^k+2)(\ldots)$, więc trzeba zapewnić: $p^{2k}-2p^k+2=p^m$, gdzie $m\in\mathbb{Z} \wedge m < 2k$ ($m<2k$ można udowodnić analogicznie jak powyżej dowodziliśmy, że $k_1 < 2$).

Rozpatrzmy dwa przypadki: 1. $m\leq k$ 2. $m>k$

Najpierw rozpatrzmy drugi przypadek:

$$p^{2k}-2p^k+2=p^m$$
$$p^{2k}-2p^k-p^m+2=0$$
$$p^{k}(p^k-2-p^{m-k})=-2$$

Żeby taki iloczyn był ujemny to jeden z czynników musi być ujemny. Wiemy, że $p^k > 0$ więc to ten drugi ma być ujemny.

$$p^k-2-p^{m-k} < 0$$
$$p^k < p^{m-k} + 2$$

Ale skoro: $m < 2k$ to $m - k < k \Rightarrow p^{m-k} < p^k $, więc dalej:

$$p^{m-k} < p^k < p^{m-k}+2$$

A stąd prosty wniosek: (ze względu na zasadę skwantowania)

$$p^k = p^{m-k}+1$$
$$p^k - p^{m-k}=1$$
$$p^{m-k}(p^{2k-m}-1)=1$$

$p^{m-k} > 0$, przeto: 

$$p^{m-k} = 1 \wedge p^{2k-m}-1=1$$

$p^{m-k} = 1 \Rightarrow p = 1$ co jest sprzeczne, więc z tego przypadku otrzymujemy tylko sprzeczność.

Teraz rozpatrzmy pierwszy przypadek ($m\leq k$):

$$p^{2k}-2p^k+2=p^m$$
$$p^{2k}-2p^k-p^m+2=0$$
$$p^m(p^{2k-m}-2p^{k-m}-1)=-2$$

Tak samo jak poprzednio – żeby ten iloczyn był ujemny to ten drugi czynnik musi być ujemny ponieważ $p^m>0$.

$$p^{2k-m}-2p^{k-m}-1<0$$
$$p^{2k-m}<2p^{k-m}+1$$
$$p^{2k}<2p^{k}+p^m$$

Zauważmy, że: $(m\leq k \Rightarrow p^m\leq p^k)$

$$p^{2k}<2p^k+p^m\leq 3p^k$$
$$p^{2k} < 3p^k$$
$$p^k < 3$$

Skoro $k>2$ to żadna liczba pierwsza tego nie spełnia.

A więc skoro dla obu przypadków nam wyszło, że dla $k>1$ jest sprzeczność, to widzimy, że jedynym rozwiązaniem jest $x=1$.

Odpowiedź: $x=1$.


\end{document}