%\documentclass[xcolor=dvipsnames]{beamer}
\documentclass[handout]{beamer}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usecolortheme{sidebartab}
%\input{makra-utf8}

\usetheme{Warsaw}
%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\title[Kongruence\hspace{15mm} \insertframenumber/\inserttotalframenumber]
{MB141 -- 11. přednáška \\Kongruence}
%\subtitle{}
\author[11. přednáška]{Martin Čadek\\ s využitím přednášek  pro předmět MB104}
\date{Jarní semestr 2022}

\begin{document}
\begin{frame}
\titlepage
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Osnova 11. přednášky}
\begin{itemize}
\item Kongruence a počítání s nimi
\bigskip
\item Malá Fermatova věta
\bigskip
\item Eulerova funkce a Eulerova věta
\bigskip
\item Řešení lineárních rovnic s kongruencemi
\bigskip
\item Čínská zbytková věta a řešení soustav lineárních kongruencí
\end{itemize}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\newtheorem{veta}{Věta}
%\newtheorem{hyp}{Hypot\'eza}
\newtheorem{reseni}{Řešení}
%\newtheorem{problemx}{Problem}
%\newtheorem{definition}{Definition}
%\newtheorem{lemma}{Lemma}
\theoremstyle{example}
\newtheorem{definice}{Definice}
\newtheorem{priklad}{P\v r\'iklad}
\newtheorem*{pozn}{Poznámka}
\newtheorem*{dusl}{Důsledek}
\def\cervena #1{{\color{red} #1}}
\def\cervene #1{{\color{red} #1}}
\def\modra #1{{\color{blue}  #1}}
\def\modre #1{{\color{blue}  #1}}
\xdefinecolor{tmavezelena}{cmyk}{0.7,0,1,0.5}
\def\zelena #1{{\color{tmavezelena}  #1}}
\def\zelene #1{{\color{tmavezelena}  #1}}
\def\c #1{\mathcal {#1}}
\def\s #1{\mathsf {#1}}
%\def\poznamka #1{{\footnotesize Pozn.: #1}\\}
\def\poznamka #1{{\scriptsize Pozn.: #1}\\}
\def\otazka #1{{\scriptsize Kontrolní otázka: #1}\\}
\def\zavorka #1{{\scriptsize [ #1 ]}\\}
\def\sami {{\scriptsize Vyřešte samostatně.}}
\def\ec {{\vec{e_1}}}
\def\ecc {{\vec{e_2}}}
\def\efc {{\vec{f_1}}}
\def\efcc {{\vec{f_2}}}

\def\rovina {{\mathbb R^2}}
\def\vect #1{{\overrightarrow{#1}}}
\def\skalar #1#2{{\langle #1, #2\rangle}}
\def\velikost #1{{\| #1\|}}
\def\sgn #1{{\operatorname{sgn}(#1)}}
\def\norm #1{\|#1\|}

\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\K{\mathbb K}
\def\Z{\mathbb Z}
\def\N{\mathbb N}
\def\C{\mathbb C}

\let\isom\cong
\let\divides\mid
\let\ndivides\nmid
\newcommand{\smalland}{\ \land\ }
\newcommand{\Sage}{\texttt{SAGE}\ }
\let\congr\equiv
\newcommand{\I}{\mathbb{I}}
\def\noqed{\renewcommand{\qedsymbol}{}}
\newcommand{\kron}[2]{(#1/#2)}
\newcommand{\kro}[2]{\genfrac{(}{)}{}{}{#1}{#2}}
%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

%\input definice-slovak.tex

\def\tuzka{\hfill ${\color{orange}\blacktriangleright \blacktriangleright}$}
%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Pojem kongruence}
  Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice
jednoduchý, jeho důležitost a užitečnost v~teorii čísel je
nedocenitelná; projevuje se zejména ve stručných a přehledných
zápisech některých i velmi komplikovaných úvah.

%\pause
\begin{definice}
  Jestliže dvě celá čísla $a,b$ mají při
dělení přirozeným číslem $m$ týž zbytek $r$, kde $0\leq r<m$,
nazývají se $a,b$  \cervene{kongruentní modulo m} (též
kongruentní podle modulu m), což zapisujeme takto:
$$a\congr b\pmod  m.$$
V~opačném případě řekneme, že $a,b$ nejsou kongruentní modulo
$m$, a píšeme $$a\not\congr b\pmod m.$$
\end{definice}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Kongruence jako ekvivalence}
\begin{lemma}
Pro libovolná $a,b\in\Z$,
$m\in\N$ jsou následující podmínky ekvivalentní:
\begin{enumerate}
\item $a\congr b\pmod m$,
\item $a=b+mt\quad\text{pro vhodné } t\in\Z$,
\item $m\divides a-b$.
\end{enumerate}
\end{lemma}
Přímo z~definice
plyne, že kongruence podle modulu $m$ je reflexivní (tj.
$a\congr a\pmod m$ platí pro každé $a\in\Z$), symetrická
(tj. pro každé $a,b\in\Z$ z~$a\congr b \pmod m$ plyne
$b\congr a \pmod m$) a
tranzitivní (tj. pro každé $a,b,c\in\Z$ z~$a\congr
b\pmod m$ a $b\congr c\pmod m$ plyne $a\congr
c\pmod m)$ relace, jde tedy o~\emph{ekvivalenci}.

\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Základní vlastnosti kongruencí I}

Ukážeme nyní další vlastnosti kongruencí, které jsou důležité při počítání:
    \begin{itemize}
 \item \cervene{Kongruence} podle téhož modulu \cervene{můžeme sčítat}. Libovolný
sčí\-ta\-nec můžeme přenést s~opačným znaménkem z~jedné strany
kongruence na druhou. \cervene{K~libovolné straně} kongruence \cervene{můžeme
přičíst} jakýkoliv \cervene{ná\-so\-bek modulu.}
\end{itemize}
\medskip

Je-li $a_1\congr b_1\pmod m$ a $a_2\congr
b_2\pmod m$, existují podle lemmatu 
 $t_1,t_2\in\Z$ tak, že
$a_1=b_1+mt_1$, $a_2=b_2+mt_2$. Pak ovšem
$a_1+a_2=b_1+b_2+m(t_1+t_2)$ a opět podle lemmatu  $a_1+a_2\congr
b_1+b_2\pmod m$. Sečteme-li kongruenci $a+b\congr
c\pmod m$ s~kongruencí $-b\congr -b\pmod m$, která
zřejmě platí, dostaneme $a\congr c-b\pmod m$. Sečteme-li
kongruenci $a\congr b\pmod m$ s~kongruencí $mk\congr
0\pmod m$, jejíž platnost je zřejmá, dostaneme $a+mk\congr b\pmod m$.
\end{frame}

\begin{frame}{Základní vlastnosti kongruencí II}
      \begin{itemize}
\item \cervene{Kongruence} podle téhož modulu \cervene{můžeme násobit}. Obě strany
kongruence je možné \cervene{umocnit na totéž přirozené číslo}. Obě strany
kongruence je možné \cervene{vynásobit stejným celým číslem}.
% \begin{proof}
%    Je-li $a_1\congr b_1\pmod m$ a $a_2\congr
% b_2\pmod m$, existují podle 
%  $t_1,t_2\in\Z$ tak, že
% $a_1=b_1+mt_1$, $a_2=b_2+mt_2$. Pak ovšem
% $$a_1a_2=(b_1+mt_1)(b_2+mt_2)=b_1b_2+m(t_1b_2+b_1t_2+mt_1t_2),$$
% odkud podle  dostáváme $a_1a_2\congr b_1b_2\pmod m$.

% Je-li $a\congr b\pmod m$, dokážeme indukcí vzhledem
% k~přirozenému číslu $n$, že platí $a^n\congr b^n\pmod m$. Pro $n=1$
% není co dokazovat. Platí-li $a^n\congr b^n\pmod m$ pro
% nějaké pevně zvolené $n$, vynásobením této kongruence a
% kongruence $a\congr b\pmod m$ dostáváme $a^n\cdot a\congr
% b^n\cdot b\pmod m$, tedy $a^{n+1}\congr
% b^{n+1}\pmod m$, což je tvrzení pro $n+1$. Důkaz indukcí je
% hotov.

% Jestliže vynásobíme kongruenci $a\congr b\pmod m$ a
% kongruenci $c\congr c\pmod m$, dosta\-ne\-me $ac\congr bc\pmod m$.
% \end{proof}


\item \cervene{Obě strany} kongruence \cervene{můžeme vydělit jejich společným
dě\-li\-te\-lem}, jestliže je tento dělitel \cervene{nesoudělný s~modulem.}
% \begin{proof}
%   Předpokládejme, že $a\congr b\pmod m$,
% $a=a_1\cdot d$, $b=b_1\cdot d$ a $(m,d)=1$. Podle lemmatu je rozdíl
% $a-b=(a_1-b_1)\cdot d$ dělitelný číslem $m$. Protože $(m,d)=1$,
% je podle  věty 
% \ref{veta:nesoudelnost} číslo $a_1-b_1$ také dělitelné číslem $m$,
% odtud podle lemmatu plyne $a_1\congr b_1\pmod m$.
% \end{proof}


\item Obě strany kongruence i její modul můžeme současně vynásobit tímtéž
přirozeným číslem.
% \begin{proof}
%   Je-li $a\congr b\pmod m$, existuje podle lemmatu
% celé číslo $t$ tak, že $a=b+mt$, odkud pro $c\in\N$ platí
% $ac=bc+mc\cdot t$, odkud opět podle lemmatu plyne $ac\congr bc\pmod{mc}$.
% \end{proof}

\item Obě strany kongruence i její modul můžeme vydělit jejich
spo\-leč\-ným kladným dělitelem.
% \begin{proof}
%   Předpokládejme, že $a\congr b\pmod m$,
% $a=a_1\cdot d$, $b=b_1\cdot d$, $m=m_1\cdot d$, kde $d\in\N$.
% Podle lemmatu
% existuje $t\in\Z$ tak, že $a=b+mt$, tj. $a_1\cdot d=b_1\cdot
% d+m_1dt$, odkud $a_1=b_1+m_1t$, což podle lemmatu znamená, že
% $a_1\congr b_1\pmod{m_1}$.
% \end{proof}
\end{itemize}
Důkazy těchto tvrzení se provádějí stejným způsobem jako důkaz z předchozí strany.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Základní vlastnosti kongruencí III}
\begin{itemize}
\item \cervene{Jestliže kongruence} $a\congr b$ \cervene{platí podle  modulů}
$m_1,\dots, m_k$, \cervene{platí i podle modulu, kterým je nejmenší společný
násobek} $[m_1,\dots, m_k]$ \cervene{těchto čísel.}
\end{itemize}

Jestliže $a\congr b\pmod{m_1}, a\congr
b\pmod{m_2},\dots, a\congr b\pmod{m_k}$, podle lemmatu je
rozdíl $a-b$ společný násobek čísel $m_1,m_2,\dots, m_k$ a tedy je
dělitelný jejich nejmenším společným násobkem $[m_1,m_2,\dots, m_k]$,
odkud plyne $a\congr b\pmod{[m_1,\dots, m_k]}$.

\begin{itemize}
\item Jestliže kongruence platí podle modulu $m$, platí podle
libovolného modulu $d$, který je dělitelem čísla $m$.
% \begin{proof}
%   Jestliže $a\congr b\pmod m$, je $a-b$
% dělitelné $m$, a proto také dělitelem $d$ čísla $m$, odkud
% $a\congr b\pmod d$.
% \end{proof}

\item Jestliže je jedna strana kongruence a modul dělitelný
nějakým celým číslem, musí být tímto číslem dělitelná i druhá
strana.% kongruence.
% \begin{proof}
%   Předpokládejme, že $a\congr b\pmod m$,
% $b=b_1d$, $m=m_1d$. Pak podle lemmatu existuje $t\in\Z$ tak, že
% $a=b+mt=b_1d+m_1dt=(b_1+m_1t)d$, a tedy $d\divides a$.
% \end{proof}
\end{itemize}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\begin{frame}{Poznámka a příklad 1}

Libovolné tvrzení používající kongruence můžeme snadno přepsat
pomocí dělitelnosti. Užitečnost kongruencí tedy netkví v~tom, že
bychom pomocí nich mohli řešit úlohy, které bez nich řešit nejsme
schopni, ale v~tom, že jde o~velmi vhodný způsob zápisu.
Osvojíme-li si ho, výrazně tím zjednodušíme jak vyjadřování, tak
i některé úvahy. Je to typický jev: v~matematice hraje vhodná
symbolika velmi závažnou úlohu.

\begin{priklad}[1]
  Nalezněte zbytek po dělení čísla $5^{20}$ číslem 26.
\end{priklad}


  Protože $5^2=25\congr-1\,\pmod{26}$, platí 
$$5^{20}=(5^2)^{10}\equiv(-1)^{10}=1\,\pmod{26},$$

a tedy zbytek po dělení čísla $5^{20}$ číslem 26 je jedna.

\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Příklady 2 a 3}
  
\begin{priklad}[2]
Dokažte, že pro libovolné $n\in\N$ je
$37^{n+2}+16^{n+1}+23^n$ dělitelné sedmi.
\end{priklad}

%\pause

Platí $37\equiv 16\equiv 23\equiv 2\,\pmod 7$,
a tedy podle základních vlastností kongruencí platí
$$37^{n{+}2}+16^{n{+}1}+23^n\equiv
2^{n{+}2}+2^{n{+}1}+2^n=2^n(4{+}2{+}1)%=2^n\cdot 7
\equiv 0\pmod 7.$$


%\pause
\begin{priklad}[3]
Dokažte, že číslo $n=(835^5+6)^{18}-1$ je dělitelné číslem 112.  
\end{priklad}

%\pause

  Rozložíme $112=7\cdot 16$. Protože $(7,16)=1$,
stačí ukázat, že $7\divides n$ a $16\divides n$. Platí $835\equiv
2\,\pmod 7$, a tedy 
\begin{multline*}
n\equiv(2^5+6)^{18}-1=38^{18}-1\equiv 3^{18}-1=\\=27^6-1\equiv(-1)^6-1
=0\,\pmod 7,
\end{multline*}
\end{frame}

\begin{frame}{Příklad 3}
proto $7\divides n$. Podobně $835\equiv 3\,\pmod{16}$, a tedy
\begin{multline*}
n\equiv(3^5+6)^{18}-1=(3\cdot 81+6)^{18}-1\equiv(3\cdot
1+6)^{18}-1=\\=9^{18}-1=81^9-1\equiv 1^9-1=0\,\pmod{16},  
\end{multline*}
proto $16\divides n$. Celkem tedy $112\divides n$, což jsme měli dokázat.

%\pause
\begin{priklad}
Najděte ``inverzi'' k číslu 39 modulo 47, tj.\ najděte $x$ takové, že $39 \cdot x \equiv 1 \pmod{47}$.
\end{priklad}
Počítáme $\pmod{47}$: $39\equiv -8$, proto $-8x\equiv 1$. Vynásobíme $6$ a odečteme $47x\equiv 0$, dostaneme $x\equiv -6\equiv 41$.
\end{frame}

\begin{frame}{Příklad 4}
\begin{priklad}[4]
Najděte ``inverzi'' k číslu 39 modulo 235, tj.\ najděte $x$ takové, že $39 \cdot x \equiv 1 \pmod{235}$.
\end{priklad}
Protože $235=5\cdot 47$ a čísla $5$ a $47$ jsou nesoudělná, je kongruence 
$39x\equiv 1\, \pmod{235}$ ekvivalentní se dvěma kongruencemi
 
$39x\equiv 1\, \pmod{47}$ a  $39x\equiv 1\, \pmod{5}$ 

Podle předchozí úlohy má prvá řešení $x\equiv 41\, \pmod{47}$. Řešení druhé je
 $x\equiv 4\, \pmod{5}$. Tedy podle prvé kongrunce je $x=47y+41$,
 dosazením do druhé dostaneme $47y+41\equiv 4\, \pmod{5}$, ekvivalentně 
 $2y+1\equiv 4\, \pmod{5}$, $2y\equiv 3\, \pmod{5}$, $2y\equiv =2\, \pmod{5}$,
 tedy $y\equiv -1\equiv 4\, \pmod{5}$. Tedy $y=5z+4$. Zpětným dosazením do
 $x$ dostaneme $x=47(5z+4)+41=235z+229\equiv 229$.
 
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\begin{frame}{Malá Fermatova věta}  

Tato  tvrzení  patří mezi nejdůležitější výsledky elementární teorie
 čísel. 

\begin{veta} [Malá Fermatova věta]
  Nechť $ p$ je prvočíslo a nechť  $a\in \Z$ je takové, že $p\ndivides a$.  Pak 
  \begin{displaymath}
a^{p-1}\congr  1\pmod p.
  \end{displaymath}
\end{veta}

 Prvně dokážeme indukcí, že $a^p\equiv a\, \pmod{p}$ pro všechna $a$ přirozená. 
 Pro $a=1$ to platí. Předpokládejme, že $a^p\equiv a$ pro nějaké $a\ge 1$. Potom pomocí binomické věty 
 $(a+1)^p=\sum_{k=0}^p\binom{p}{k}a^k\equiv a^p+1$,
 neboť pro všechna $k=1,2,\dots, p-1$ platí, že $p\mid \binom{p}{k}=\frac{p!}{k!(p-k)!}$ díky tomu, že $p$ je prvočíslo. Dále použijeme indukční předpoklad
 $(a+1)^p\equiv a^p+1\equiv a+1$.
 Platí-li, že $a^p\equiv a\, \pmod{p}$, pak číslem $a$, které není násobkem $p$, můžeme dělit a dostaneme $a^{p-1}\equiv 1\, \pmod{p}$.
 \end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\begin{frame}{Příklad 5}
Všimněte si, že jsme při důkazu dokázali $a^{p}\equiv a\, \pmod p$ pro všechna $a$.

\begin{priklad}[5]
Zjistěte zbytek po dělení čísla $21^{480}$  číslem $47$.
\end{priklad}
$47$ je prvočíslo. $47-1=46$ a $480=10\cdot 46+20$. Proto podle Fermatovy věty
dostáváme
$21^{480}=(21^{46})^{10}\cdot 21^{20}\equiv 1^{10}\cdot 21^{20}\equiv (21^2)^{10}\equiv
441^{10}\equiv 18^{10}\equiv (18^2)^5\equiv (-5)^5\equiv 625\cdot (-5)\equiv 14\cdot(-5)\equiv 24\, \pmod{47}$.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Eulerova funkce}
Malou Fermatovu větu lze zobecnit. K tomu budeme potřebovat Eulerovu funkci.
Je-li $p$ prvočíslo, pak počet celých čísel v intervalu $[1,p]$, která jsou nesoudělná s $p$ je $p-1$. To je  exponent vyskytující se ve Fermatově větě.  

\begin{definice}
  Nechť $n\in\N$.  Eulerovu funkci $\varphi$ definujeme jako počet celých čísel 
  v~intervalu $[1,n]$ nesoudělných s $n$,
$$\varphi(n)=|\{a\in\N\,|\, 0<a\leq n,\, (a,n)=1\}|$$
\end{definice}

%\pause
\begin{priklad}
  $\varphi(1)=1, \varphi(5)=4, \varphi(12)=4$, je-li p prvočíslo, je
  zřejmě $\varphi(p)=p-1$.
\end{priklad}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Výpočet Eulerovy funkce}
  
\begin{veta}
  Nechť $n\in\N$, jehož rozklad je tvaru $n=p_1^{\alpha_1}\cdots
  p_k^{\alpha_k}$. Pak 
 \begin{align*} 
\varphi(n)&=p^{\alpha_1-1}\cdots p_k^{\alpha_k-1}(p_1-1)\cdots(p_k-1)\\
&=n\cdot\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right)
\end{align*}
\end{veta}

  Předchozí výsledek lze obdržet  z následujících dvou tvrzení.
  \begin{itemize}
  \item
  Nechť $a,b\in\N,\,(a,b)=1$.  Pak $\varphi(a\cdot b)=\varphi(a)\cdot\varphi(b)$.
\item $ \varphi(p^\alpha)=p^\alpha-p^{\alpha-1}=(p-1)\cdot p^{\alpha-1}$.
  \end{itemize}

\begin{priklad}[6]
  Vypočtěte $\varphi(72)$. %Dokažte, že $\forall n\in\N:\, \varphi(4n+2)=\varphi(2n+1)$.
\end{priklad}


  $72=2^3\cdot3^2 \implies
  \varphi(72)=72\cdot(1-\frac{1}{2})\cdot(1-\frac{1}{3})=24$, alternativně
  $\varphi(72)=\varphi(8)\cdot\varphi(9)=4\cdot6=24$.

%$\varphi(4n+2)=\varphi(2\cdot(2n+1))=\varphi(2)\cdot \varphi(2n+1)=\varphi(2n+1)$.

\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Eulerova věta}
\begin{veta}[Eulerova]
  Nechť $a\in\Z,\, m\in\N,\, (a,m)=1$.  Pak 
  \begin{displaymath}
a^{\varphi(m)}\congr  1\pmod m.
  \end{displaymath}
\end{veta}

%\pause
S~Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem \emph{řád
  čísla modulo $m$}:

\begin{definice}
  Nechť $a\in\Z,\, m\in\N\; (a,m)=1$.  \cervene{Řádem čísla $a$ modulo $m$}
  rozumíme nejmenší přirozené číslo $n$ splňující $$a^n\congr 1\pmod m.$$
\end{definice}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Primitivní kořeny}

  To, že je řád definován, plyne z~Eulerovy věty -- pro každé číslo
  nesoudělné s~modulem je totiž jistě jeho řád nejvýše roven
  $\varphi(m)$.  Velmi důležitá jsou právě ta čísla,
  jejichž řád je roven právě $\varphi(m)$ -- tato čísla nazýváme
  \cervene{primitivními kořeny modulo $m$}.
  
  \begin{priklad}[7]
  Určete řád čísla 2 modulo 7.
\end{priklad}
%\pause
Řešení:
  \begin{gather*}
    2^1=2\not\congr 1\pmod7\\
    2^2=4\not\congr 1\pmod7\\
    2^3=8\congr 1\pmod7\\
  \end{gather*}
  Řád čísla 2 modulo 7 je tedy roven 3.

%\pause
%\begin{priklad}
 %Pro libovolné $m\in\N$ má číslo 1 modulo $m$ řád 1.  Číslo
   % $-1$ má řád
    %\begin{itemize}
    %\item 1 pro $m=1$ nebo $m=2$
    %\item 2 pro $m>2$
    %\end{itemize}
%\end{priklad}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

%\begin{frame}{Příklad 7}

%\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}
  \frametitle{Lineární kongruence o jedné neznámé}
   \begin{veta}
Nechť $m\in\N,\, a,b\in\Z$.  Označme $d=(a,m)$.  Pak kongruence
$$ax\congr b\pmod m$$
(o~jedné neznámé $x$) má řešení právě tehdy, když $d\divides b$.

Pokud platí $d\divides b$, má tato kongruence právě $d$ řešení
(modulo $m$).
\end{veta}

Řešením modulo $m$ myslíme zbytkovou třídu. Např. zbytková třída $3 \pmod 7$
je množina $\{7k+3\in\Z;\ k\in\Z\}$.  
%\pause
\begin{priklad}
  \begin{enumerate}
  \item Kongruence $2x\equiv 1\pmod 3$ má jedno řešení (modulo 3).
  \item  Kongruence $10x\equiv 5\pmod{15}$ má pět řešení (modulo 15).
   \end{enumerate}
\end{priklad}

\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Důkaz}
Kongruence $2x\equiv 1\pmod 3$ má  řešení $x\equiv 2\, \pmod 3$. Kongruence $10x\equiv 5\pmod{15}$ má  řešení $2$, $3+2=5$, $6+2=8$, $9+2=11$, $12+2=14\, \pmod{15}$.

\medskip
Důkaz předchozí věty provedeme pomocí Eulerovy věty:

\medskip
  Dokážeme nejprve, že uvedená podmínka je nutná. Je-li celé číslo $c$
  řešením této kongruence, pak nutně $m\divides a\cdot c-b$. Pokud 
  $d=(a,m)$, pak  $d$ dělí také  $a\cdot c-b$. A protože dělí $a$, musí dělit také $b$.

\medskip    
Obráceně dokážeme: pokud $d\divides b$, pak má daná kongruence právě $d$
  řešení modulo $m$. Označme $a_1, b_1\in\Z$ a $m_1\in \N$ tak, že 
  $a=d\cdot a_1$, $b=d\cdot b_1$ a $m=d\cdot m_1$.  Řešená kongruence
  je tedy ekvivalentní s~kongruencí $$a_1\cdot x\congr
  b_1\pmod{m_1},$$ kde $(a_1,m_1)=1$. 
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Dokončení důkazu}
  
       Tuto kongruenci můžeme
  vynásobit číslem $a_1^{\varphi(m_1)-1}$ a díky Eulerově větě obdržíme 
  $$x\equiv a_1^{\varphi(m_1)}\cdot x\equiv   a_1^{\varphi(m_1)-1}\cdot b_1\pmod{m_1}.$$  Tato
  kongruence má jediné řešení modulo $m_1$ a tedy $d=m/m_1$ řešení
  modulo m. Ta jsou  $a_1^{\varphi(m_1)-1}\cdot b_1+km_1$, kde $k=0,1,2,\dots,d-1$.
  
 \medskip
  Následující příklad ukáže, že postup uvedený v~důkazu věty obvykle
není tím nejefektivnějším -- s~výhodou lze použít jak Bezoutovu větu,
tak ekvivalentní úpravy řešené kongruence.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Příklad 8}

%\pause
  \begin{priklad}[8]
      Řešte $39x\congr41\pmod{47}$
\end{priklad}

%\pause
\begin{enumerate}
\item[(1)] Nejprve využijeme Eulerovu větu, stejně jako v důkazu.
\item[(2)] Další možností je využít Bezoutovu větu. Najdeme $a,b\in\Z$ tak, že
$39a+47b=1$. Pak vynásobíme číslem  $41$. Řešení je $x\equiv 41a$. 
\item[(3)] Obvykle nejrychlejším, ale nejhůře algoritmizovatelným
  způsobem řešení je metoda takových úprav kongruence, které
  zachovávají množinu řešení.
\begin{align*}
\onslide<6->{39x\congr41\pmod{47}&\iff -8x\congr-6\pmod{47}\iff\\}
\onslide<7->{ 4x\congr3\pmod{47}&\iff 4x\congr-44\pmod{47}\iff\\}
\onslide<8->{     x\congr-11\pmod{47}&\iff x\congr36\pmod{47}}
  \end{align*}
\end{enumerate}
Více ve cvičení.

\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\begin{frame}
  \frametitle{Soustavy lineárních kongruencí}
  Máme-li soustavu lineárních kongruencí o~téže neznámé, můžeme
podle předchozí věty rozhodnout o~řešitelnosti každé z~nich. V~případě, kdy aspoň jedna
z~kongruencí nemá řešení, nemá řešení ani celá soustava. Naopak,
jestliže každá z~kongruencí řešení má, upravíme ji do tvaru
$x\equiv c_i \pmod{m_i}$. \pause Dostaneme tak soustavu kongruencí
\begin{align*}
x&\equiv c_1\pmod{m_1}\notag\\
&\mskip10mu\vdots\\
x&\equiv c_k\pmod{m_k}\notag
\end{align*}

%\pause
Zřejmě stačí vyřešit případ $k=2$, 
řešení soustavy více kongruencí snadno obdržíme opakovaným řešením soustav dvou kongruencí.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Řešení soustav lineárních kongruencí}
  \begin{veta}
  Nechť $c_1,c_2$ jsou celá čísla, $m_1,m_2$
přirozená. Označme $d=(m_1,m_2)$. Soustava dvou kongruencí
\begin{align*}
x&\equiv c_1\pmod{m_1}\\
x&\equiv c_2\pmod{m_2}
\end{align*}
v~případě $c_1\not\equiv c_2 \pmod{d}$ nemá řešení. Jestliže
naopak $c_1\equiv c_2 \pmod{d}$, pak existuje celé číslo $c$ tak, že
$x\in\Z$ vyhovuje soustavě, právě když vyhovuje kongruenci
$$x\equiv c\pmod{[m_1,m_2]}.$$
\end{veta}

%\pause

  Má-li soustava  nějaké řešení $x\in\Z$, platí
nutně $x\equiv c_1 \pmod{d}$, $x\equiv c_2 \pmod  d$,
a tedy i $c_1\equiv c_2 \pmod{d}$. 
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Náznak důkazu}
  Předpokládejme dále $c_1\equiv c_2 \pmod{d}$. První kongruenci
řešené soustavy vyhovují všechna celá čísla $x$ tvaru $x=c_1+tm_1$,
kde $t\in\Z$ je libovolné. Toto $x$ bude vyhovovat i druhé
kongruenci soustavy, právě když bude platit $c_1+tm_1\equiv
c_2 \pmod{m_2}$, tj.
$tm_1\equiv c_2-c_1\pmod{m_2}.$ %\pause
Podle věty o řešitelnosti lineárních kongruencí má tato kongruence (vzhledem k~$t$) řešení, neboť
$d=(m_1,m_2)$ dělí $c_2-c_1$.

%, a $t\in\Z$ splňuje tuto kongruenci
%právě když
%$$t\equiv\frac{c_2-c_1}d\cdot\left ( %\frac{m_1}d\right)^{\varphi(\frac{m_2}d)-1}\left(\text{mod}{\;%\frac{m_2}d}\right),$$
%\pause
%tj. právě když
%$$t=\frac{c_2-%c_1}d\cdot\left(\frac{m_1}d\right)^{\varphi(\frac{m_2}d)-1}+r\cdot\frac{m_2}d,$$
% kde $r\in\Z$ je libovolné. Dosazením
%$ x=c_1+tm_1=c_1+(c_2-c_1)\cdot\left(
%\frac{m_1}d\right)^{\varphi(\frac{m_2}d)}
%+r\frac{m_1m_2}d=c+r\cdot[m_1,m_2],$
%kde $r\in\Z$ je libovolné a $c=c_1+(c_2-c_1)\cdot(m_1/d)^{\varphi(m_2/d)}$, neboť
%$m_1m_2=d\cdot[m_1,m_2]$. Našli jsme tedy takové
%$c\in\Z$, že libovolné $x\in\Z$ splňuje soustavu, právě když
%$x\equiv c\pmod{[m_1,m_2]},$
%což jsme chtěli dokázat.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}
  \frametitle{Čínská zbytková věta}



Ve čtvrtém století se  čínský matematik Sun Ze (Sun Tsu)  ptal na číslo, které při dělení třemi dává zbytek 2, při dělení pěti zbytek 3 a při dělení sedmi je zbytek opět 2.

%\begin{reseni}
  %Odpověď je (prý) ukryta v následující písni:
%
%\pause
%\centerline{\resizebox{4cm}{!}{\includegraphics{sunzige.png}}}
%
%\end{reseni}


\begin{veta}[Čínská zbytková věta]
  Nechť $m_1,,\dots, m_k\in\N$ jsou po dvou nesoudělná, $a_1,\dots,
  a_k\in\Z$.  Pak platí: soustava
  \begin{align*}
      x&\equiv a_1\pmod{m_1}\\
      &\vdots\\
      x&\equiv a_k\pmod{m_k}
  \end{align*}
má jediné řešení modulo $m_1\cdot m_2 \cdots m_k$.
\end{veta}

%\pause
  Řešení  hledáme stejně jako v předchozím důkazu, jak uvidíte v~následujícím příkladu.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Příklad 9}
 
\begin{priklad}[9]
      Řešte systém kongruencí
    \begin{align*}
x&\equiv 1\pmod{10}\\
x&\equiv 5\pmod{18}\\
x&\equiv -4\pmod{25}.
\end{align*}
\end{priklad}

%\pause
Řešení: Z první kongruence plyne, že $x=10y+1$. Dosazením do druhé kongruence dostaneme $10y\equiv 4\, \pmod{18}$, ekvivalentně $5y\equiv 2\, \pmod{9}$.
Řešení je  $y=9z+4$, proto $x=90z+41$. Dosazením do poslední kongruence dostaneme $90z\equiv -45\, \pmod{25}$, ekvivalentně $18z\equiv -9\, \pmod{5}$, vydělíme $9$ a dostaneme $2z\equiv -1\, \pmod{5}$. Tedy $z=5a+2$. Dosazením
$x=90(5a+2)+41=450a+180+41\equiv 221\, \pmod{450}$.  
  Výsledkem je $x\equiv 221 \pmod{450}$.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Příklad 10}
  Čínskou zbytkovou větu můžeme použít také \uv{v opačném směru}.

 \begin{priklad}[10]
    Řešte kongruenci $23\,941x\equiv 915 \pmod{3 564}$.
  \end{priklad}

%\pause
      Rozložme $3564=2^2\cdot 3^4\cdot 11$. Protože ani
2, ani 3, ani 11 nedělí číslo $23\,941$, platí $(23\,941,3564)=1$ a
má tedy  kongruence řešení. Protože
$\varphi(3564)=2\cdot(3^3\cdot 2)\cdot 10=1080$,  je
řešení tvaru $x\equiv 915\cdot 23\,941^{1079} \pmod{3 564}$.
Úprava
čísla stojícího na pravé straně by však vyžádala značné úsilí.
Proto budeme kongruenci řešit poněkud jinak.

\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Dokončení příkladu 10}
 
    Víme, že $x\in\Z$ řešením dané kongruence, právě když je řešením soustavy
\begin{align*}
 23941x&\equiv 915\pmod{2^2}\\
23941x&\equiv 915\pmod{3^4}\\
23941x&\equiv 915\pmod{11}.
\end{align*}

%\pause
Vyřešíme-li postupně každou z kongruencí soustavy, dostaneme ekvivalentní soustavu
\begin{align*}
  x&\equiv 3\pmod{4}\\
x&\equiv -3\pmod{81}\\
x&\equiv -4\pmod{11},
\end{align*}
%\pause
odkud snadno postupem pro řešení soustav kongruencí dostaneme $x\equiv -1137 \pmod{3 564}$, což je také řešení zadané kongruence.
 
\end{frame}


\end{document}