Problem done/IMO/1959/1959.1.tex

% NumberTheory, EuclideanAlgorithm, GCD, Zlomek

\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]
\newtheorem{algorithmic}{Algorithm}[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}{1959 IMO, 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}

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

\begin{document}
\fontsize{15}{15}\selectfont

\section*{Problem Statement}

Prove that the fraction $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.

\noindent\textbf{Polski:}

Udowodnij, że ułamek $\frac{21n+4}{14n+3}$ jest nieskracalny dla każdej liczby naturalnej $n$.

\bigskip

\noindent\textbf{Solution:}

W rozwiązaniu będziemy używać algorytmu Euklidesa:

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

Zauważmy, że teza jest równoważna temu: 
$$\gcd\left(21n+4,14n+3\right) = 1$$

Wydaje się, że oczywiste jest, że $21n+4 > 14n+3$ dla każdego $n$ dodatniego.

Zastosujmy, przeto, nasz algorytm Euklidesa (patrz alg. \ref{a:algorytm-euklidesa}):
\begin{align*}
\gcd\left(21n+4,14n+3\right) &= \gcd\left(21n+4 - 14n-3,14n+3\right) \\
&= \gcd\left(7n + 1,14n+3\right) \\
&= \gcd\left(7n + 1,14n+3-7n-1\right) \\
&= \gcd\left(7n + 1,7n+2\right) 
\end{align*}

Otrzymaliśmy $\gcd\left(7n + 1,7n+2\right)$, czyli tak iście $\gcd$ dwóch kolejnych liczb całkowitych. Więc jest to równe 1.

\begin{greenbox}{Największy wspólny dzielnik dwóch kolejnych liczb całkowitych}
\begin{lemma}
    \label{lemma:gcd-two-consecutive-integers}
    Dla każdej liczby całkowitej $a$ zachodzi: $\gcd(a, a+1) = 1$.
\end{lemma}
\end{greenbox}

\begin{redbox}{Dowód lematu \ref{lemma:gcd-two-consecutive-integers}}
\begin{proof}
    Jeśli jakaś liczba $d > 1$ dzieli zarówno $a$, jak i $a+1$, to musi również dzielić ich różnicę: $(a+1) - a = 1$. Ale jedyną liczbą dzielącą $1$ jest $1$ — więc taki $d$ nie może istnieć. 

    Zatem największy wspólny dzielnik $a$ i $a+1$ to $1$.
\end{proof}
\end{redbox}

A skoro $\gcd\left(7n + 1,7n+2\right)=1$, to z powyższych równości otrzymujemy:
$$\gcd\left(21n+4,14n+3\right) = 1$$

Co należało dowieść.

\end{document}