\documentclass[11pt,a4paper]{report}
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage[T1]{fontenc}
\usepackage{mathptmx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{a4wide}
%\usepackage{opakuj}
\usepackage{enumerate}
%\parindent=0mm
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usepackage{enumerate}
\usepackage{paralist}
\usepackage{xypic}

\usepackage[pdftex]{hyperref}
\hypersetup{hidelinks}

\DeclareMathOperator{\tg}{tg}
\DeclareMathOperator{\cotg}{cotg}
\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\tgh}{tgh}
\DeclareMathOperator{\cotgh}{cotgh}
\newcommand{\dx}{\,\mathrm{d}x}
\newcommand{\dt}{\,\mathrm{d}t}
\newcommand{\ds}{\,\mathrm{d}s}

\newcommand{\I}{{\rm i}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\ce}[1]{\ensuremath{\left(#1 \right)}}	% definice \ce 	- argument bude v~kulatych zavorkach
\newcommand{\cce}[1]{\ensuremath{\left[#1 \right]}}	% definice \cce	- argument bude v~hranatych zavorkach

\newcommand{\pp}[1]{\ensuremath{\left|#1\right|}}
\newcommand{\zk}[1]{\ensuremath{\left(#1 \right)}}
\newcommand{\zs}[1]{\ensuremath{\left<#1 \right>}}
\newcommand{\zh}[1]{\ensuremath{\left[#1 \right]}}
\newcommand{\zm}[1]{\ensuremath{\left\{#1 \right\}}}

\newcommand{\kon}[3]{\ensuremath{{#1} \equiv {#2}\pmod{#3}}}
\newcommand{\imp}{\ensuremath{\Rightarrow}}
\newcommand{\ekv}{\ensuremath{\Leftrightarrow}}
\newcommand{\bu}{\ensuremath{\bold{u}}}
\newcommand{\bv}{\ensuremath{\bold{v}}}

\newcommand{\psl}[1]{\ensuremath{\{{#1 }_n\}_{n=1}^\infty}}

\newtheorem{veta}{Věta}[chapter]
\newtheorem{lemma}[veta]{Lemma}
\theoremstyle{definition}
\newtheorem{definice}[veta]{Definice}
\newtheorem{dusledek}[veta]{Důsledek}
\newtheorem{prikl}{Příklad}[chapter]
\newtheorem{prikl*}[prikl]{*Příklad}
\newtheorem*{priklad}{Příklad}
\renewcommand{\qedsymbol}{$\blacksquare$}
\newtheorem{pr}{Návodný příklad}[chapter]
\newtheorem*{hint}{Hint}
\theoremstyle{remark}
\newtheorem{pozn}[veta]{Poznámka}

\overfullrule=2cm

\begin{document}
\setcounter{chapter}{4}
\chapter{Teorie čísel}
\begin{definice}
Buďte $a$, $b$, $m \in \N$. Řekneme, že číslo $a$ je \emph{kongruentní} s číslem $b$ modulo $m$, píšeme
\[
a \equiv b \pmod{m},
\]
jestliže $m \mid a-b$.
\end{definice}
\begin{veta}[Malá Fermatova]
Buďte $a \in \N$ a $p$ prvočíslo. Pak platí
\[
a^p \equiv a \pmod{p}.
\]
Pokud navíc $\ce{a,p} = 1$, tak
\[
a^{p-1} \equiv 1 \pmod{p}.
\]
\end{veta}
\begin{definice}
\emph{Eulerovou funkci} $\varphi \colon \N \to \N$ definujeme předpisem
\[
\varphi\ce{n} = \left| \{k \in \N \mid k \leq n, (k,n) = 1\} \right|,
\]
tj. Eulerova funkce nám udává počet čísel nesoudělných s číslem $n$, která nepřesáhnou $n$.
\end{definice}
\begin{veta}[Eulerova]
Buďte $a,m \in \N$ takové, že $(a,m) = 1$. Pak
\[
a^{\varphi\ce{m}} \equiv 1 \pmod{m},
\]
kde $\varphi$ je Eulerova funkce.
\end{veta}
\begin{pr}
Buďte $a$, $b$, $c \in \Z$ takové, že $a \mid b \cdot c$. Jestliže $(a,b) = 1$, pak $a \mid c$.
\end{pr}
\begin{pr}\label{rada}
Nechť $a,b \in \Z$. Dokažte, že $\forall n \in \N$ platí $\ce{a-b} \mid \ce{a^n - b^n}$.
\end{pr}
\begin{pr}
Nechť $a,b \in \Z$ a $n \in \N$ je liché. Dokažte, že $\ce{a+b} \mid \ce{a^n + b^n}$.
\end{pr}
\begin{pr}
Pomocí rovnosti Sophie Germainové
\[
a^4 + 4b^4 = \ce{a^2 +2b^2 + 2ab}\cdot\ce{a^2 + 2b^2-2ab}
\]
dokažte, že pro $n \in \N$, $n >1$ je číslo $n^4 + 4^n$ složené.
\end{pr}
\begin{pr}
Dokažte, že rovnice $15x^2 -7y^2 = 9$ nemá v oboru celých čísel žádné řešení.
\end{pr}
\begin{pr}\label{unique}
Nechť $p$ je prvočíslo a~$a \in \N$ je takové, že $\ce{a,p}=1$. Pak existuje $b \in \N$ takové, že
\[
a\cdot b \equiv 1 \pmod{p}.
\]
Mezi čísly $\{1, \dots, p-1\}$ je navíc takové $b$ určeno jednoznačně.
\end{pr}


\section{Příklady}
\begin{prikl}
Dokažte, že existuje nekonečně mnoho prvočísel tvaru $4k+3$.
\end{prikl}
\begin{proof}[Řešení]
Předpokládejme sporem, že prvočísel tvaru $4k+3$ existuje jen konečně mnoho. Nechť jsou $p_1 = 3$, $p_2 = 7, \dots, p_n$ všechna taková prvočísla. Uvažme
\[
N = 3 + 4\cdot \prod_{i = 2}^{n} p_n.
\]
Nechť $N = q_1^{\alpha_1} \cdot \dots \cdot q_m^{\alpha_m}$ je rozklad čísla $N$ na prvočísla. Protože $N \equiv 3 \pmod{4}$, musí být mezi prvočísly~$q_i$ nějaké ve tvaru $4k+3$. Protože ale $p_i \nmid N$ pro žádné $i=1,2,\dots,n$, dostáváme další prvočíslo tvaru $4k+3$, což nám dává požadovaný spor.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %15
Nalezněte všechna prvočísla $p$, $q$ taková, že $p^2 - 2q^2 = 1$.
\end{prikl}
\begin{proof}[Řešení]
Zřejmě $p > q$. Nejprve vyřešme případy, kdy $q \leq 3$. Je-li $q = 2$, máme $p^2 = 9$, tj. $p = 3$. Pro $q = 3$ máme $p^2 = 19$, což nám řešení nedá. Pro $p,q > 3$ platí
\[
p,q \equiv \pm 1 \pmod{6}.
\]
Když se tedy na zadanou rovnost podíváme modulo 6, dostáváme
\[
\ce{\pm 1}^2 - 2\ce{\pm 1}^2 \equiv 1 \pmod{6}.
\]
Jediné řešení je tedy $\ce{p,q} = \ce{3,2}$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %21
Buď $p \in \N$. Jsou-li $p$ a $p^2+2$ prvočísla, pak je i $p^3+2$ prvočíslo.
\end{prikl}
\begin{proof}[Řešení]
Zřejmě $p \neq 2$. Pro $p = 3$ máme $p^2 + 2 = 11$ a $p^3 + 2 = 29$. Pro $p>3$ je číslo $p^2+2$ dělitelné třemi, proto pro žádné $p>3$ není splněn předpoklad implikace a tvrzení platí.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %E8
Dokažte, že neexistuje polynom $f\ce{x}$ s~celočíselnými koeficienty takový, že $f\ce{7} = 11$, $f\ce{11} = 13$.
\end{prikl}
\begin{proof}[Řešení]
Nechť 
\[
f\ce{x} = \sum_{i=0}^{n} a_i x^i,
\]
kde $a_i \in \Z$. Jistě $\ce{c-d} \mid \ce{c^i - d^i}$ pro každé $i = 0,\dots,n$. Proto také $\ce{c-d} \mid a_i\ce{c^i - d^i}$ a~součtem přes~$i$ dostáváme $\ce{c-d} \mid \sum_{i=0}^{n}\ce{a_i}\ce{c^i-d^i} = f\ce{c}-f\ce{d}$. Kdyby hledaný polynom existoval, pak by $11-7 \mid f(11) - f(7)$, tj. $4 \mid 2$, což neplatí.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %57
Nalezněte nejmenší přirozené číslo takové, že odstraněním první cifry se toto číslo zmenší 57krát.
\end{prikl}
\begin{proof}[Řešení]
Označme $x$ první cifru hledaného čísla a~$y$ číslo, které nám vznikne odstraněním této cifry. Pak
\[
10^nx + y = 57y,
\]
kde $n$ je počet cifer čísla $y$. Odtud
\[
10^nx = 56y.
\]
Protože $56 = 2^3 \cdot 7$ a $(7,10^n) = 1$, platí $7 \mid x$, tj. $x = 7$ ($1\leq x\leq 9$, vždyť $x$ je cifra). Dostáváme
\[
10^n = 8y.
\]
Proto $y = 125 \cdot 10^{n-3}$, přitom vidíme, že nutně $n \geq 3$.  Původní číslo je tedy tvaru
\[
10^nx + y = 7125 \cdot 10^{n-3}.
\]
Nejmenší z~nich je pro $n = 3$, tj. $7125$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %121
Dokažte, že pokud poslední cifra čísla $m \in \N$ je 5, pak $1991 \mid (12^m + 9^m + 8^m + 6^m)$.
\end{prikl}
\begin{proof}[Řešení]
Nejprve upravme
\[
12^m + 9^m + 8^m + 6^m = \ce{4^m+3^m}\cdot\ce{3^m + 2^m}.
\]
Protože poslední cifra $m$ je 5, můžeme psát $m = 10a + 5 = 5\cdot\ce{2a+1}$. Protože $2a+1$ je liché, dostáváme
\[
\ce{4^5 + 3^5} \mid \ce{4^m + 3^m}\qquad\text{a}\qquad \ce{3^5 + 2^5} \mid \ce{3^m + 2^m}.
\]
Odtud
\[
\ce{4^5 + 3^5}\cdot\ce{3^5+2^5} \mid \ce{12^m + 9^m + 8^m + 6^m},
\]
přitom $\ce{4^5 + 3^5}\cdot\ce{3^5+2^5} = 1267 \cdot 275 = 5^2 \cdot 7 \cdot 11\cdot 181$. Protože $1991 = 11 \cdot 181$, dostáváme výsledek z~tranzitivity relace dělitelnosti.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %58
Nechť jsou dána $a$, $b$, $c$, $d \in \N$ taková, že $ab= cd$. Dokažte, že $\forall n \in \N$ je $a^n+b^n+c^n+d^n$ číslo složené.
\end{prikl}
\begin{proof}
Protože $ab = cd$, vydělením $bc$ dostáváme
\[
\frac{a}{c} = \frac{d}{b} = \frac{x}{y}
\]
pro nějaká $x$, $y \in \N$, kde $\ce{x,y} = 1$. Odtud
\[
a = ux, \quad c = uy, \quad d = vx, \quad b = vy.
\]
pro nějaká $u$, $v \in \N$. Tedy
\[
a^n + b^n + c^n + d^n = u^nx^n + u^ny^n + v^nx^n + v^ny^n = \ce{u^n+v^n}\ce{x^n+y^n}.
\]
Jistě obě závorky dávají čísla $>1$. Proto $a^n+b^n+c^n+d^n$ je číslo složené.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %[Wilsonova věta], 71
Dokažte, že $n\in \N$, $n > 1$ je prvočíslo právě tehdy, když $n \mid \ce{\ce{n-1}!+1}$.
\end{prikl}
\begin{hint}
Využijte návodného příkladu~\ref{unique} a~faktu, že pro prvočíslo $p$ má kongruence
\[
x^2 \equiv 1 \pmod{p}
\]
právě dvě řešení (v případě $p = 2$ dostáváme dvojnásobný kořen). Tento fakt dokazovat nemusíte.
\end{hint}
\begin{proof}[Řešení]
V~řeči kongruencí tvrzení říká, že $n > 1$ je prvočíslo $\Leftrightarrow \ce{n-1}! \equiv 1 \pmod{n}$.\\
\uv{$\Rightarrow$}: Buď $p$ prvočíslo. Prvky z množiny $M = \{2,3,\dots,p-2\}$ spárujeme tak, že každá dvojice $\ce{a,b}$ splní $a \cdot b \equiv 1 \pmod{p}$. Víme, že ke každému prvku $a \in M$ bude existovat (a to jednoznačně) prvek $b \in M$, neboť $(a,p)=1$. Kdyby $a = b$, pak $a^2 \equiv 1 \pmod{p}$, ale víme, že jediná řešení kongruence $x^2 \equiv 1 \pmod{2}$ jsou $1$ a~$p-1$. Díky tomuto párování máme
\[
\prod_{a \in M} a \equiv 1 \pmod{p},
\]
což nám celkem dává
\[
\ce{p-1}! = 1 \cdot (p-1) \cdot \prod_{a \in M} a \equiv p-1 \equiv -1 \pmod{p}.
\]
Přitom pro $p = 2,3$ využíváme konvence, že $\prod_{\emptyset} a = 1$ (případně snadno rozmyslíme, že pro tato prvočísla tvrzení platí).\\
\uv{$\Leftarrow$}: Pro $n = 4$ máme $\ce{n-1}! \equiv 2 \pmod{4}$ a pro ostatní složená čísla máme $\ce{n-1}! \equiv 0 \pmod{n}$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %Modifikace 108
Dokažte, že $2015 \mid \underbrace{55\dots5}_{360}$.
\end{prikl}
\begin{proof}[Řešení]
Vydělením pěti dostáváme
\[
403 \mid \underbrace{11\dots1}_{360},
\]
kde
\[
\underbrace{11\dots1}_{360} = \frac{10^{360}-1}{9}.
\]
Protože $(403, 9) = 1$, dostáváme ekvivalentní podmínku (kterou chceme dokázat)
\[
403 \equiv 10^{360} - 1.
\]
Uvažme Eulerovu funkci: $\varphi\ce{403} = \varphi\ce{13} \cdot \varphi\ce{31} = 360$. Protože $\ce{10,403}=1$, dostáváme z Eulerovy věty
\[
10^{\varphi\ce{403}}=10^{360} \equiv 1 \pmod{403},
\]
tedy
\[
403 \mid 10^{360} - 1,
\]
což jsme chtěli dokázat.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %E17
Nechť $\alpha$, $\beta$ jsou dvě kladná iracionální čísla taková, že $\frac{1}{\alpha} + \frac{1}{\beta} = 1$. Uvažme posloupnosti $\{a_n\}_{n = 1}^{\infty}$, $\{b_n\}_{n=1}^{\infty}$ zadané pomocí předpisů $a_n = \lfloor n\alpha\rfloor$, $b_n = \lfloor n\beta \rfloor$. Dokažte, že:
\begin{enumerate}
\item Posloupnosti $\{a_n\}_{n=1}^{\infty}$, $\{b_n\}_{n=1}^{\infty}$ jsou disjunktní, tj. $\forall m,n \in \N\colon a_m \neq b_n$.
\item Sjednocením obou posloupností jsou přirozená čísla, tj. $\forall k \in \N$~$\exists n\in \N \colon k = a_n$ nebo $k = b_n$.
\end{enumerate}
\end{prikl}
\begin{proof}[Řešení]
\begin{enumerate}
\item Předpokládejme sporem, že existují $n$, $m\in \N$ takové, že $a_m = b_n$, tj. $\lfloor \alpha m \rfloor = \lfloor \beta n \rfloor = q$. Pak 
\[
q < \alpha m < q + 1, \qquad q < \beta n < q+1,
\]
přitom ostré nerovnosti jsou díky iracionalitě $\alpha$ a $\beta$. Odtud
\[
\frac{m}{q+1} < \frac{1}{\alpha} < \frac{m}{q}, \qquad \frac{n}{q+1} < \frac{1}{\beta} < \frac{n}{q}.
\]
Sečtením obou řetězců nerovností dostaneme
\[
\frac{m+n}{q+1} < 1 < \frac{m+n}{q}.
\]
To nám dává
\[
q < m+n < q+1,
\]
což je spor. Nutně jsou tedy obě posloupnosti disjunktní.
\item Jistě $\alpha, \beta > 1$. Navíc právě jedno z nich musí být $< 2$ (jinak by součet převrácených hodnot byl $<1$). Jistě tedy $a_1$ nebo $b_1 = 1$. Sporem předpokládejme, že v~intervalu $(q,q+1)$ pro $q \geq 2$ neleží žádný člen zadaných posloupností, tedy
\begin{align*}
\alpha m < q < q+1 < \alpha \ce{m+1}&, \qquad \beta n < q < q+1 <  \beta \ce{n+1},\\
\frac{m}{q} < \frac{1}{\alpha} < \frac{m+1}{q+1}&, \qquad \frac{n}{q} < \frac{1}{\beta} < \frac{n+1}{q+1}.
\end{align*}
Sečtením obou řetězců nerovností dostáváme
\[
\frac{m+n}{q} < 1 < \frac{m+n+2}{q+1}.
\]
Odtud
\[
m+n < q < q+1 < m+n+2,
\]
což je spor.
\end{enumerate}
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %161
Dokažte, že pro nekonečně mnoho složených čísel $n$ platí $n \mid 3^{n-1} - 2^{n-1}$.
\end{prikl}
\begin{hint}
Hledejte $n$ ve tvaru $n = 3^{2^t} - 2^{2^t}$ pro $t \in \N$.
\end{hint}
\begin{hint}[Alternativní hint]
Využijte návodného příkladu~\ref{rada}.
\end{hint}
\begin{proof}[Řešení]
Pro volbu $n = 3^{2^t} - 2^{2^t}$ dostáváme, že chceme ukázat
\[
3^{2^t} - 2^{2^t} \mid 3^{3^{2^t} - 2^{2^t}-1} - 2^{3^{2^t}-2^{2^t}-1}.
\]
Protože $x-y \mid x^k - y^k$ pro každé $k \in \N$, stačí ukázat, že
\[
2^t \mid 3^{2^t} - 2^{2^t} - 1.
\]
Zejména tedy chceme ukázat, že
\[
3^{2^t} \equiv 1 \pmod{2^t}.
\]
Protože $\ce{2,3} = 1$ a $\varphi\ce{2^t} = 2^{t-1}$, máme z~Eulerovy věty
\[
3^{2^t} = \ce{3^{2^{t-1}}}^2 \equiv 1^2 = 1 \pmod{2^t},
\]
což jsme chtěli dokázat.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %162
Dokažte, že rovnice $x^2 + y^2 + z^2 = x^3 + y^3 + z^3$ má nekonečně mnoho celočíselných řešení.
\end{prikl}
\begin{proof}[Řešení]
Hledejme řešení, pro která $y = -z$, pak dostáváme
\[
x^2 + 2y^2 = x^3.
\]
Separací proměnných dostáváme
\[
x^2 \frac{x-1}{2} = y^2.
\]
Odtud plyne, že $\frac{x-1}{2}$ je čtverec, tj. $\frac{x-1}{2} = t^2$. Tedy
\[
x = 2t^2+1, \qquad y = 2t^3 + t.
\]
Pro každé $t \in \N$ dostáváme řešení $\ce{2t^2+1, 2t^3+t, -2t^3-t}$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl} %163
Dokažte, že existuje nekonečně mnoho přirozených čísel $n$ takových, že $2^n$ končí na $n$.
\end{prikl}
\begin{hint}
Nejmenší $n$, které tuto podmínku splní je $36$: $2^{36} = 68\,719\,476\,736$. Množinu řešení konstruujte induktivně. Ukažte, že pokud je $n$ řešení a $2^n = \dots dn$ pro nějaké číslo $d = g \cdot 10^m$, kde $g \in \{1,\dots, 9\}$ (přitom $dn$ neznamená násobení, ale zřetězení), pak je i $dn$ řešení. \\
Jinými slovy: další řešení nalezneme tak, že v~dekadickém zápise čísla $2^n$ připojíme k~$n$ všechny předcházející cifry až po první nenulovou (včetně). To, že nestačí brát jen další cifru lze odůvodnit tím, že uvedeným postupem bychom dostali $2^{75\,353\,432\,948\,736}  = \dots 075\,353\,432\,948\,736$.
\end{hint}
\begin{proof}[Řešení]
Nechť $n$ je nějaké řešení. Označme $g$ první nenulovou cifru čísla $2^n$, která předchází $n$. Buď dále $k$ počet cifer čísla $n$, $l$ počet nul mezi $g$ a $n$. Konečně označme $d = g \cdot 10^l$. Tedy
\[
2^n = \dots dn, \qquad \text{kde}\qquad d = g\underbrace{0\dots0}_{l\times}
\]
Pak $dn = n + g\cdot 10^{k+l}$. Chceme ukázat implikaci
\[
2^n \equiv n + g\cdot 10^{k+l} \pmod{10^{k+l+1}} \quad\Rightarrow\quad 2^{n + g\cdot 10^{k+l}} \equiv n+g\cdot 10^{k+l} \pmod{10^{k+l+1}}.
\]
Díky Čínské zbytkové větě nám stačí ukázat, že
\[
2^n \equiv 2^{n+g \cdot 10^{k+l}} \pmod{2^{k+l+1}} \qquad \text{a} \qquad 2^n \equiv 2^{n+g \cdot 10^{k+l}} \pmod{5^{k+l+1}}.
\]
Protože $k$ je počet cifer čísla $n$ a $n \geq 36$, je $k << n$. Je-li $l$ dostatečně malé (nejvýše exponenciální vůči $n$), pak též $k+l < n$. Odtud
\[
2^n \equiv 0 \equiv 2^{n+g \cdot 10^{k+l}} \pmod{2^{k+l+1}}.
\]
Protože $\varphi\ce{5^{k+l+1}} = 4\cdot 5^{k+l}$, dostáváme z~Eulerovy věty
\[
2^{d \cdot 10^{k+l}} = \ce{2^{d \cdot 2^{k+l-2}}}^{\varphi\ce{5^{k+l+1}}} \equiv 1 \pmod{5^{k+l+1}}.
\]
Tím dostáváme
\[
2^{n+g\cdot 10^{k+l}} = 2^n \cdot 2^{g \cdot 10^{k+l}} \equiv 2^n \pmod{5^{k+l+1}}.
\]
Ukázali jsme tedy, že je-li $n$ řešení, pak je řešení i $dn = n + g\cdot 10^{k+l}$.
\end{proof}
\end{document}