%\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[Celá čísla a dělitelnost\hspace{15mm} \insertframenumber/\inserttotalframenumber]
{MB141 -- 10. přednáška \\Celá čísla a dělitelnost}
%\subtitle{}
\author[10. 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}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\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
\newcommand{\maticemn}[1]{
\left(
\begin{array}{llll}
#1_{11}&#1_{12}&\dots&#1_{1n}\\
#1_{21}&#1_{22}&\dots&#1_{2n}\\
\vdots&\vdots&&\vdots\\
#1_{m1}&#1_{m2}&\dots&#1_{mn}\\
\end{array}
\right)}

\newcommand{\maticedvadva}[4]{
\left(
\begin{array}{rr}
#1&#2\\
#3&#4\\
\end{array}
\right)}

%\newcommand{\maticedvatri}[6]{
%\left(
%\begin{array}{rrr}
%#1&#2&#3\\
%#4&#5&#6\\
%\end{array}
%\right)}

\newcommand{\maticedvatri}[6]{
\left(
\begin{smallmatrix} 
#1&#2&#3\\
#4&#5&#6
\end{smallmatrix} \right)}


\newcommand{\sloupecdva}[2]{
\left(
\begin{array}{l}
#1\\
#2\\
\end{array}
\right)}
%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx



\begin{frame}
  \frametitle{Doporučené zdroje k teorii čísel}
  \begin{itemize}
  \item Jan Slovák, Martin Panák, Michal Bulant \\
\textbf{Matematika drsně a svižně}, $e$-text na
\url{www.math.muni.cz/Matematika\_drsne\_svizne}.
%\item \textit{resp. v předmětových záložkách v~IS MU}
%\pause
\item Michal Bulant, výukový text k přednášce \textbf{Elementární teorie čísel}, \url{http://is.muni.cz/el/1431/podzim2019/M6520/um/main-print.pdf}
%\item Jiří Herman, Radan Kučera, Jaromír Šimša, \textbf{Metody řešení matematických úloh}. MU Brno, 2001.
\item William Stein, \textbf{Elementary Number Theory: Primes, Congruences, and Secrets}, Springer, 2008. Dostupné na \url{http://wstein.org/ent/ent.pdf}
\item Radan Kučera, výukový text k přednášce \textbf{Algoritmy teorie čísel}, \url{http://www.math.muni.cz/~kucera/texty/ATC2014.pdf}
\item Adam Spencer, \textbf{Why I fell in love with monster prime numbers}, video, 17 minut,
\url{ https://www.ted.com/talks/adam_spencer_why_i_fell_in_love_with_monster_prime_numbers}
\end{itemize}
\end{frame}


%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Osnova 10. přednášky}
\begin{itemize}
\item Dělitelnost a dělení se zbytkem
\bigskip
\item Největší společný dělitel, Eukleidův algoritmus
\bigskip
\item Bezoutova věta
\bigskip
\item Nesoudělnost
\bigskip
\item Prvočísla, rozklad čísel na prvočísla
\end{itemize}
\end{frame}


\begin{frame}{Problémy teorie čísel}

Přirozená a celá čísla jsou nejjednodušší matematickou strukturou, 
zkoumání jejich
vlastností však postavilo před generace matematiků celou řadu velice
obtížných problémů. 

\bigskip 
Často jsou to problémy, které je možno snadno
formulovat, přesto však dodnes neznáme jejich řešení. 

\bigskip 
V několika přednáškách se teď budeme zabývat úlohami o~celých číslech.
Převážně v~nich půjde o~dělitelnost celých čísel, popřípadě
o~řešení rovnic v~oboru celých nebo přirozených čísel. 

\bigskip
\cervene{  \begin{flushright}
    \textit{God made integers, all else is the work of man. (L. Kronecker)}
  \end{flushright}}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}\frametitle{Příklady problémů teorie čísel}

\begin{itemize}[<+->]
\item {\it problém prvočíselných dvojčat\/} -- rozhodnout, zda existuje nekonečně mnoho prvočísel $p$ takových,
že i $p+2$ je prvočíslo,
\item \textit{problém existence lichého dokonalého čísla} -- tj. čísla jehož součet dělitelů je roven dvojnásobku tohoto čísla
\item {\it Goldbachova hypotéza\/}
(rozhodnout, zda každé sudé číslo větší než 2 je možno psát jako
součet dvou prvočísel), 
\item {\it velká Fermatova věta\/} (Fermat's Last Theorem) -- rozhodnout, zda existují přirozená
čísla $n$, $x$, $y$, $z$ tak, že $n>2$  a platí $x^n+y^n=z^n$; Pierre de Fermat jej formuloval cca 1637, vyřešil Andrew Wiles v roce 1995.
\end{itemize}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Diofantické rovnice}
  V kouzelném měšci máme neomezené množství dvoukorun a pětikorun. Jaké částky můžeme zaplatit tak, aby nebylo potřeba vracet?

\medskip\pause
Ptáme se tedy, pro která přirozená čísla $n$ existují přirozená $k$, $\ell$ tak, aby
$$2k+5\ell=n.$$ 
 
Asi se dá vcelku snadno uvěřit, že libovolnou vyšší částku takto zaplatíme, po pravdě jakoukoliv častku s výjimkou 1\,Kč a 3\,Kč.

%\pause
S vracením pak zvládneme zaplatit libovolnou částku, tj.\ každé $n$ lze vyjádřit jako
$$2k+5\ell=n$$ 
pro nějaká celá $k$, $\ell$.

Umíme to pro jakékoliv hodnoty mincí? 
Jak by to dopadlo třeba pro $7k + 11\ell = n$?
A jak pro $2k + 4\ell = n$?
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Dělitelnost}
\begin{definice}
Řekneme, že celé číslo $a$ {\it
dělí\/} celé číslo $b$ (neboli číslo $b$ je {\it dělitelné\/}
číslem $a$, též $b$ je {\it násobek\/} $a$), právě když existuje
celé číslo $c$ tak, že platí $a\cdot c=b$. Píšeme pak $a\divides b$.
\end{definice}

%\pause
Přímo z~definice plyne několik jednoduchých tvrzení
%, jejichž
%důkaz přenecháváme čtenáři jako cvičení s~návodem v~\cite[\S 12]{hks:metody_i}
: Číslo
nula je dělitelné každým celým číslem; jediné celé číslo, které
je dělitelné nulou, je nula; pro libovolné číslo $a$  platí
$a\divides a$; %\pause 
pro libovolná čísla $a,b,c$ platí tyto čtyři implikace:

\begin{align*}
  a\divides b \smalland b\divides c \,&\implies\, a\divides c\\
a\divides b\smalland a\divides c\,&\implies\, a\divides b+c\smalland a\divides b-c\\
c\ne 0\,&\implies\,(a\divides b\Longleftrightarrow ac\divides bc)\\
a\divides b\smalland b>0\,&\implies\, a\leq b
\end{align*}
  
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Příklady}
\begin{priklad}
Zjistěte, pro která přirozená čísla $n$ je číslo
$n^2+1$ dělitelné číslem $3$.  
\end{priklad}

%\pause

Uvidí se, že záleží pouze na zbytku $n$ po dělení třemi.


%\pause
\begin{priklad}
Zjistěte, pro která přirozená čísla $n$ je číslo
$n^2+1$ dělitelné číslem $n+1$.  
\end{priklad}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
\begin{frame}{Dělení se zbytkem}

\begin{veta}[o~dělení celých čísel se zbytkem]
\label{veta:del-se-zbytkem}
Pro
libovolně zvolená čísla $a\in\Z$, $m\in\N$ existují jednoznačně určená
čísla $q\in\Z$, $r\in\{0,1,\dots, m-1\}$ tak, že $a=qm+r$.
\end{veta}

%\pause

Důkaz indukcí: pro $a < m$ zřejmé, pro $a \geq m$ pak rekurzivně s využitím výsledku pro $a - m$ (podíl je potřeba zvětšit o 1, zbytek zůstane stejný).

\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Dělení se zbytkem -- pokračování}
Číslo $q$, resp. $r$  z~věty  se nazývá {\it (neúplný)
podíl\/}, resp. {\it zbytek\/} při dělení čísla $a$ číslem $m$
se zbytkem. Vhodnost obou názvů je zřejmá, přepíšeme-li rovnost
$a=mq+r$ do tvaru
$$\frac am=q+\frac rm,\quad\text{přitom}\quad 0\leq\frac rm<1.$$
% Je vhodné též si uvědomit, že z~věty  plyne, že číslo $m$ dělí
% číslo $a$, právě když zbytek $r$ je roven nule.

%\pause  
% \end{frame}
% \begin{frame}
\begin{priklad}\label{prikl:zbytek1}
Dokažte, že jsou-li zbytky po dělení čísel $a,b\in\Z$ číslem
$m\in\N$ jedna, je jedna i zbytek po dělení čísla $ab$ číslem $m$.  
\end{priklad}

%\pause
%\begin{reseni}
  %Podle Věty o dělení se zbytkem  existují $s,t\in\Z$ tak, že
%$a=sm+1$, $b=tm+1$. Vynásobením dostaneme 
%$$ab=(sm+1)(tm+1)=(stm+s+t)m+1=qm+r,$$
%kde $q=stm+s+t$, $r=1$, které je podle téže věty 
 %jednoznačné, a tedy
%zbytek po dělení čísla $ab$ číslem $m$ je jedna.\qed
%\end{reseni}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}\frametitle{Největší společný dělitel (gcd)}
  Jedním z nejdůležitějších nástrojů výpočetní teorie čísel je výpočet největšího společného dělitele. Protože jde, jak si ukážeme, o~relativně rychlou proceduru, je i v moderních algoritmech velmi často využívána.

%\pause
\begin{definice}
Měj\-me celá čísla $a_1,a_2$.  Libovolné celé číslo $m$
takové, že $m\divides a_1$, $m\divides a_2$ se nazývá {\it společný dělitel\/} čísel $a_1,a_2$. Společný dělitel 
$m\geq 0$ čísel $a_1,a_2$, který je dělitelný libovolným
společným dělitelem čísel
$a_1,a_2$, se nazývá {\it největší společný dělitel\/} čísel $a_1,a_2$ a značí se
$(a_1,a_2)$.
\end{definice}

%\pause
Například $(12,64) = 4$.
  
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Nejmenší společný násobek}

\begin{definice}
Měj\-me celá čísla $a_1,a_2$.  Libovolné celé číslo $m$
takové, že $a_1\divides m$, $a_2\divides
m$ se nazývá {\it společný
násobek\/} čísel $a_1,a_2$. Společný násobek
$m\geq 0$ čísel $a_1,a_2$, který dělí libovolný společný násobek čísel
$a_1,a_2$, se nazývá 
{\it nejmenší společný násobek\/} čísel $a_1,a_2$ a značí se
$[a_1,a_2]$.
\end{definice}

%\pause
\begin{pozn}
Přímo z~definice plyne, že pro libovolné $a,b\in\Z$ platí
$(a,b)=(b,a)$, $[a,b]=[b,a]$, $(a,1)=1$, $[a,1]=\vert a\vert$,
$(a,0)=\vert a\vert$, $[a,0]=0$. 
Analogicky se definuje  i největší
společný dělitel a nejmenší společný násobek více než dvou celých čísel a snadno se následně dokáže, že platí 
\begin{align*}
  (a_1,\ldots, a_n)&=((a_1,\ldots,a_{n-1}),a_n)\\
  [a_1,\ldots, a_n]&=[[a_1,\ldots,a_{n-1}],a_n]\\
\end{align*}
\end{pozn}

\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Euklidův algoritmus}

Dosud jsme nijak nezdůvodnili, zda pro
každou dvojici $a,b\in\Z$ čísla $(a,b)$ a $[a,b]$ vůbec existují. To si lze hezky představit přes rozklad na prvočinitele, ale ten je výpočetně velmi náročný (RSA) a navíc k jeho odvození budeme existenci největšího společného dělitele využívat.

%\pause
Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla
$m_1,m_2\in\N_0$ totiž podle definice platí, že pokud $m_1\divides m_2$ a
zároveň $m_2\divides m_1$, je nutně $m_1=m_2$. Důkaz existence čísla
$(a,b)$ podáme (spolu s~algoritmem jeho nalezení) v následující větě.


%\pause
\begin{veta}[Euklidův algoritmus]
\label{veta:euklid}
  Nechť $a_1,a_2$ jsou
přirozená čísla. Pro každé $n\geq 3$, pro které $a_{n-1}\ne0$,
označme $a_n$ zbytek po dělení čísla $a_{n-2}$ číslem $a_{n-1}$.
Pak po konečném počtu kroků dostaneme $a_k=0$ a platí $a_{k-1}=(a_1,a_2)$.
\end{veta}
\end{frame}

%\begin{frame}
%\begin{proof}
%Podle Věty o dělení se zbytkem platí $a_2>a_3>a_4>\dots$. Protože jde
%o~nezáporná celá čísla, je každé následující alespoň o~1 menší než
%předchozí, a proto po určitém konečném počtu kroků dostáváme
%$a_k=0$, přičemž $a_{k-1}\ne 0$. Z~definice čísel $a_n$ plyne, že
%existují celá čísla $q_1,q_2,\dots, q_{k-2}$ tak, že  
%\begin{align*}
    %a_1&=q_1\cdot a_2+a_3,\\
%%a_2&=q_2\cdot a_3+a_4,\\
%&\vdots\\
%a_{k-3}&=q_{k-3}\cdot a_{k-2}+a_{k-1}\\
%a_{k-2}&=q_{k-2}\cdot a_{k-1}.
%\end{align*}
%Z~poslední rovnosti plyne, že $a_{k-1}\divides a_{k-2}$,
%dále $a_{k-1}\divides a_{k-3}$, atd., je
%tedy $a_{k-1}$ společný dělitel čísel $a_1,a_2$. Naopak jejich
%libovolný společný dělitel dělí i číslo $a_3=a_1-q_1a_2$, proto i
%$a_4=a_2-q_2a_3,\dots$, a proto i
%$a_{k-1}=a_{k-3}-q_{k-3}a_{k-2}$. Dokázali jsme, že $a_{k-1}$ je
%největší společný dělitel čísel $a_1,a_2$.
%\end{proof}
%\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Euklidův algoritmus -- příklad}

Algoritmus a důkaz jeho korektnosti demonstrujeme na příkladu:

\begin{priklad}
Určete největšího společného dělitele čísel 10175 a 2277.
\end{priklad}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Vlastnosti největšího společného dělitele}


Z definice, z předchozího tvrzení a z toho, že pro libovolná
$a,b\in\Z$ platí $(a,b)=(a,-b)=(-a,b)=(-a,-b)$, plyne, že existuje
největší společný dělitel libovolných dvou celých čísel.

  
%\pause
\begin{veta}[Bezoutova]\label{veta:bezout}
  Pro libovolná celá čísla
$a_1,a_2$ existuje jejich největší společný dělitel $(a_1,a_2)$,
přitom existují celá čísla $k_1,k_2$ tak, že $(a_1,a_2)=k_1a_1+k_2a_2$.
\end{veta}

%\pause
\begin{dusl}
Pro libovolná celá čísla $a_1,a_2$ lze jako celočíselné kombinace $n=k_1a_1+k_2a_2$ vyjádřit právě násobky největšího společného dělitele $(a_1, a_2)$.
\end{dusl}

Ukázat praktický výpočet pro $a_1=10175$, $a_2=2277$. 
\end{frame}

%\begin{frame}
%\begin{proof}
  %Jistě stačí větu dokázat pro $a_1,a_2\in\N$.
%Všimněme si, že jestliže je možné nějaká čísla $r,s\in\Z$
%vyjádřit ve tvaru $r=r_1a_1+r_2a_2$, $s=s_1a_1+s_2a_2$, kde
%$r_1,r_2,s_1,s_2\in\Z$, můžeme tak vyjádřit i
%$$r+s=(r_1+s_1)a_1+(r_2+s_2)a_2$$
%a také
%$$c\cdot r=(c\cdot r_1)a_1+(c\cdot r_2)a_2$$
%pro libovolné $c\in\Z$. Protože $a_1=1\cdot a_1+0\cdot a_2$,
%$a_2=0\cdot a_1+1\cdot a_2$, plyne z~(5), že takto můžeme
%vyjádřit i $a_3=a_1-q_1a_2$, $a_4=a_2-q_2a_3$, \dots,
%$a_{k-1}=a_{k-3}-q_{k-3}a_{k-2}$, což je ovšem $(a_1,a_2)$.
%\end{proof}
%\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Příklad}
\begin{priklad}
  Výpočet největšího společného dělitele pomocí Euklidova algoritmu je s~využitím výpočetní
  techniky i pro relativně velká čísla poměrně rychlý. V~našem
  příkladu to vyzkoušíme na 2 číslech A,B, z~nichž každé je součinem dvou
  101-ciferných prvočísel.  Všimněme si, že výpočet největšího
  společného dělitele i takto velkých čísel trval zanedbatelný čas.

  Příklad v systému \Sage lze vyzkoušet na \url{https://cocalc.com/}.


\end{priklad}

  Euklidův algoritmus a Bezoutova věta jsou základními
  výsledky elementární teorie čísel a tvoří jeden z~pilířů
  algoritmů algebry a teorie čísel. 


\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}
\frametitle{Nejmenší společný násobek}

\begin{veta}
  \label{veta:nsd-nsn-vztah}
Pro libovolná celá čísla $a_1,a_2$
existuje jejich nejmenší společný násobek $[a_1,a_2]$ a platí
$(a_1,a_2)\cdot[a_1,a_2]=\vert a_1\cdot a_2\vert$.
\end{veta}

%\pause
\begin{proof}
Nejlépe se vidí přes rozklad na součin prvočísel.
\end{proof}
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}
  \frametitle{Nesoudělnost}
  \begin{definice}
Čísla $a_1,a_2,\dots, a_n\in\Z$ se
nazývají {\it nesoudělná}, jestliže platí  $(a_1,a_2,\dots, a_n)=1$. Čísla
$a_1,a_2,\dots, a_n\in\Z$ se nazývají {\it po dvou nesoudělná},
jestliže pro každé $i,j$ takové, že $1\leq i<j\leq n$, platí $(a_i,a_j)=1$.
\end{definice}


  V~případě $n=2$ oba pojmy splývají, pro $n>2$ plyne
z~nesoudělnosti po dvou nesoudělnost, ne však naopak: například
čísla $6$, $10$, $15$ jsou nesoudělná, ale
nejsou nesoudělná po dvou, neboť
dokonce žádná dvojice
z~nich vybraná nesoudělná není: $(6,10) = 2$, $(6,15) = 3$, $(10,15) =
5$.
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Nesoudělnost -- důležité vlastnosti}
  \begin{veta}\label{veta:nesoudelnost}
  Pro libovolná přirozená čísla $a,b,c$ platí
  \begin{enumerate}
  \item $(ac,bc)=(a,b)\cdot c$,
  \item jestliže $a\divides bc$, $(a,b)=1$, pak $a\divides c$,
  \item $d=(a,b)$ právě tehdy, když existují $q_1,q_2\in\N$ tak, že
$a=dq_1$, $b=dq_2$ a $(q_1,q_2)=1$.
  \end{enumerate}
\end{veta}
\end{frame}
%\begin{frame}
%\begin{proof}
  %ad 1. Protože $(a,b)$ je společný dělitel čísel $a,b$,
%je $(a,b)\cdot c$ společný dělitel čísel $ac$, $bc$, proto
%$(a,b)\cdot c\divides(ac,bc)$. Podle Bezoutovy věty
  %existují $k,l\in\Z$ tak, že
%$(a,b)=ka+lb$. Protože $(ac,bc)$ je společný dělitel čísel $ac$,
%$bc$, dělí i číslo $kac+lbc=(a,b)\cdot c$. Dokázali jsme, že
%$(a,b)\cdot c$ a $(ac,bc)$ jsou dvě přirozená čísla, která dělí
%jedno druhé, proto se rovnají.
%
%\pause
%ad 2. Předpokládejme, že $(a,b)=1$ a $a\divides bc$. Podle Bezoutovy věty 
%existují $k,l\in\Z$ tak, že $ka+lb=1$, odkud plyne, že
%$c=c(ka+lb)=kca+lbc$. Protože $a\divides bc$, plyne odsud, že i
%$a\divides c$.
%
%\pause
%ad 3. Nechť $d=(a,b)$, pak existují $q_1,q_2\in\N$ tak, že
%$a=dq_1$, $b=dq_2$. Pak podle 1. části  platí
%$d=(a,b)=(dq_1,dq_2)=d\cdot(q_1,q_2)$, a tedy $(q_1,q_2)=1$.
%Naopak, je-li $a=dq_1$, $b=dq_2$ a $(q_1,q_2)=1$, pak
%$(a,b)=(dq_1,dq_2)=d(q_1,q_2)=d\cdot 1=d$ (opět užitím 1. části tohoto
%tvrzení).
%\end{proof}
%
%\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Prvočísla}
  Prvočíslo je jeden z~nejdůležitějších pojmů elementární teorie
čísel. Jeho důležitost je dána především větou o~jednoznačném
rozkladu libovolného přirozeného čísla na součin prvočísel, která
je silným a účinným nástrojem při řešení celé řady úloh z~teorie čísel.

\begin{definice}
  Každé přirozené číslo $n\geq 2$ má
aspoň dva kladné dělitele: 1 a $n$. Pokud kromě těchto dvou jiné
kladné dělitele nemá, nazývá se {\it prvočíslo\/}. V~opačném
případě hovoříme o~{\it složeném čísle\/}.
\end{definice}

%\pause
V~dalším textu budeme zpravidla prvočíslo značit písmenem $p$.
Nejmenší prvočísla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, \dots
(zejména číslo 1 za prvočíslo ani za  číslo složené nepovažujeme).
Prvočísel je, jak brzy dokážeme, nekonečně mnoho, máme ovšem poměrně limitované
výpočetní prostředky na zjištění, zda je dané číslo prvočíslem (\href{http://primes.utm.edu}{největší známé
prvočíslo} $2^{82\,589\,933}-1$  má pouze $24\,862\,048$ cifer).
\end{frame}

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\begin{frame}{Základní věta aritmetiky}

Uveďme nyní větu, která udává ekvivalentní podmínku prvočíselnosti a je základní ingrediencí při důkazu jednoznačnosti rozkladu na prvočísla.

  \begin{veta}[Eukleidova o prvočíslech]
  Přirozené číslo $p\geq 2$ je
prvočíslo, právě když platí: pro každá celá čísla $a,b$ z~$p\divides ab$
plyne $p\divides a$ nebo $p\divides b$.
\end{veta}

%\pause
\begin{veta}
\label{veta:jednoznacny-rozklad}
Li\-bo\-vol\-né přirozené číslo $n\geq 2$ je možné vyjádřit
jako součin prvočísel, přičemž je toto vyjádření jediné,
nebereme-li v~úvahu pořadí činitelů. (Je-li $n$ prvočíslo, pak
jde o~\uv{součin} jednoho prvočísla.)
\end{veta}
\end{frame}



\end{document}