Problem done/OMJ/I/1.2.4.tex

% NumberTheory, Integers, Primes

\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{enumitem}
\usepackage[most]{tcolorbox}

\setmainfont{Linux Libertine O}
\newfontfamily\russianfont{Linux Libertine O}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[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}{I OMG, etap 2, 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}
\fontsize{13.5}{15}\selectfont

\section*{Problem Statement}

Wyznacz wszystkie dodatnie liczby całkowite $n$, dla których liczba $14^n-9$ jest pierwsza.

\bigskip

\noindent\textbf{Solution:}

Sprawdźmy na początek kilka małych wartości:

Zauważmy, że dla $n=1$ mamy: $14^1-9 = 5$. Co jest liczbą pierwszą!

$n=2$: $14^2-9=187=11\cdot17$. Czyli nie jest pierwsza.

$n=3$: $14^3-9=2735$. Jest podzielna przez 5 czyli nie jest pierwsza.

Dlatego dajmy taką hipotezę: dla $n>1$ liczba $14^n - 9$ \textbf{nie jest} pierwsza.

Rozważmy przypadki: gdy $n$ jest parzyste i gdy $n$ jest nieparzyste.

Najpierw, gdy $n$ jest nieparzyste i większe niż 1.

Najpierw zauważmy, że $14^n$ zawsze daje resztę 4 przy dzieleniu przez 10.

\textbf{Dowód:}

Zauważmy, że obliczamy potęgi liczby 4 modulo 10. Sprawdźmy kilka pierwszych potęg:

\[
\begin{aligned}
4^1 &\equiv 4 \pmod{10}, \\
4^2 &= 16 \equiv 6 \pmod{10}, \\
4^3 &= 64 \equiv 4 \pmod{10}, \\
4^4 &= 256 \equiv 6 \pmod{10}, \\
\end{aligned}
\]

Widzimy, że powstaje cykl długości 2:
\[
4, 6, 4, 6, \ldots
\]

Możemy więc zapisać:
\[
4^n \equiv 
\begin{cases}
4 \pmod{10}, & \text{gdy } n \text{ nieparzyste}, \\
6 \pmod{10}, & \text{gdy } n \text{ parzyste}.
\end{cases}
\]

Zatem, dla każdego nieparzystego \( n \), \( 4^n \equiv 4 \pmod{10} \).

Ale wtedy:
$$ 14^n - 9 \equiv 4-9 \equiv -5 \equiv -5 + 10 \equiv 5 \pmod{10} $$

Czyli ostatnią cyfrą jest zawsze 5, ale wiemy, że ta liczba jest $>5$, co oznacza, że jest podzielna przez 5, ale nie jest równa 5. Czyli nie jest pierwsza.

Teraz przypadek, gdy $n$ jest parzyste.

Oznaczmy, że $n=2k$. Wtedy:
$$ 14^n - 9 = 14^{2k} - 3^2 = (14^k)^2 - 3^2 = (14^k - 3)(14^k + 3)$$

Dla $n\geq2$, czyli $k\geq1$ oba czynniki są większe niż 1. Co oznacza, że liczba $14^n - 9$ nie jest pierwsza.

Jak widać, udało się dowieść naszą hipotezę, co oznacza, że jedyną możliwością jest $n=1$.

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

\end{document}