Problem OMJ 22.1.1

% NumberTheory, Integers, Divisibility

\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{longtable}
\usepackage{booktabs}

\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 1}

\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 najmniejszą liczbę naturalną $n$ o tej własności, że liczba $6n+ 1$ ma co najmniej
trzy różne dzielniki pierwsze.

\bigskip

\noindent\textbf{Solution:}

\textbf{Sposób 1: (wzorcówka)}

Zauważmy, że liczba $6n + 1$ jest nieparzysta, więc liczba pierwsza $2$ na pewno nie dzieli tej liczby.

Podobnie liczba pierwsza $3$ też nie dzieli tej liczby (przy dzieleniu przez $3$ daje resztę $1$). Jest tak, ponieważ $6n \equiv 0 \pmod{3}$.
\[
    6n + 1 \equiv 0 + 1 \equiv 1 \pmod{3}
\]

Skoro mają to być trzy różne dzielniki pierwsze to przyjmijmy następujące oznaczenie:
\[
    p_1 < p_2 < p_3
\]

Jakie mogą być najmniejsze liczby pierwsze spełniające to? Musi być:
\[
    p_1 \geq 5 \quad p_2 \geq 7 \quad p_3 \geq 11
\]

A zatem iloczyn tych trzech liczb pierwszych jest:
\[
    p_1p_2p_3 \geq 5 \cdot 7 \cdot 11 = 385
\]

Ponieważ $p_1$, $p_2$, $p_3$ są różnymi liczbami pierwszymi, które dzielą liczbę $6n + 1$, to ich iloczyn $p_1p_2p_3$ również dzieli tę liczbę.

Czyli nasza liczba $6n + 1$ musi być co najmniej równa $385$. Zapiszmy tę nierówność:
\begin{align}
    6n + 1 &\geq 385 \\
    6n &\geq 384 \\
    n &\geq 64\label{e1}
\end{align}

Czyli wyszło nam, że $n \geq 64$. Sprawdźmy czy $n=64$ spełnia nasze założenie z zadania:
\[
    6n + 1 = 6 \cdot 64 + 1 = 385 = 5 \cdot 7 \cdot 11
\]

Widzimy, że spełnia założenie zadania! A więc to jest nasza odpowiedź, bo mniejsze $n$ nie może być z warunku \eqref{e1}.

\textbf{Odpowiedź: } $n=64$.

\textbf{Sposób 2: (brute force)}

Uwaga, ten sposób nie jest zalecany na zawodach, ponieważ jest czasochłonny.

Rozpiszmy po kolei wszystkie możliwości jakie możemy uzyskać wstawiając $n = 1, 2, \ldots$.

\begin{longtable}{r r l}
\toprule
$n$ & $6n + 1$ & Rozkład na czynniki pierwsze \\
\midrule
\endfirsthead

\multicolumn{3}{c}%
{{\bfseries Ciąg dalszy z poprzedniej strony}} \\
\toprule
$n$ & $6n + 1$ & Rozkład na czynniki pierwsze \\
\midrule
\endhead

\midrule
\multicolumn{3}{r}{{Ciąg dalszy na następnej stronie...}} \\
\endfoot

\bottomrule
\endlastfoot

1  & 7   & 7 (liczba pierwsza) \\
2  & 13  & 13 (liczba pierwsza) \\
3  & 19  & 19 (liczba pierwsza) \\
4  & 25  & $5^2$ \\
5  & 31  & 31 (liczba pierwsza) \\
6  & 37  & 37 (liczba pierwsza) \\
7  & 43  & 43 (liczba pierwsza) \\
8  & 49  & $7^2$ \\
9  & 55  & $5 \cdot 11$ \\
10 & 61  & 61 (liczba pierwsza) \\
11 & 67  & 67 (liczba pierwsza) \\
12 & 73  & 73 (liczba pierwsza) \\
13 & 79  & 79 (liczba pierwsza) \\
14 & 85  & $5 \cdot 17$ \\
15 & 91  & $7 \cdot 13$ \\
16 & 97  & 97 (liczba pierwsza) \\
17 & 103 & 103 (liczba pierwsza) \\
18 & 109 & 109 (liczba pierwsza) \\
19 & 115 & $5 \cdot 23$ \\
20 & 121 & $11^2$ \\
21 & 127 & 127 (liczba pierwsza) \\
22 & 133 & $7 \cdot 19$ \\
23 & 139 & 139 (liczba pierwsza) \\
24 & 145 & $5 \cdot 29$ \\
25 & 151 & 151 (liczba pierwsza) \\
26 & 157 & 157 (liczba pierwsza) \\
27 & 163 & 163 (liczba pierwsza) \\
28 & 169 & $13^2$ \\
29 & 175 & $5^2 \cdot 7$ \\
30 & 181 & 181 (liczba pierwsza) \\
31 & 187 & $11 \cdot 17$ \\
32 & 193 & 193 (liczba pierwsza) \\
33 & 199 & 199 (liczba pierwsza) \\
34 & 205 & $5 \cdot 41$ \\
35 & 211 & 211 (liczba pierwsza) \\
36 & 217 & $7 \cdot 31$ \\
37 & 223 & 223 (liczba pierwsza) \\
38 & 229 & 229 (liczba pierwsza) \\
39 & 235 & $5 \cdot 47$ \\
40 & 241 & 241 (liczba pierwsza) \\
41 & 247 & $13 \cdot 19$ \\
42 & 253 & $11 \cdot 23$ \\
43 & 259 & $7 \cdot 37$ \\
44 & 265 & $5 \cdot 53$ \\
45 & 271 & 271 (liczba pierwsza) \\
46 & 277 & 277 (liczba pierwsza) \\
47 & 283 & 283 (liczba pierwsza) \\
48 & 289 & $17^2$ \\
49 & 295 & $5 \cdot 59$ \\
50 & 301 & $7 \cdot 43$ \\
51 & 307 & 307 (liczba pierwsza) \\
52 & 313 & 313 (liczba pierwsza) \\
53 & 319 & $11 \cdot 29$ \\
54 & 325 & $5^2 \cdot 13$ \\
55 & 331 & 331 (liczba pierwsza) \\
56 & 337 & 337 (liczba pierwsza) \\
57 & 343 & $7^3$ \\
58 & 349 & 349 (liczba pierwsza) \\
59 & 355 & $5 \cdot 71$ \\
60 & 361 & $19^2$ \\
61 & 367 & 367 (liczba pierwsza) \\
62 & 373 & 373 (liczba pierwsza) \\
63 & 379 & 379 (liczba pierwsza) \\
64 & 385 & $5 \cdot 7 \cdot 11$ \\
\end{longtable}

Zauważmy, dla $n = 64$ mamy trzy różne dzielniki pierwsze! A skoro sprawdzaliśmy każdą możliwość po kolei od najmniejszej to wiemy, że to jest nasza odpowiedź.

\textbf{Odpowiedź:} $n = 64$.

\end{document}