Problem OM 76.2.2

% NumberTheory, Primes, FLT

\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{polski}
\usepackage{graphicx}
\usepackage{float}
\usepackage{fontspec}
\usepackage[most]{tcolorbox}

\setmainfont{Linux Libertine O}
\newtheorem{theorem}{Theorem}[section]

\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}{LXXVI OM, etap 2, 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}

\newtcolorbox{bluebox}[1]{
    breakable,
    enhanced jigsaw,
    colback=blue!5!white,
    colframe=blue!50!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

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

\section*{Problem Statement}

Wyznaczyć wszystkie liczby całkowite $n \geq 2$ o następującej własności:
liczba $2^k \cdot n - 1$ jest pierwsza dla każdego $k \in \{2, 3, \ldots, n\}$.
\bigskip

\noindent\textbf{Rozwiązanie:}

W rozwiązaniu będziemy korzystali z Małego Twierdzenia Fermata (MTF, FLT)

\begin{bluebox}{Małe Twierdzenie Fermata}
    \begin{theorem}[Małe Twierdzenie Fermata]
        Niech $ p $ będzie liczbą pierwszą, a $ a $ liczbą całkowitą taką, że $ p \nmid a $.  
        Wówczas zachodzi:
        $$
        a^{p-1} \equiv 1 \pmod{p}.
        $$
    \end{theorem}
\end{bluebox}

Najpierw sprawdźmy małe wartości:
\begin{itemize}
    \item Dla $n=2$: Sprawdzamy $k=2$. Mamy $2^2 \cdot 2 - 1 = 7$, które jest
          pierwsze.
    \item Dla $n=3$: Sprawdzamy $k=2,3$. Obliczamy $2^2 \cdot 3 - 1 = 11$
          (pierwsze) oraz $2^3 \cdot 3 - 1 = 23$ (pierwsze).
\end{itemize}
Zatem $n=2$ i $n=3$ spełniają warunki zadania.

\vspace{5pt}
\noindent\textbf{Przypadek 1:} Niech $n \geq 4$ będzie parzyste. Wówczas $n-1$
jest nieparzystą liczbą złożoną (gdyż $n-1 \geq 3$). Niech $p$ będzie
\textbf{dowolnym dzielnikiem pierwszym} liczby $n-1$. Wówczas:
\begin{itemize}
    \item $p$ jest nieparzyste i $p \geq 3$,
    \item $p-1 \leq n-1$ (bo $p \mid n-1$),
    \item Z Małego Twierdzenia Fermata: $2^{p-1} \equiv 1 \pmod{p}$.
\end{itemize}
Rozważmy liczbę $2^{p-1} \cdot n - 1$. Ponieważ $n \equiv 1 \pmod{p}$ (bo $p
    \mid n-1$), mamy:
\[
    2^{p-1} \cdot n - 1 \equiv 2^{p-1} \cdot 1 - 1 \equiv 0 \pmod{p}.
\]
Stąd $p \mid 2^{p-1} \cdot n - 1$. Ponieważ $2^{p-1} \cdot n - 1 \geq 2^{2}
    \cdot 4 - 1 = 15 > p$, liczba ta jest złożona. Zatem żadne parzyste $n \geq 4$
nie spełnia warunku.

\vspace{5pt}
\noindent\textbf{Przypadek 2:} Niech $n \geq 5$ będzie nieparzyste. Wówczas
$n-2$ jest nieparzystą liczbą złożoną (gdyż $n-2 \geq 3$). Niech $p$ będzie
\textbf{dowolnym dzielnikiem pierwszym} liczby $n-2$. Rozważmy dwa
podprzypadki:

\begin{itemize}
    \item \textbf{Podprzypadek 2.1:} $p=3$. Wówczas $3 \mid n-2$, czyli $n
              \equiv 2 \pmod{3}$. Rozważmy $k=3$:
          \[
              2^3 \cdot n - 1 = 8n - 1 = 8(n-2) + 15.
          \]
          Ponieważ $3 \mid n-2$ i $3 \mid 15$, liczba $8n -1$ jest podzielna
          przez $3$ i większa od $3$, więc jest złożona.

    \item \textbf{Podprzypadek 2.2:} $p \geq 5$. Wówczas $p-2 \geq 3$ oraz $p-2
              \leq n-2$ (bo $p \mid n-2$). Z MTF:
          \[
              2^{p-1} \equiv 1 \pmod{p} \implies 2^{p-2} \equiv \frac{1}{2} \pmod{p}.
          \]
          Ponieważ $n \equiv 2 \pmod{p}$ (bo $p \mid n-2$), mamy:
          \[
              2^{p-2} \cdot n \equiv 2^{p-2} \cdot 2 \equiv 2^{p-1} \equiv 1
              \pmod{p}.
          \]
          Stąd $2^{p-2} \cdot n - 1 \equiv 0 \pmod{p}$. Liczba ta jest większa od
          $p$ (np. dla $p=5$, $n \geq 5$: $2^{3} \cdot 5 - 1 = 39 > 5$), więc jest
          złożona.
\end{itemize}

W obu podprzypadkach otrzymujemy sprzeczność. Zatem jedynymi rozwiązaniami są
$n=2$ i $n=3$.

\vspace{10pt}

\[
    \boxed{n \in \{2, 3\}}
\]

\bigskip
\bigskip
\bigskip

\fontsize{12}{13}\selectfont

Niestety to rozwiązanie jest to kopia rozwiązania umieszczonego na stronie OMa.
Nie udało mi się go zrobić samemu a chciałem umieścić. Dlatego jakość jest
gorsza od pozostałych rozwiązań. (Za niedogodności przepraszamy)

\end{document}