Problem done/OMJ/demo/omj.demo.4.tex

% NumberTheory, Divisors, Primes, Integers

\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}{demo 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}
\fontsize{14}{14}\selectfont

\section*{Problem Statement}
Dodatnia liczba całkowita $n$ ma dokładnie trzy różne dodatnie dzielniki. Uzasadnij, że liczba $n^2$ ma dokładnie pięć różnych dodatnich dzielników.
\bigskip

\noindent\textbf{Solution:}

Wprowadźmy na początku następujące twierdzenie:

\begin{theorem}
    Jeśli $a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$, gdzie $p_i$ to liczby pierwsze, a $\alpha_i$ są dodatnie, to liczba dodatnich dzielników $a$ jest równa:
    $$(\alpha_1 + 1) \cdot (\alpha_2 + 1) \cdot \ldots \cdot (\alpha_k + 1)$$
\end{theorem}

\begin{proof}
    Rozpocznijmy od rozpisania liczby \( a \) w postaci iloczynu potęg liczb pierwszych:
    \[
    a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}
    \]
    gdzie \( p_1, p_2, \dots, p_k \) to liczby pierwsze, a \( \alpha_1, \alpha_2, \dots, \alpha_k \) to liczby dodatnie.
    
    Każdy dzielnik \( d \) liczby \( a \) ma postać:
    \[
    d = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_k^{b_k}
    \]
    gdzie \( b_1, b_2, \dots, b_k \) są liczbami całkowitymi spełniającymi warunki:
    \[
    0 \leq b_i \leq \alpha_i \quad \text{dla każdego} \ i = 1, 2, \dots, k.
    \]
    
    Zatem, dla każdej liczby pierwszej \( p_i \), \( b_i \) może przyjąć \( \alpha_i + 1 \) różnych wartości (od 0 do \( \alpha_i \) włącznie).
    
    Ponieważ liczba dzielników liczby \( a \) jest równa liczbie różnych kombinacji wartości \( b_1, b_2, \dots, b_k \), to liczba dzielników liczby \( a \) jest iloczynem liczby możliwych wartości \( b_1, b_2, \dots, b_k \):
    \[
    (\alpha_1 + 1) \cdot (\alpha_2 + 1) \cdot \ldots \cdot (\alpha_k + 1)
    \]
    
    Tym samym, liczba dodatnich dzielników liczby \( a \) jest równa:
    \[
    (\alpha_1 + 1) \cdot (\alpha_2 + 1) \cdot \ldots \cdot (\alpha_k + 1),
    \]
    co kończy dowód.
\end{proof}

Zatem, oznaczmy $n$ jako: 
$$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$$
gdzie $p_i$ to liczby pierwsze, a $\alpha_i$ są dodatnie.

Wiemy, z założeń zadania, że liczba dzielników $n$ jest równa 3. Ale patrząc na powyższe twierdzenie możemy również stwierdzić, że:
$$(\alpha_1 + 1) \cdot (\alpha_2 + 1) \cdot \ldots \cdot (\alpha_k + 1) = 3$$

A skoro $\alpha_i$ są dodatnie to jedyny możliwy przypadek to: $k = 1$, $\alpha_1 = 2$. (Również ze względu na to, że 3 jest liczbą pierwszą, więc jedyny możliwy iloczyn, który by to spełniał to pojedyncza liczba 3)

A skoro tak, to: $n = p^2$, gdzie $p$ jest liczbą pierwszą.

W takim razie $n^2 = (p^2)^2 = p^4$.

A korzystając znowu z powyższego twierdzenia możemy powiedzieć, że liczba dzielników liczby $p^4$ jest równa $4+1 = 5$. A skoro $n^2 = p^4$ to otrzymujemy tezę. (Przy czym te dzielniki są równe $1$, $p$, $p^2$, $p^3$, $p^4$)

\end{document}