Problem OMJ 22.1.4

% NumberTheory, Integers, Primes

\documentclass[a4paper,12pt]{article}

\usepackage[left=2cm, top=2cm, right=2cm, bottom=1cm, includeheadfoot,
    headheight=50pt]{geometry}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{float}
\usepackage[most]{tcolorbox}
\usepackage{enumitem}
\usepackage{graphicx}

\usepackage{polyglossia}
\setmainlanguage{polish}

\usepackage{amsmath, amsthm}

\usepackage{fontspec}
\usepackage{unicode-math}

\setmainfont{Linux Libertine O}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]

\newcommand{\Name}{Hostek}
\newcommand{\Email}{your.email@example.com}
\newcommand{\ProblemNumber}{XXII OMJ, etap 1, zadanie 4}

\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*{Problem Statement}

Wyznacz wszystkie pary liczb pierwszych $p, q$, dla których $p > q$ i liczby $p - q$ oraz $p + q$ również są pierwsze.

\bigskip

\noindent\textbf{Solution:}

Zauważmy, że gdyby $p$ i $q$ były liczbami nieparzystymi to zarówno ich różnica i suma byłyby parzyste. A skoro jest tylko jedna liczba pierwsza parzysta to byłoby niemożliwe by suma i różnica były naraz liczbami pierwszymi.

Stąd możemy wywnioskować, że $q = 2$. (Bo jedna z liczb $p$ i $q$ musi być parzysta a druga nieparzysta, a jak wiadomo $2$ to jedyna liczba pierwsza parzysta).

Zatem różnica i suma mają postać odpowiednio: $p - 2$ oraz $p + 2$.

Przeanalizujmy różne reszty z dzielenia przez $3$ liczby $p$:
\begin{itemize}
    \item co gdy $p \equiv 0 \pmod{3}$: Zauważmy, że jedyna liczba pierwsza, która daje resztę $0$ przy dzieleniu przez $3$ to $3$. Zatem sprawdźmy czy $p = 3$ jest dobre:
    \[
        p - 2 = 3 - 2 = 1
    \]
    jak widać: różnica $p$ i $q$ nie jest liczbą pierwszą. Zatem ten przypadek nie daje nam żadnej odpowiedzi.
    \item co gdy $p \equiv 1 \pmod{3}$: Zauważmy, że wtedy:
    \[
    p+2 \equiv 3 \equiv 0 \pmod{3}
    \]
    Zatem, żeby $p+2$ było liczbą pierwszą to musi być równe $3$ jak to pokazaliśmy w poprzednim przypadku. Zatem
    \[
        p + 2 = 3 \Longrightarrow p = 1
    \]
    Tutaj też nie mamy żadnej odpowiedzi, bo $1$ nie jest liczbą pierwszą.
    \item co gdy $p \equiv 2 \pmod{3}$: Zauważmy, że wtedy:
    \[
        p - 2 \equiv 0 \pmod{3}
    \]
    Zatem, żeby $p-2$ było liczbą pierwszą to jedyną możliwością (tak jak to pokazaliśmy w poprzednich przypadkach) jest:
    \[
        p - 2 = 3 \Longrightarrow p = 5
    \]
    Jak widać różnica $p-2$ jest liczbą pierwszą i $p = 5$ też jest liczbą pierwszą. Sprawdźmy czy $p+2$ jest liczbą pierwszą: $p + 2 = 5 + 2 = 7$. Jak widać jest liczbą pierwszą. Jest to jedyna możliwa odpowiedź.
\end{itemize}

Z rozważenia powyższych przypadków widzimy, że jedynie para $(p,q)=(5,2)$ jest dobra.

\textbf{Odpowiedź: } $(p,q)=(5,2)$.

\noindent\textit{Dodatek: Jak wpaść na rozwiązanie?}

Intuicja na rozwiązanie jest taka, że gdy już zauważymy, że musi być $q = 2$ to mamy takie trzy liczby:
\[
    p - 2 \quad p \quad p + 2
\]

Pomysł żeby rozważyć reszty dzielenia przez $3$ liczby $p$ bierze się stąd, że zachodzi:
\[
    -2 \equiv +1 \pmod{3}
\]

A zatem patrząc "modulo $3$" na nasze liczby otrzymujemy:
\[
    p \quad p + 1 \quad p + 2
\]

A wiadomo przecież że wśród trzech kolejnych liczb całkowitych jest przynajmniej jedna (i tylko jedna!) podzielna przez $3$. (A jedyną liczbą pierwszą podzielną przez $3$ jest $3$.)

\textbf{Drugi sposób:}

Rozważmy iloczyn liczb $p - q$ oraz $p + q$:
\[
    (p - q)(p + q) = p^2 - q^2.
\]

Zbadajmy podzielność tego wyrażenia przez $3$. Rozpatrzmy dwa przypadki ze względu na podzielność liczb $p$ i $q$ przez $3$:

\begin{enumerate}[label=\textbf{\arabic*.}]
    \item \textbf{Przypadek, w którym co najmniej jedna z liczb $p, q$ jest równa $3$:}
    \begin{itemize}
        \item Jeśli $p = 3$, to z warunku $p > q$ wynika, że jedyną możliwością jest $q = 2$. Otrzymujemy wówczas $p - q = 3 - 2 = 1$, co nie jest liczbą pierwszą.
        \item Jeśli $q = 3$, to $p > 3$, zatem $p$ musi być nieparzystą liczbą pierwszą. Wtedy jednak obie liczby:
        \[
            p - q = p - 3 \quad \text{oraz} \quad p + q = p + 3
        \]
        byłyby parzyste (jako różnica i suma dwóch liczb nieparzystych) oraz większe od $2$, co oznacza, że żadna z nich nie mogłaby być liczbą pierwszą.
    \end{itemize}
    W tym przypadku brak rozwiązań.

    \item \textbf{Przypadek, w którym $p \neq 3$ oraz $q \neq 3$:} \\
    Kwadrat dowolnej liczby całkowitej niepodzielnej przez $3$ daje resztę $1$ z dzielenia przez $3$, zatem:
    \[
        p^2 \equiv 1 \pmod{3} \quad \text{oraz} \quad q^2 \equiv 1 \pmod{3}.
    \]
    Wynika stąd, że:
    \[
        (p - q)(p + q) = p^2 - q^2 \equiv 1 - 1 \equiv 0 \pmod{3}.
    \]
    Iloczyn $(p - q)(p + q)$ jest więc podzielny przez $3$. Ponieważ $3$ jest liczbą pierwszą, dzieli ona co najmniej jeden z czynników:
    \[
        3 \mid (p - q) \quad \text{lub} \quad 3 \mid (p + q).
    \]
    Skoro liczby $p - q$ oraz $p + q$ mają być pierwsze, jedyna liczba pierwsza podzielna przez $3$ to $3$. Z nierówności $p - q < p + q$ wynika, że to mniejsza z nich musi być równa $3$:
    \[
        p - q = 3 \iff p = q + 3.
    \]
    Różnica liczb $p$ i $q$ jest liczbą nieparzystą ($3$), co oznacza, że liczby $p$ i $q$ mają różną parzystość. Jedyną parzystą liczbą pierwszą jest $2$, a ponieważ $p > q$, otrzymujemy:
    \[
        q = 2 \implies p = 2 + 3 = 5.
    \]
\end{enumerate}

Sprawdzamy otrzymaną parę $(p, q) = (5, 2)$:
\[
    p - q = 5 - 2 = 3 \quad (\text{liczba pierwsza}),
\]
\[
    p + q = 5 + 2 = 7 \quad (\text{liczba pierwsza}).
\]
Wszystkie warunki zadania są spełnione.

\bigskip
\noindent\textbf{Odpowiedź:} Jedyną parą spełniającą warunki zadania jest $(p, q) = (5, 2)$.

\bigskip
\noindent\textit{Komentarz dydaktyczny: Dlaczego ten sposób jest wart zapamiętania?}

Zauważenie tożsamości $(p-q)(p+q) = p^2 - q^2$ to klasyczny trik olimpijski. Własność:
\[
a \not\equiv 0 \pmod{3} \implies a^2 \equiv 1 \pmod{3}
\]
(będąca prostym wnioskiem z Małego Twierdzenia Fermata) pozwala błyskawicznie powiązać sumę i różnicę bez konieczności rozpisywania każdego z trzech przypadków reszt liczby $p$ z osobna.

\end{document}