Problem done/CZOM/74/Z9/74Z9.2.1.tex

% NumberTheory, Algebra, CRT, Integers, DiophantineEquations

\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}{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. Z9, etap 2, 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}
\fontsize{15}{15}\selectfont

\section*{Problem Statement}

Najděte všechna dvojmístná přirozená čísla, která mají následující vlastnost: Když
před číslo připíšeme součin jeho první číslice a jeho první číslice zvětšené o 1, dostaneme
druhou mocninu původního čísla.

\noindent\textbf{Polski:}

Znajdź wszystkie dwucyfrowe liczby naturalne, które mają następującą własność: gdy przez liczbę napiszemy iloczyn jej pierwszej cyfry oraz tejże cyfry powiększonej o 1, dostaniemy drugą potęgę liczby wyjściowej.

\bigskip

\noindent\textbf{Solution:}

% \noindent
\boxed{\textbf{Sposób 1: (firmówka)}}

Oznaczmy cyfrę dziesiątek przez $a$, a cyfrę jedności przez $b$. Przy czym $1\leq a\leq 9$, $0\leq b\leq 9$.

Zauważmy, że dopisujemy do naszej liczby dwucyfrowej coś na początek. Czyli ostatnie dwie cyfry (czyli cyfra dziesiątek i jedności) pozostają takie same.

Co oznacza, że w szczególności, chcemy by kwadrat naszej liczby dawał taką samą cyfrę jedności na koniec.

Sprawdzając wszystkie cyfry od 0 do 9 dostajemy, że cyfry spełniające to, że jak podniesiemy je do drugiej potęgi to cyfra jedności będzie taka sama, to: 0, 1, 5, 6. Zachowajmy to w pamięci.

Co oznacza, że na początek dwucyfrowej liczby \textit{coś} dopisujemy? Oznacza to tyle, że po prostu dodajemy to \textit{coś} pomnożone przez 100.

Teraz przejdźmy do zapisania równania
\begin{align*}
100a(a+1) + 10a + b &= (10a + b)^2 \\
100a^2 + 100a + 10a + b &= 100a^2 + 20ab + b^2 \\
110a + b &= 20ab + b^2 
\end{align*}

Czyli dostajemy takie równanko:
\begin{equation}
\label{r1}
110a + b = 20ab + b^2
\end{equation}

Teraz podstawmy każdą możliwą cyfrę jedności do tego równania jako $b$ (patrz powyżej) i sprawdzimy wszystkie odpowiedzi:

\begin{itemize}
    \item $b=0$: otrzymujemy coś takiego: 
    $$110a = 0 \Rightarrow a = 0$$
    ale to jest sprzeczne z założeniami.
    \item $b=1$: otrzymujemy coś takiego:
    $$110a + 1 = 20a + 1 \Rightarrow 90a = 0$$
    Znowu otrzymujemy $a=0$ co jest sprzeczne.
    \item $b=5$: otrzymujemy coś takiego:
    $$110a + 5 = 100a + 25 \Rightarrow 10a = 20$$
    Otrzymujemy $a=2$ co jak najbardziej jest dobre! Czyli jedną z opcji jest liczba $25$.
    \item $b=6$: otrzymujemy coś takiego:
    $$110a + 6 = 120a + 36 \Rightarrow -10a = 30$$
    Otrzymujemy $a = -3$ ale to jest sprzeczne z założeniami.
\end{itemize}

Podsumowując wszystkie przypadki: okazuje się, że jedynym rozwiązaniem jest liczba $25$.

\textbf{Odpowiedź:} Jedyna liczba spełniająca warunki zadania to 25.

\boxed{\textbf{Sposób 2: (CRT)}}

Tak jak poprzednio mamy te cyfry $a$, $b$ (oznaczają to samo).

Zauważmy, że skoro dopisujemy coś na początek, to koniec się nie zmienia. A my mamy mieć kwadrat tej liczby.

Czyli możemy rozpatrywać jedynie dwucyfrowe liczby $x = 10a + b$, które spełniają:
\begin{align*}
x^2 &\equiv x \pmod {100} \\ 
x(x-1) &\equiv 0 \pmod {100}
\end{align*}

Zauważmy, że $100=4\cdot25=2^2\cdot5^2$.

Skoro $x$ i $x-1$ są kolejnymi liczbami całkowitymi to, to oznacza, że jedna jest parzysta a druga nieparzysta.

Dlatego rozpatrzmy cztery przypadki:

\begin{equation}
\label{r2}
\begin{cases}
    x\equiv0 \pmod{25} \\
    x\equiv1 \pmod{4} 
\end{cases}
\end{equation}

\begin{equation}
\label{r3}
\begin{cases}
    x\equiv0 \pmod{4} \\
    x\equiv1 \pmod{25} 
\end{cases}
\end{equation}

\begin{equation}
\label{r4}
x\equiv0 \pmod{100} 
\end{equation}

\begin{equation}
\label{r5}
x\equiv1 \pmod{100} 
\end{equation}
    
Najpierw rozpatrzmy \eqref{r2}:

Używając Chińskiego Twierdzenia o Resztach (ChTR, CRT) wiemy, wszystkie rozwiązania modulo 100 wystarczą.

Z pierwszego równania (w tym układzie równań) wyznaczmy $x=25k$, gdzie $k\in\mathbb{Z}$.

Podstawiając to do drugiego otrzymujemy:
\begin{align*}
25k&\equiv1\pmod4 \\
k&\equiv1\pmod4
\end{align*}

A to nam daje $k=4m+1$, gdzie $m\in\mathbb{Z}$.

Podstawiając spowrotem do równania pierwszego (w tym rozpatrzanym układzie) otrzymujemy:
\begin{align*}
& x = 25k = 25(4m + 1) = 100m + 25 \\
\Rightarrow \ & x \equiv 25 \pmod {100}
\end{align*}

Czyli w tym przypadku otrzymujemy 25 jako możliwe rozwiązanie. Trzymajmy to w pamięci.

Teraz rozpatrzmy \eqref{r3}:

Używając Chińskiego Twierdzenia o Resztach (ChTR, CRT) wiemy, wszystkie rozwiązania modulo 100 wystarczą.

Z pierwszego równania (w tym układzie równań) wyznaczmy $x=4k$, gdzie $k\in\mathbb{Z}$.

Podstawiając to do drugiego otrzymujemy:
$$4k\equiv1\pmod{25}$$

Tutaj $k$ możemy nazwać jako inwersję modularną 4 modulo 25. Bo po podzieleniu przez 4 otrzymujemy:
$$k\equiv\frac{1}{4}\pmod{25}$$

Możemy to znaleźć na dwa sposoby:
\begin{itemize}
    \item Używając ręcznie rozszerzonego algorytmu Euklidesa
    \item Używając małego twierdzenia Fermata
\end{itemize}

Nie będziemy tu używać małego twierdzenia Fermata, bo za dużo ręcznej robótki:
$$ 4^{-1} \equiv 4^{25 - 2} = 4^{23} \pmod{25}$$

Zamiast tego użyjemy rozszerzonego algorytmu Euklidesa:

Czyli szukamy $y$ i $z$ całkowitych takich, że:
$$4y+25z=1$$

Wtedy $k = 4^{-1}\equiv y \pmod {25}$.

Użyjemy rozszerzonego algorytmu Euklidesa, aby znaleźć liczby całkowite \(y\) i \(z\), które spełniają to równanie.

Najpierw wyznaczamy największy wspólny dzielnik:

\begin{align*}
25 &= 6 \cdot 4 + 1 \\
4 &= 4 \cdot 1 + 0
\end{align*}

Zatem:
\[
\gcd(25, 4) = 1
\]

Teraz cofamy się, aby zapisać 1 jako kombinację liniową 25 i 4:

\begin{align*}
1 &= 25 - 6 \cdot 4 \\
  &= 1 \cdot 25 + (-6) \cdot 4
\end{align*}

Zatem jedno z możliwych rozwiązań to:
\[
y = -6, \quad z = 1
\]

Czyli mamy, że $k\equiv-6\equiv19\pmod{25}$

Czyli $k = 25m + 19$, dla $m\in\mathbb{Z}$. 

Podstawiając spowrotem do pierwszego równania (w tym układzie):

$$a=4k=4(25m+19)=100m+76$$

Czyli $a\equiv76\pmod{100}$. To rozwiązanie też miejmy w pamięci.

Rozpatrując teraz \eqref{r4}: 

Mamy $x\equiv0\pmod{100}$, czyli tak iście mamy tylko $x = 0$, $x = 100$. Jak widać żadne nie są dwucyfrowe; czyli w tym przypadku nie mamy żadnych odpowiedzi.

Rozpatrując teraz \eqref{r5}: 

Mamy $x\equiv1\pmod{100}$, czyli tak iście mamy tylko $x = 1$, $x = 101$. Jak widać żadne nie są dwucyfrowe; czyli w tym przypadku nie mamy żadnych odpowiedzi.

Czyli jedyne możliwości to 25 i 76. Sprawdzając czy działają, postępując zgodnie z treścią zadania możemy się przekonać, że tylko 25 jest dobre.

\begin{bluebox}{Chińskie Twierdzenie o Resztach}
    \begin{theorem}[Chińskie Twierdzenie o Resztach]
        \label{tw:crt}
        Niech \( m_1, m_2, \ldots, m_k \) będą liczbami całkowitymi większymi niż 1, takimi że są parami względnie pierwsze, tzn.:
        \[
        \gcd(m_i, m_j) = 1 \quad \text{dla } i \neq j.
        \]
        Dla dowolnych liczb całkowitych \( a_1, a_2, \ldots, a_k \) układ równań kongruencyjnych:
        \[
        \begin{cases}
        x \equiv a_1 \pmod{m_1} \\
        x \equiv a_2 \pmod{m_2} \\
        \quad\vdots \\
        x \equiv a_k \pmod{m_k}
        \end{cases}
        \]
        ma dokładnie jedno rozwiązanie modulo \( M = m_1 m_2 \cdots m_k \).
        
        Innymi słowy, istnieje liczba całkowita \( x \) taka, że spełnia wszystkie powyższe kongruencje, a każde dwa takie rozwiązania są kongruentne modulo \( M \).
    \end{theorem}
\end{bluebox}

\begin{redbox}{Dowód tw. \ref{tw:crt}}
    \begin{proof}
        Rozważmy układ równań:
        \[
        \begin{cases}
        x \equiv a_1 \pmod{m_1} \\
        x \equiv a_2 \pmod{m_2} \\
        \quad\vdots \\
        x \equiv a_k \pmod{m_k}
        \end{cases}
        \]
        Ponieważ \( m_1, m_2, \ldots, m_k \) są parami względnie pierwsze, to z Chińskiego Twierdzenia o Resztach wynika, że istnieje jedno rozwiązanie \( x \), które jest rozwiązaniem układu modularnego.
        
        Aby znaleźć to rozwiązanie, zastosujmy konstrukcję opartą na odwrotnościach modularnych.
        
        Niech \( M = m_1 m_2 \cdots m_k \). Definiujemy \( M_i = \frac{M}{m_i} \) dla każdego \( i = 1, 2, \ldots, k \). Wtedy \( M_i \) jest liczbą, która jest podzielna przez wszystkie \( m_j \) oprócz \( m_i \), czyli \( \gcd(M_i, m_i) = 1 \).
        
        Dla każdego \( i \) możemy znaleźć liczbę \( y_i \) taką, że:
        \[
        M_i y_i \equiv 1 \pmod{m_i}
        \]
        jest to **odwrotność modularna** \( M_i \) modulo \( m_i \).
        
        Zatem rozwiązanie \( x \) układu równań możemy zapisać w postaci:
        \[
        x = \sum_{i=1}^k a_i M_i y_i
        \]
        gdzie każda składnik \( a_i M_i y_i \) jest rozwiązaniem \( x \equiv a_i \pmod{m_i} \).
        
        Ponieważ \( M_i \) jest podzielne przez wszystkie \( m_j \) oprócz \( m_i \), każdy z tych składników spełnia odpowiednią kongruencję. W ten sposób \( x \) jest rozwiązaniem układu.
        
        Na koniec, ponieważ wszystkie \( m_i \) są parami względnie pierwsze, każde dwa rozwiązania \( x_1 \) i \( x_2 \) układu równań będą kongruentne modulo \( M = m_1 m_2 \cdots m_k \).
        
        Zatem rozwiązanie jest jedyne modulo \( M \), co kończy dowód.
    \end{proof}
\end{redbox}

\begin{orangebox}{Rozszerzony algorytm Euklidesa}
    \begin{algorithmic}
        % \caption{Rozszerzony algorytm Euklidesa}
        \label{a:extended-algorytm-euklidesa}
        Rozważmy dwie liczby całkowite \( a \) i \( b \). Celem jest znalezienie ich największego wspólnego dzielnika \( \gcd(a, b) \) oraz współczynników \( x \) i \( y \), takich że:
        \[
        ax + by = \gcd(a, b)
        \]
        
        \textbf{Kroki algorytmu:}
        \begin{enumerate}
            \item Ustal początkowe wartości:
            \[
            r_0 = a, \quad r_1 = b
            \]
            \[
            s_0 = 1, \quad s_1 = 0
            \]
            \[
            t_0 = 0, \quad t_1 = 1
            \]
            \item Powtarzaj kroki aż \( r_1 = 0 \):
            \begin{enumerate}
                \item Oblicz iloraz \( q \) z dzielenia \( r_0 \) przez \( r_1 \):
                \[
                q = \left\lfloor \frac{r_0}{r_1} \right\rfloor
                \]
                \item Oblicz resztę \( r_2 \):
                \[
                r_2 = r_0 - q \cdot r_1
                \]
                Zaktualizuj reszty:
                \[
                r_0 \leftarrow r_1, \quad r_1 \leftarrow r_2
                \]
                \item Zaktualizuj współczynniki \( s \) i \( t \):
                \[
                s_2 = s_0 - q \cdot s_1
                \]
                \[
                s_0 \leftarrow s_1, \quad s_1 \leftarrow s_2
                \]
                \[
                t_2 = t_0 - q \cdot t_1
                \]
                \[
                t_0 \leftarrow t_1, \quad t_1 \leftarrow t_2
                \]
            \end{enumerate}
            \item Gdy \( r_1 = 0 \), zwróć \( s_0 \) i \( t_0 \). Wtedy spełnione jest:
            \[
            ax + by = \gcd(a, b)
            \]
            gdzie \( x = s_0 \) i \( y = t_0 \).
        \end{enumerate}
    \end{algorithmic}
\end{orangebox}

\end{document}