Problem done/CZOM/74/C/74C.2.2.tex

% NumberTheory, GCD, LCM, Primes, Integers, Algebra, EuclideanAlgorithm

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

\DeclareMathOperator{\lcm}{lcm}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{fakcik}{Fakcik}[section]
\newtheorem{algorithmic}{Algorytm}[section]

% dowod, proof
\newtcolorbox{redbox}[1]{
    breakable,
    enhanced jigsaw,
    colback=red!5!white,
    colframe=red!50!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% lemat, lemma
\newtcolorbox{greenbox}[1]{
    breakable,
    enhanced jigsaw,
    colback=green!5!white,
    colframe=green!50!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% twierdzonko, theorem
\newtcolorbox{bluebox}[1]{
    breakable,
    enhanced jigsaw,
    colback=blue!5!white,
    colframe=blue!50!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% zasada, rule 
\newtcolorbox{yellowbox}[1]{
    breakable,
    enhanced jigsaw,
    colback=yellow!5!white,
    colframe=yellow!70!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% Fakcik, fact
\newtcolorbox{purplebox}[1]{
    breakable,
    enhanced jigsaw,
    colback=purple!5!white,
    colframe=purple!90!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

% algorithm
\newtcolorbox{orangebox}[1]{
    breakable,
    enhanced jigsaw,
    colback=orange!5!white,
    colframe=orange!70!black,
    title=#1,
    fonttitle=\bfseries,
    before upper={\parindent15pt},
    boxrule=0.5pt,
    left=2mm,
    right=2mm,
    top=2mm,
    bottom=2mm,
    before skip=10pt plus 1pt,
    after skip=10pt plus 1pt
}

\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}{74 CZOM, kat. C, etap 2, zadanie 2}

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

\section*{Problem Statement}

Patrik napsal na tabuli dvě přirozená čísla. Všiml si, že jejich součet je prvočíslo 313,
které je navíc dělitelem součtu jejich největšího společného dělitele a nejmenšího
společného násobku. Která čísla Patrik na tabuli napsal?

\noindent\textbf{Solution:}

Patryk napisał na tablicy dwie liczby naturalne. Zauważył, że ich suma jest równa liczbie pierwszej 313. Ponadto zauważył, że suma największego wspólnego dzielnika tych liczb i najmniejszej wspólnej wielokrotności tych liczb również jest równa 313. Jakie liczby napisał Patryk na tablicy?

\bigskip

\noindent\textbf{Solution:}

W tym zadaniu będziemy używać oznaczeń: 
\begin{itemize}
    \item $\gcd\left(x,y\right)$ - największy wspólny dzielnik
    \item $\lcm\left(x,y\right)$ - najmniejsza wspólna wielokrotność
\end{itemize}

Oznaczmy liczby, które Patryk zapisał na tablicy jako $a$, $b$. Przy czym bez straty ogólności załóżmy, że $b > a$. (Nie mogą być równe, ponieważ 313 jest nieparzysta)

Napiszmy sobie równanka:
$$
\begin{cases}
a+b=313\\
\gcd\left(a,b\right) + \lcm\left(a,b\right)=313
\end{cases}
$$

Zauważmy fajny fakcik:
\begin{purplebox}{Zależność między $\gcd$ a $\lcm$}
\begin{fakcik}
    \label{fakcik:relationship-gcd-lcm}
    $\lcm\left(x,y\right) = \frac{xy}{\gcd\left(x,y\right)}$
\end{fakcik}
\end{purplebox}

\begin{redbox}{Dowód fakciku \ref{fakcik:relationship-gcd-lcm}}
\begin{proof}
    Aby udowodnić równość \( \text{lcm}(x, y) = \frac{x \cdot y}{\gcd(x, y)} \), przypomnijmy definicje funkcji LCM (najmniejszej wspólnej wielokrotności) oraz GCD (największego wspólnego dzielnika):
    
    \begin{itemize}
        \item Największy wspólny dzielnik \( \gcd(x, y) \) to największa liczba, która dzieli zarówno \( x \), jak i \( y \).
        \item Najmniejsza wspólna wielokrotność \( \text{lcm}(x, y) \) to najmniejsza liczba, która jest podzielna zarówno przez \( x \), jak i \( y \).
    \end{itemize}
    
    Rozkładając \( x \) i \( y \) na czynniki pierwsze:
    \[
    x = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}, \quad y = p_1^{f_1} p_2^{f_2} \dots p_k^{f_k},
    \]
    gdzie \( p_1, p_2, \dots, p_k \) to różne liczby pierwsze, a \( e_1, e_2, \dots, e_k \) oraz \( f_1, f_2, \dots, f_k \) to wykładniki tych liczb w rozkładach na czynniki pierwsze.
    
    Wówczas:
    \[
    \gcd(x, y) = p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \dots p_k^{\min(e_k, f_k)},
    \]
    oraz
    \[
    \text{lcm}(x, y) = p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \dots p_k^{\max(e_k, f_k)}.
    \]
    
    Iloczyn \( x \cdot y \) to:
    \[
    x \cdot y = p_1^{e_1 + f_1} p_2^{e_2 + f_2} \dots p_k^{e_k + f_k}.
    \]
    
    Teraz obliczmy \( \frac{x \cdot y}{\gcd(x, y)} \):
    \[
    \frac{x \cdot y}{\gcd(x, y)} = \frac{p_1^{e_1 + f_1} p_2^{e_2 + f_2} \dots p_k^{e_k + f_k}}{p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \dots p_k^{\min(e_k, f_k)}}.
    \]
    Po uproszczeniu, otrzymujemy:
    \[
    \frac{x \cdot y}{\gcd(x, y)} = p_1^{\max(e_1, f_1)} p_2^{\max(e_2, f_2)} \dots p_k^{\max(e_k, f_k)} = \text{lcm}(x, y).
    \]
    
    Stąd udowodniliśmy, że:
    \[
    \text{lcm}(x, y) = \frac{x \cdot y}{\gcd(x, y)}.
    \]
\end{proof}
\end{redbox}

Czyli używając fakciku \ref{fakcik:relationship-gcd-lcm} otrzymujemy dwa równania:
\begin{equation}
\label{r1}
b=313-a
\end{equation}

\begin{equation}
\label{r2}
\gcd\left(a,b\right) + \frac{ab}{\gcd\left(b\right)} = 313
\end{equation}

Podstawiając \eqref{r1} do \eqref{r2} otrzymujemy:
\begin{equation}
\label{r3}
\gcd\left(a,313-a\right) + \frac{a\left(313-a\right)}{\gcd\left(a,313-a\right)} = 313
\end{equation}

\begin{orangebox}{Algorytm Euklidesa}
\begin{algorithmic}
    \label{a:algorytm-euklidesa}
    Jeśli $y>x$ to:
    $$\gcd\left(x,y\right) = \gcd\left(x,y-x\right)$$
\end{algorithmic}
\end{orangebox}

\begin{redbox}{Dowód algorytmu \ref{a:algorytm-euklidesa}}
\begin{proof}
    Załóżmy, że \( x \) i \( y \) są dwoma liczbami całkowitymi, przy czym \( y > x \). Chcemy udowodnić, że:
    \[
    \gcd(x, y) = \gcd(x, y - x).
    \]
    
    Rozpocznijmy dowód. Niech \( d = \gcd(x, y) \). Oznacza to, że \( d \) jest największym wspólnym dzielnikiem obu liczb \( x \) i \( y \), czyli \( d \) dzieli zarówno \( x \), jak i \( y \). Zatem istnieją liczby całkowite \( q_1 \) i \( q_2 \), takie że:
    \[
    x = d q_1 \quad \text{oraz} \quad y = d q_2.
    \]
    Oznacza to, że \( d \) dzieli również \( y - x \), ponieważ:
    \[
    y - x = d q_2 - d q_1 = d (q_2 - q_1).
    \]
    Zatem \( d \) dzieli \( y - x \), co implikuje, że \( d \) jest wspólnym dzielnikiem \( x \) i \( y - x \).
    
    Teraz, niech \( d' = \gcd(x, y - x) \). Oznacza to, że \( d' \) jest największym wspólnym dzielnikiem \( x \) i \( y - x \), czyli \( d' \) dzieli zarówno \( x \), jak i \( y - x \). Ponieważ \( d \) dzieli \( x \) i \( y - x \), to \( d \) jest także dzielnikiem \( d' \). Zatem \( d' \leq d \).
    
    Z drugiej strony, \( d' \) dzieli \( x \) i \( y - x \), a ponieważ \( y = x + (y - x) \), to \( d' \) dzieli także \( y \). Zatem \( d' \) jest dzielnikiem \( y \), co oznacza, że \( d' \leq d \). Zatem \( d' = d \).
    
    W ten sposób udowodniliśmy, że:
    \[
    \gcd(x, y) = \gcd(x, y - x).
    \]
\end{proof}
\end{redbox}

Używając tego algorytmu Euklidesa (\ref{a:algorytm-euklidesa}) otrzymujemy, że:
$$ \gcd\left(a,313-a\right) = \gcd\left(a,313\right) = 1$$

$\gcd\left(a,313\right) = 1$ ponieważ, z treści zadania wiemy, że $a<313$ oraz, że 313 jest liczbą pierwszą.

Ale podstawiając $\gcd\left(a,313\right) = 1$ do równania \eqref{r3} otrzymujemy:
\begin{align*}
1+a(313-a)&=313\\
313a-a^2&=312\\
a^2-313a+312&=0\\
(a-1)(a-312)&=0\\
\Rightarrow a=1 \vee a=312 &\\
\end{align*}

A używając równania \eqref{r1} otrzymujemy następujące rozwiązanie:
$$(a,b)\in\left\{\left(1,312\right), \left(312,1\right)\right\}$$

Ale zakładaliśmy, że $a < b$, więc otrzymujemy tak iście:
\[
    (a,b)=(1,312)
\]

\textbf{Odpowiedź:} Patryk napisał na tablicy liczby 1 i 312.

\textbf{P.S.} Zauważmy, zresztą, że kolejność nie ma znaczenia, bo operacja dodawania jest przemienna tak samo jak $\gcd$ czy $\lcm$.

\end{document}