Problem done/OMJ/II/2.1.3.tex

% NumberTheory, ModularArithmetic, Primes, DiophantineEquations, SystemOfEquations, Cases

\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{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}{II OMG, etap 1, zadanie 3}

\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{15}{18}\selectfont

\section*{Problem Statement}

Wyznacz wszystkie trójki liczb pierwszych $p$, $q$, $r$ spełniające układ równań
\[
\begin{cases}
    q = p^2 + 6\\
    r = q^2 + 6
\end{cases}
\]

\bigskip

\noindent\textbf{Solution:}

Sprawdźmy, co się dzieje, gdy $p = 2$:
\[
q = p^2 + 6 = 10
\]

Nie jest pierwsza, więc $p=2$ odpada.

Sprawdźmy, co się dzieje, gdy $p = 3$:
\[
q = p^2 + 6 = 15
\]

Nie jest pierwsza, więc $p=3$ odpada.

Zauważmy, że trójka $(5,31,967)$ jest dobra. 
Udowodnijmy, że nie istnieje żadna inna poprawna trójka.
W dowodzie załóżmy $p>5$. Oczywiste jest, że $r > q > p > 5$.

Rozważmy przypadki ze względu na resztę dzielenia liczby $p$ przez 10:
(zauważmy, że ze względu na to, że $p$ jest liczbą pierwszą większą niż 5 nie 
trzeba sprawdzać reszt parzystych ani reszty 5)

Gdy $p \equiv 1 \pmod{10}$ to:
\[
p^2 + 6 \equiv 1^2 + 6 \equiv 7 \pmod{10}
\]

Gdy $p \equiv 3 \pmod{10}$ to:
\[
p^2 + 6 \equiv 3^2 + 6 \equiv 5 \pmod{10}
\]

Sprzeczność! Skoro $q = p^2 + 6$ ma być liczbą pierwszą oraz wiemy, że $q>5$, to 
$q$ nie może dawać reszty 5 przy dzieleniu przez 10. Zatem $p \nequiv 3 \pmod{10}$.

Gdy $p \equiv 7 \pmod{10}$ to:
\[
p^2 + 6 \equiv 7^2 + 6 \equiv 5 \pmod{10}
\]

Sprzeczność! Ta sama co wyżej.

Gdy $p \equiv 9 \pmod{10}$ to:
\[
p^2 + 6 \equiv 9^2 + 6 \equiv 7 \pmod{10}
\]

Czyli po sprawdzeniu tych przypadków, wiemy, że
\[
p \equiv 1 \pmod{10} \quad \vee \quad p \equiv 9 \pmod{10}
\]

Przy czym zauważmy, że w obu przypadkach dostaniemy, że 
\begin{equation}
    q \equiv 7 \pmod{10}
\end{equation}

Czyli pokazaliśmy, że $q$ musi dawać resztę 7 przy dzieleniu przez 10. 
Sprawdźmy jaką resztę daje $r$:
\[
r = q^2 + 6 \equiv 7^2 + 6 \equiv 5 \pmod{10}
\] 

Zakładaliśmy, że $r>5$. 
Jedyną liczbą pierwszą dającą resztę 5 przy dzieleniu przez 10 jest 5, zatem $r$ 
nie jest liczbą pierwszą.

Wniosek: dla $p>5$ nie ma żadnych rozwiązań.

\textbf{Odpowiedź:} Jedyną trójką spełniającą układ równań jest $(p,q,r) = (5,31,967)$.

\end{document}