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}

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

\section*{Rozwiązanie}

Rozłóżmy dane wyrażenie na czynniki:
\begin{align*}
S &= (1+x+x^2+x^3) + x^4(1+x+x^2+x^3) \\
  &= (1+x+x^2+x^3)(x^4+1) \\
  &= (x+1)(x^2+1)(x^4+1).
\end{align*}

Liczba $S$ ma być postaci $p^N$, gdzie $p$ jest liczbą pierwszą oraz $N \in \mathbb{Z}_{\ge 1}$. Oznacza to, że każdy z czynników tego iloczynu musi być potęgą tej samej liczby pierwszej $p$. W szczególności:
$$x+1 = p^k \quad \text{dla pewnego } k \in \mathbb{Z}_{\ge 1}.$$

Rozpatrzmy dwa główne przypadki: $k=1$ oraz $k \ge 2$.

\subsection*{Przypadek 1: $k = 1$ ($x = p - 1$)}

Wstawiając $x = p - 1$ do drugiego czynnika, otrzymujemy:
$$x^2 + 1 = (p-1)^2 + 1 = p^2 - 2p + 2.$$
Wartość ta również musi być potęgą liczby pierwszej $p$, czyli:
$$p^2 - 2p + 2 = p^{k_1} \quad \text{dla pewnego } k_1 \in \mathbb{Z}_{\ge 0}.$$

Sprawdźmy małe wartości wykładnika $k_1$:
\begin{itemize}
    \item Dla $k_1 = 0$: $p^2 - 2p + 2 = 1 \iff (p-1)^2 = 0 \iff p = 1$, co jest sprzeczne, gdyż $1$ nie jest liczbą pierwszą.
    \item Dla $k_1 = 1$: $p^2 - 2p + 2 = p \iff p^2 - 3p + 2 = 0 \iff (p-1)(p-2) = 0$. Jedynym pierwszym rozwiązaniem jest $p = 2$.
    \item Dla $k_1 = 2$: $p^2 - 2p + 2 = p^2 \iff -2p + 2 = 0 \iff p = 1$ (brak rozwiązań pierwszych).
\end{itemize}

Wykażemy teraz za pomocą rachunku różniczkowego, że dla $k_1 \ge 3$ równanie nie ma rozwiązań w liczbach rzeczywistych $t > 1$ (w szczególności dla liczb pierwszych $p \ge 2$). 

Zdefiniujmy funkcję pomocniczą dla $t > 0$:
$$h(t) = t^2 - 2t + 2 - t^{k_1}.$$
Zauważmy, że $h(1) = 1^2 - 2(1) + 2 - 1^{k_1} = 0$. Pochodna funkcji $h(t)$ wynosi:
$$h'(t) = 2t - 2 - k_1 t^{k_1 - 1} = 2(t-1) - k_1 t^{k_1 - 1}.$$

Zbadajmy znak pochodnej $h'(t)$ na przedziale $(0, \infty)$:
\begin{itemize}
    \item Dla $t \in (0, 1)$: mamy $2(t-1) < 0$ oraz $-k_1 t^{k_1 - 1} < 0$, skąd bezpośrednio wynika, że $h'(t) < 0$.
    \item Dla $t \ge 1$: wyznaczmy drugą pochodną:
    $$h''(t) = 2 - k_1(k_1 - 1)t^{k_1 - 2}.$$
    Dla $k_1 \ge 3$ oraz $t \ge 1$ zachodzi $k_1(k_1 - 1) \ge 3 \cdot 2 = 6$ oraz $t^{k_1 - 2} \ge 1$, zatem:
    $$h''(t) \le 2 - 6 = -4 < 0.$$
    Skoro $h'(1) = -k_1 < 0$ oraz $h''(t) < 0$ dla każdego $t \ge 1$, to funkcja $h'(t)$ jest ściśle malejąca na tym przedziale, a więc $h'(t) \le h'(1) < 0$ dla wszystkich $t \ge 1$.
\end{itemize}

Oznacza to, że $h'(t) < 0$ dla każdego $t > 0$, czyli funkcja $h(t)$ jest ściśle malejąca w całej dodatniej dziedzinie. Wobec tego punkt $t = 1$ jest jedynym miejscem zerowym funkcji $h(t)$ dla $t > 0$. Ponieważ liczba $1$ nie jest liczbą pierwszą, dla $k_1 \ge 3$ równanie $p^2 - 2p + 2 = p^{k_1}$ nie posiada rozwiązań pierwszych.

Jedynym rozwiązaniem w tym przypadku jest $p = 2$, co daje $x = p - 1 = 1$. Sprawdzamy wyjściowe wyrażenie:
$$S(1) = 1+1+1+1+1+1+1+1 = 8 = 2^3,$$
co stanowi potęgę liczby pierwszej. Zatem $x = 1$ spełnia warunki zadania.

\subsection*{Przypadek 2: $k \ge 2$ ($x = p^k - 1$)}

Podstawiając $x = p^k - 1$ do czynnika $x^2 + 1$, otrzymujemy:
$$x^2 + 1 = (p^k - 1)^2 + 1 = p^{2k} - 2p^k + 2.$$
Wyrażenie to musi być równe $p^m$ dla pewnego $m \in \mathbb{Z}_{\ge 0}$. 

Zauważmy, że dla $p \ge 2$ oraz $k \ge 2$ mamy $-2p^k + 2 \le -2 \cdot 4 + 2 = -6 < 0$, skąd:
$$p^m = p^{2k} - 2p^k + 2 < p^{2k} \implies m < 2k.$$

Rozważmy dwa podprzypadki w zależności od relacji między $m$ a $k$:

\paragraph{Podprzypadek 2.1: $m > k$}
Przekształcamy równanie:
$$p^{2k} - 2p^k + 2 = p^m \iff p^k(p^k - 2 - p^{m-k}) = -2.$$
Lewa strona jest podzielna przez $p^k$. Zatem $p^k$ musi być dzielnikiem liczby $-2$, co oznacza, że:
$$p^k \le 2.$$
Jest to jednak sprzeczne z założeniem, że $p \ge 2$ oraz $k \ge 2$, gdyż wtedy $p^k \ge 2^2 = 4 > 2$. Przypadek ten nie daje rozwiązań.

\paragraph{Podprzypadek 2.2: $m \le k$}
Przekształcamy równanie, wyłączając $p^m$:
$$p^{2k} - 2p^k - p^m + 2 = 0 \iff p^m(p^{2k-m} - 2p^{k-m} - 1) = -2.$$
Ponieważ iloczyn po lewej stronie jest ujemny, a $p^m > 0$, drugi czynnik musi być ujemny:
$$p^{2k-m} - 2p^{k-m} - 1 < 0 \iff p^{2k-m} < 2p^{k-m} + 1.$$
Mnożąc obie strony przez $p^m$, dostajemy:
$$p^{2k} < 2p^k + p^m.$$
Wykorzystując założenie $m \le k$ (z którego wynika $p^m \le p^k$), otrzymujemy:
$$p^{2k} < 2p^k + p^k = 3p^k.$$
Dzieląc obustronnie przez $p^k > 0$:
$$p^k < 3.$$
Ponieważ jednak $p \ge 2$ oraz $k \ge 2$, zachodzi $p^k \ge 2^2 = 4$, co stoi w sprzeczności z nierównością $p^k < 3$.

\bigskip
Wszystkie gałęzie przypadku $k \ge 2$ prowadzą do sprzeczności. 

\section*{Odpowiedź}
Jedyną dodatnią liczbą całkowitą spełniającą warunki zadania jest $x = 1$.

\section*{Sposób 2 (arytmetyka modularna i NWD)}

Rozpatrzmy to samo zadanie przy użyciu standardowych narzędzi teorii liczb: badania największego wspólnego dzielnika oraz kongruencji.

Podobnie jak poprzednio, rozkładamy dane wyrażenie na czynniki:
$$S = (x+1)(x^2+1)(x^4+1).$$

Załóżmy, że $S = p^n$, gdzie $p$ jest liczbą pierwszą oraz $n \ge 1$. Wówczas każdy z czynników $(x+1)$, $(x^2+1)$ oraz $(x^4+1)$ musi być potęgą tej samej liczby pierwszej $p$.

Zbadajmy największy wspólny dzielnik dwóch pierwszych czynników. Korzystając z algorytmu Euklidesa:
$$\gcd(x+1, x^2+1) = \gcd(x+1, x^2+1 - (x-1)(x+1)) = \gcd(x+1, 2).$$
Wynika stąd bezpośrednio, że:
$$\gcd(x+1, x^2+1) \in \{1, 2\}.$$

Rozpatrzmy dwa przypadki ze względu na parzystość liczby pierwszej $p$:

\begin{enumerate}
    \item \textbf{Liczba $p$ jest nieparzysta ($p > 2$):} \\
    Czynniki $x+1$ oraz $x^2+1$ są potęgami nieparzystej liczby pierwszej $p$. Ich największy wspólny dzielnik również musi być potęgą $p$. Ponieważ jednak $\gcd(x+1, x^2+1) \mid 2$, jedyną możliwością jest:
    $$\gcd(x+1, x^2+1) = 1.$$
    Dwie potęgi tej samej liczby pierwszej mogą być względnie pierwsze tylko wtedy, gdy mniejsza z nich jest równa $p^0 = 1$. Zatem:
    $$x+1 = 1 \implies x = 0,$$
    co stoi w sprzeczności z warunkiem, że $x$ jest dodatnią liczbą całkowitą ($x \ge 1$). Oznacza to, że liczba $p$ nie może być nieparzysta.

    \item \textbf{Liczba $p$ jest parzysta ($p = 2$):} \\
    W tym przypadku każdy czynnik musi być potęgą dwójki. W szczególności istnieje liczba całkowita $b \ge 1$ taka, że:
    $$x^2 + 1 = 2^b.$$
    
    Zauważmy, że skoro $x+1$ jest potęgą dwójki oraz $x \ge 1$:
    \begin{itemize}
        \item Jeśli $x = 1$, to $x+1 = 2 = 2^1$, $x^2+1 = 2 = 2^1$, $x^4+1 = 2 = 2^1$, skąd $S = 2 \cdot 2 \cdot 2 = 8 = 2^3$, co jest poprawnym rozwiązaniem.
        \item Jeśli $x > 1$, to $x+1 \ge 4$, skąd wynika, że $x$ musi być liczbą nieparzystą ($x = 2k+1$).
    \end{itemize}
    Dla dowolnej nieparzystej liczby całkowitej $x$ zachodzi:
    $$x^2 \equiv 1 \pmod 4 \implies x^2 + 1 \equiv 2 \pmod 4.$$
    Oznacza to, że liczba $x^2+1$ jest podzielna przez $2$, ale nie jest podzielna przez $4$. Jedyną potęgą dwójki dającą resztę $2$ z dzielenia przez $4$ jest $2^1 = 2$.
    
    Otrzymujemy zatem:
    $$x^2 + 1 = 2 \implies x^2 = 1 \implies x = 1$$
    (ponieważ $x \in \mathbb{Z}^+$), co nie daje nowych rozwiązań poza $x=1$.
\end{enumerate}

\bigskip
\textbf{Odpowiedź:} Jedyną dodatnią liczbą całkowitą spełniającą warunki zadania jest $x = 1$.

\end{document}