\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}
\makeatletter
\let\newmcodes@\relax
\makeatother

\usepackage{enumerate}
%\parindent=0mm
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usepackage{enumerate}
\usepackage{paralist}
\usepackage{xypic}

\usepackage{verbatim}

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

\DeclareMathOperator{\tg}{tg}
\DeclareMathOperator{\cotg}{cotg}
\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\tgh}{tgh}
\DeclareMathOperator{\cotgh}{cotgh}
\DeclareMathOperator{\LM}{LM}
\DeclareMathOperator{\LT}{LT}
\DeclareMathOperator{\LC}{LC}
\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)}}
\newcommand{\cce}[1]{\ensuremath{\left[#1 \right]}}

\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{\dcc}[1]{\ensuremath{\left\lfloor #1 \right\rfloor}}

\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

\let\WITHSOLUTION 1 % added \usepackage{verbatim}
\newenvironment{reseni}
{ \ifx\WITHSOLUTION 1 \begin{proof}[Řešení]\else \comment \fi }
{ \ifx\WITHSOLUTION 1 \end{proof}\else \endcomment \fi }

\newenvironment{ilpr}
{ \ifx\WITHSOLUTION 1 \begin{priklad}\else \comment \fi }
{ \ifx\WITHSOLUTION 1 \end{priklad}\else \endcomment \fi }

\begin{document}
\chapter{Teorie čísel}
\section*{Dělitelnost a kongruence}
V této části si představíme pojem kongruence. Uvedeme několik užitečných tvrzení. Jejich důkazy ponecháváme jako jednoduchá cvičení. Zápis $\gcd\ce{a,b}$ značí největší společný dělitel $a,b \in \Z$. Na~úvod připomeňme definici dělitelnosti.
\begin{definice}
Nechť $a,b \in \Z$. Řekneme, že $a$ dělí $b$ (též $b$ je dělitelné $a$), píšeme 
\[
a \mid b,
\]
jestliže existuje $k \in \Z$ takové, že $ak = b$.
\end{definice}
\begin{lemma}
Relace dělitelnosti je tranzitivní, tedy pro $a,b,c \in \Z$ platí
\[
a \mid b,~b \mid c \quad \Rightarrow \quad a \mid c.
\]
\end{lemma}
\begin{lemma}
Nechť $p$ je prvočíslo, pak platí
\[
p \mid ab \quad \Rightarrow \quad (p \mid a ~\text{ nebo }~ p \mid b).
\]
\end{lemma}
\begin{definice}
Nechť $a,b \in \Z$, $m \in \N$. Řekneme, že $a$ je kongruentní s~$b$ modulo~$m$, píšeme
\[
a \equiv b \pmod{m},
\]
jestliže $m \mid a-b$.
\end{definice}

\begin{lemma}[základní operace s kongruencemi]
Nechť $a,b,c,d,k \in \Z$, $m,n \in \N$. Platí
\begin{alignat*}{3}
&a \equiv b \pmod{m},~ c \equiv d \pmod{m} \quad &&\Rightarrow \quad a \pm \equiv b \pmod{m},\\
&a \equiv b \pmod{m},~ c \equiv d \pmod{m} \quad &&\Rightarrow \quad ac \equiv bd \pmod{m},\\
&a \equiv b \pmod{m} \quad &&\Rightarrow \quad ak \equiv bk \pmod{m},\\
&a \equiv b \pmod{m} \quad &&\Rightarrow \quad a^n \equiv b^n \pmod{m},\\
&ak \equiv bk \pmod{m}, ~\gcd\ce{k,m} = 1 \quad &&\Rightarrow \quad a \equiv b \pmod{m},\\
&an \equiv bn \pmod{m}, ~n \mid m \quad &&\Rightarrow \quad a \equiv b \pmod{\frac{m}{n}},\\
&a \equiv b \pmod{m} \quad &&\Rightarrow \quad an \equiv bn \pmod{bn},\\
&a \equiv b \pmod{m},~ d \mid m \quad &&\Rightarrow \quad a \equiv b \pmod{d}.
\end{alignat*}
\end{lemma}
\begin{pozn}
Předchozí lemma nám může dost usnadnit uvažování při řešení příkladů o dělitelnosti.
\begin{enumerate}
\item Nalezněte zbytek po dělení čísla $5^{20}$ číslem 26.
\[
5^{20} = 25^{10} \equiv (-1)^{10} = 1 \pmod{26}.
\]
\item Dokažte, že pro libovolné $n \in \N$ platí $7 \mid 37^{n+2} + 16^{n+1} + 23^n$.
\[
37^{n+2} + 16^{n+1} + 23^n \equiv 2^{n+2} + 2^{n+1} + 2^n = (4+2+1) \cdot 2^n \equiv 0 \pmod{7}.
\]
\item Dokažte, že pro libovolné $n \in \N$ platí $11 \mid 5^{3n} - 2^{2n}$.
\[
5^{3n} - 2^{2n} = (5 \cdot 25)^{n} - 4^n \equiv (5 \cdot 3)^n - 4^n = 15^n - 4^n \equiv 4^n - 4^n = 0 \pmod{11}.
\]
\end{enumerate}
\end{pozn}
Nyní ukážeme, že v jistém smyslu lze dělit libovolným prvkem, který je nesoudělný s modulem.
\begin{lemma}
Nechť $a \in \Z$, $m \in \N$.
\[
\gcd\ce{a,m} = 1 \quad \Leftrightarrow \exists b \in \Z \colon ab \equiv 1 \pmod{m}.
\]
\end{lemma}
K hledání této multiplikativní inverze (tj. inverze k~násobení, tedy $a^{-1}$) využijeme tzv. Euklidův algoritmus a Bezoutovu rovnost.

\begin{lemma}[Euklidův algoritmus]
Nechť $a_1, a_2 \in \Z$. Pak $(a_1,a_2) = d$ dostaneme jako \textbf{poslední nenulový zbytek}, který získáme pomocí postupného dělení se zbytkem.
\begin{align*}
a_1 &= q_1a_2 + a_3\\
a_2 &= q_2a_3 + a_4\\
a_3 &= q_3a_4 + a_5\\
&\vdots\\
a_{k-2} &= q_{k-2}a_{k-1} + a_k\\
a_{k-1} &= q_{k-1}a_{k} + 0
\end{align*}
kde $|a_i| > |a_{i+1}|$ pro všechna $i=1,\dots,k-1$ a navíc $a_k \neq 0$. Pak platí: $\ce{a_1, a_2} = a_k$
\end{lemma}

\begin{lemma}[Bezoutova identita]
Nechť $a,b \in \Z$, $\ce{a,b} = d$, pak $\exists k,l \in \Z\colon ak + bl = d$.
\end{lemma}


\begin{pozn}
Předvedeme si, jak nyní využít Euklidův algoritmus ke hledání multiplikativní inverze. Hledejme $b \in \Z$ takové, aby
\[
17 \cdot b \equiv 1 \pmod{31}
\]
Spočtěme $\gcd\ce{31, 17}$ a nalezněme koeficienty z Bezoutovy identity.
\begin{align*}
31 &= 17 + 14\\
17 &=  14 + 3\\
14 &= 4\cdot 3 + 2\\
3 &=  2 + 1\\
2 &= 2\cdot 1 + 0
\end{align*}
Dostáváme tedy, že $\gcd\ce{31,17} = 1$. Nyní opačným postupem vyjádříme $1$ pomocí $31$ a $17$
\begin{align*}
1 &= 3-2,\\
1 &= 3 - (14 - 4 \cdot 3) = 5 \cdot 3 - 14,\\
1 &= 5 \cdot (17-14) - 14 = 5 \cdot 17 - 6 \cdot 14,\\
1 &= 5 \cdot 17 - 6 \cdot (31-17) = 11 \cdot 17 - 6 \cdot 31.
\end{align*}
Podívejme se na rovnost $1 = 11 \cdot 17 - 6 \cdot 31$ modulo 31. Dostáváme
\[
1 \equiv 11 \cdot 17 \pmod{31}.
\]
Hledané $b$ je tedy 11.

Ukázali jsme si, že prvky nesoudělné s modulem jsou poměrně význačné. Tento fakt se projeví zejména v~Eulerově větě. Řekněme si proto na závěr této úvodní části ještě něco málo o~Eulerově funkci.
\end{pozn}
\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{lemma}
Buď $n \in \N$ libovolné číslo a $n = p_1^{\alpha_1} \cdot \hdots \cdot p_k^{\alpha_k}$ jeho rozklad na prvočísla, kde $p_i \neq p_j$ pro $i \neq j$ a $\alpha_i \geq 1$. Pak platí
\[
\varphi\ce{n} = \prod_{i=1}^k \ce{p_i - 1} \cdot p_i^{\alpha_i - 1} = n \cdot \prod_{i=1}^k \ce{1 - \frac1p}.
\]
\end{lemma}

%\begin{veta}[binomická]
%Nechť $x,y \in \R$, $n \in \N$. Pak platí
%\[
%\ce{x+y}^n = \sum_{k = 0}^n \binom{n}{k}x^ky^{n-k},
%\]
%kde $\binom{n}{k} = \frac{n!}{k! \cdot \ce{n-k}!}$ je binomický koeficient.
%\end{veta}

\newpage
\section{Teorie}
\begin{veta}[malá Fermatova]
Buďte $a \in \Z$ a $p$ prvočíslo. Pak platí
\[
a^p \equiv a \pmod{p}.
\]
Pokud navíc $p \nmid a$, tak
\[
a^{p-1} \equiv 1 \pmod{p}.
\]
\end{veta}
%\begin{proof}[Důkaz]
%Zřejmě pokud tvrzení platí pro $a \geq 0$, pak platí též pro $-a$. Stačí tedy provést důkaz jen pro $a \in \N_0$. Důkaz povedeme matematickou indukcí.
%
%Jistě $0^n \equiv 0 \pmod{p}$.
%
%Nechť tvrzení platí pro nějaké $a \in \N$, pak
%\[
%(a+1)^p = \sum_{i=0}^p \binom{p}{i} a^i \equiv a^p + 1 \equiv a + 1 \pmod{p},
%\]
%kde první rovnost je aplikace binomické věty, kongruence plyne z toho, že $\binom{p}{i} = \frac{p!}{i! \cdot (p-i)!} \equiv 0 \pmod{p}$ pro $i = 1, \dots, p-1$. Poslední kongruence plyne z indukčního předpokladu.
%
%Je-li navíc $\gcd\ce{a,p}$, tj. $p \nmid a$, pak můžeme krátit a dostáváme i~druhý tvar
%\[
%a^{p-1} \equiv 1 \pmod{p}.
%\]
%\end{proof}
\begin{veta}[Eulerova]
Buďte $a,m \in \N$ takové, že $\gcd\ce{a,m} = 1$. Pak
\[
a^{\varphi\ce{m}} \equiv 1 \pmod{m},
\]
kde $\varphi\colon\N \to \N$ je Eulerova funkce.
\end{veta}
%\begin{proof}[Důkaz]
%Uvažme po dvou nekongruentní čísla $a_1, \dots, a_{\varphi\ce{m}}$, která jsou nesoudělná s modulem $m$. Tato čísla tvoří tzv. \emph{redukovanou soustavu zbytků}. Jistě součin libovolných dvou čísel nesoudělných s modulem bude opět číslo nesoudělné s modulem. Proto pro libovolné $a \in \Z$ takové, že $\gcd\ce{a,m} = 1$ platí
%\begin{align*}
%a \cdot a_1 &\equiv a_{\sigma\ce{1}} \pmod{m},\\
%a \cdot a_2 &\equiv a_{\sigma\ce{2}} \pmod{m},\\
%&\vdots\\
%a \cdot a_{\varphi\ce{m}} &\equiv a_{\sigma\ce{\varphi(m)}} \pmod{m},
%\end{align*}
%kde $\sigma$ je vhodná permutace množiny $\{1,\dots, \varphi\ce{m}\}$ (jistě je násobení číslem $a$ bijekce na redukované soustavě zbytků, neboť existuje $a^{-1}$). Vynásobením těchto kongruencí dostáváme
%\[
%a^{\varphi\ce{m}} \cdot \prod_{i=1}^{\varphi\ce{m}} a_i \equiv \prod_{i=1}^{\varphi\ce{m}} a_i \pmod{m}
%\]
%díky nesoudělnosti všech $a_i$ s modulem můžeme krátit
%\[
%a^{\varphi\ce{m}} \equiv 1 \pmod{m}.
%\]
%\end{proof}
\begin{veta}[čínská zbytková]
Buďte $m_1, m_2 \dots, m_k \in \N$ po dvou nesoudělná čísla, $a_1, a_2 \dots, a_k \in \Z$. Pak soustava
\begin{align*}
x &\equiv a_1 \pmod{m_1},\\
x &\equiv a_2 \pmod{m_2},\\
&\vdots\\
x &\equiv a_k \pmod{m_k}
\end{align*}
má právě jedno řešení modulo $m_1 \cdot m_2 \cdot \hdots \cdot m_k$.
\end{veta}
\begin{veta}[Wilsonova]
Přirozené číslo $n \geq 2$ je prvočíslo právě tehdy, když
\[
(n-1)! \equiv -1 \pmod{n}.
\]
\end{veta}
\newpage
\section{Příklady}
\begin{prikl} % čínská zbytková věta 1
Buď $n \in \N$. Ukažte, že existuje $n$ po sobě jdoucích čísel takových, že každé z nich je dělitelné alespoň dvěma různými prvočísly.
\end{prikl}
\begin{reseni}
Hledáme $x$ splňující
\begin{align*}
x &\equiv 0 \pmod{p_0q_0},\\
x+1 &\equiv 0 \pmod{p_1q_1},\\
&\vdots\\
x+n-1 &\equiv 0 \pmod{p_{n-1}q_{n-1}},
\end{align*}
pro nějaká po dvou různá prvočísla $p_0,\dots, p_{n-1}$, $q_0,\dots,q_{n-1}$. Zvolíme-li libovolná různá prvočísla, budou moduly po dvou nesoudělné. Čínská zbytková věta nám pak přímo říká, že existuje celé číslo $x$ splňující soustavu
\begin{alignat*}{3}
x &\equiv 0 &&\pmod{p_0q_0},\\
x &\equiv -1 &&\pmod{p_1q_1},\\
&\vdots\\
x &\equiv -n+1 &&\pmod{p_{n-1}q_{n-1}}.
\end{alignat*}
\end{reseni}
%%%%%
\begin{prikl}% čínská zbytková věta 5 
Dokažte, že existuje číslo $n \in \Z$ takové, že pro libovolné $k \in \Z$ nemá číslo $k^2 + k + n$ žádného prvočíselného dělitele menšího než 2016.
\end{prikl}
\begin{reseni}
Nechť $p$ je prvočíslo. Zkoumejme, jaký zbytek po dělení $p$ může dávat číslo $k^2+k$. Zjevně stačí dosadit čísla $0,1,\dots\,p-1$, dále se už budou zbytky periodicky opakovat. Pro $k=0$ a $k=p-1$ je $k^2+k\equiv 0 \pmod p$. Z Dirichletova principu proto plyne, že existuje $r\in{0,1,...,p-1}$ pro které platí 
\[
\forall k \in \Z: k^2+k \not \equiv r \pmod p.
\]
Nechť $p_1,...,p_m$ jsou prvočísla menší než $2016$ a $r_1,...,r_m$ jsou příslušné zbytky, jichž $k^2+k$ nenabývá. Hledáme tedy $n$ splňující
\begin{align*}
n &\equiv -r_1 \pmod{p_1},\\
n &\equiv -r_2 \pmod{p_2},\\
&\vdots\\
n &\equiv -r_m \pmod{p_{m}},
\end{align*}
protože pak $k^2+k+n \equiv k^2+k-r_i \not \equiv 0 \pmod {p_i}$ pro všechna $i$. Existence takového $n$ vyplývá z čínské zbytkové věty.
\end{reseni}
%%%%%
\begin{prikl} % čínská zbytková věta 6
Rozhodněte, zda existuje posloupnost obsahující každé přirozené číslo právě jednou taková, aby součet jejích prvních $k$ členů byl dělitelný $k$ pro všechna $k \in \N$.
\end{prikl}
\begin{reseni}
Označme posloupnost $\{a_n\}_{n=1}$ a $s_k= \sum_{i=1}^{k} a_i$. Položme $a_1=1$. Předpokládejme, že máme prvních $k$ členů splňujících podmínky. Hledáme $a_{k+1}$ a $a_{k+2}$ taková, že $a_{k+2}$ je nejmenší přirozené číslo, které se nevyskytuje v $a_1,\dots,a_k$. Tedy chceme, aby 
\begin{alignat*}{3}
a_{k+1} &\equiv -s_k  &&\pmod{k+1}\\
a_{k+2} &\equiv -s_k-a_{k+2} &&\pmod{k+2}.
\end{alignat*}
Jelikož $(k+1,k+2)=1$ pak nám čínská zbytková věta říká, že takové $a_{k+1}$ různé od $a_1,\dots,a_k,a_{k+2}$ opravdu existuje. 
\end{reseni}
%%%%%
\begin{prikl} % čínská zbytková věta 9
Nechť $n \in \N$ a $a_1,\dots,a_k$ ($k \geq 2$) jsou navzájem různá celá čísla z~množiny $\{1,\dots,n\}$ taková, že pro každé $i = 1,\dots, k-1$ je číslo $a_i(a_{i+1}-1)$ dělitelné $n$. Dokažte, že číslo $a_k(a_1 -1)$ není dělitelné $n$.
\end{prikl}
\begin{reseni}
Nechť $n=pq$ tak, že $p|a_1$ a $q|a_2-1$. Předpokládejme pro spor, že $n|a_k(a_1-1)$. Jelikož $q|a_2-1$, pak $(q,a_2)$, a tudíž $q|a_3-1$. Obdobně pro ostatní členy dostáváme, že $q|a_i-1$ pro všechna $i$. Dále $p|a_1$, z čehož plyne $(p,a_1-1)=1$ a tedy $p|a_k$. Podobně máme $p|a_i$ pro všechna $i$. Všechna $a_i$ jsou řešením dvojice kongruencí 
\begin{align*}
x &\equiv 0 \pmod{p},\\
x &\equiv 1 \pmod{q}.
\end{align*}
Nutně navíc $(p,q)=1$, protože $p|a_1$ a $q|a_1-1$. Čínská zbytková věta nám říká, že existuje jedno takové $0\leq x<pq=n$. My jich máme ale hned $k$. Máme hledaný spor.
\end{reseni}
%%%%%
\begin{prikl} % Bulík, 3
Dokažte, že pro každé liché prvočíslo $p$ existuje nekonečně mnoho $n \in \N$ splňujících $p \mid \ce{n \cdot 2^n +1}$.
\end{prikl}
\begin{reseni}
Hledáme nekonečně mnoho $n$ pro které platí
\[
n \cdot 2^n \equiv -1 \pmod{p}.
\]
Z malé Fermatovy věty máme
\[
2^{p-1} \equiv 1 \pmod{p}.
\]
Zřejmě tedy je-li $n = p-1$, pak
\[
(p-1) \cdot 2^{p-1} \equiv -1 \cdot 1 = -1 \pmod{p}.
\]
Zvolíme-li $n$ jako $k$-tou mocninu čísla $p-1$, pak
\[
n \cdot 2^n = (p-1)^k \cdot 2^{(p-1)^k} \equiv (-1)^k \cdot 1^{(p-1)^{k-1}} = (-1)^k \pmod{p}.
\]
Vidíme, že řešením jsou všechna $n = (p-1)^k$ pro $k$ liché.
\end{reseni}
%%%%%
\begin{prikl} % Bulík 7
Dokažte, že pro všechna lichá $n \in \N$ platí $n \mid \ce{2^{n!} - 1}$.
\end{prikl}
\begin{reseni}
V řeči kongruencí chceme dokázat, že $\forall n \in \N$, $2 \nmid n$ platí
\[
2^{n!} \equiv 1 \pmod{n}.
\]
Protože $n$ je liché, je $\gcd{2,n} = 1$, můžeme tedy použít Eulerovu větu. Protože $\varphi(n) \leq n$ platí $\varphi(n) \mid n!$ a tedy existuje $k \in \N$ takové, že $k\varphi(n) = n!$. Platí tedy
\[
2^{n!} = \ce{2^{\varphi(n)}}^k \equiv 1^k = 1 \pmod{n},
\]
což jsme chtěli dokázat.
\end{reseni}
%%%%%
\begin{prikl}\label{priklad1.7}
Nechť $p$ je liché prvočíslo. Dokažte
\[
p \equiv 1 \pmod{4} \quad \Leftrightarrow \quad \exists m \in \N \colon p \mid m^2 + 1.
\]
\end{prikl}
\begin{reseni}
\uv{$\Leftarrow$}: Nechť
\[
m^2 \equiv -1 \pmod{p}.
\]
Umocněme na $\frac{p-1}{2}$, dostáváme
\[
1 \stackrel{MFV}{\equiv} m^{p-1} \equiv (-1)^{\frac{p-1}{2}} \pmod{p},
\]
což nastává právě tehdy, je-li $\frac{p-1}{2}$ sudé, tedy $p \equiv 1 \pmod{4}$.

\uv{$\Rightarrow$}: Nechť naopak $p \equiv 1 \pmod{4}$, tj. $p = 4k+1$. Z Wilsonovy věty máme
\[
-1 \equiv (4k)! \equiv 1 \cdot 2 \cdot \hdots \cdot 2k \cdot (p-2k) \cdot (p-(2k-1))\cdot \hdots \cdot (p - 1) = (-1)^{2k} \cdot [(2k)!]^2 = m^2 \pmod{p}
\]
\end{reseni}
%%%%%
\begin{prikl} % Engel, 6 Number Theory, 131
Žádné prvočíslo nelze zapsat jako součet dvou čtverců více než jedním způsobem.
\end{prikl}
%\begin{reseni}
%Nechť $p = a^2 + b^2 = c^2 + d^2$, kde $a \neq c$. Jistě též $a \neq b$ a $c \neq d$. BÚNO $a > b$, $c> d$, $a > c$. Pak
%\[
%p^2 = (a^2 + b^2) \cdot (c^2 + d^2) = a^2c^2 + b^2d^2 + a^2d^2 + b^2c^2
%\]
%můžeme psát dvěma způsoby jako
%\[
%p^2 = (ac \pm bd)^2 +(ad \mp bc)^2,
%\]
%přitom
%\[
%(ac+bd)(ad+bc) = a^2cd + b^2cd + abc^2 + abd^2 = (a^2+b^2)cd + (c^2+d^2)ab = p(ab+cd).
%\]
%Nutně tedy $p \mid (ac+bd)$ nebo $p \mid (ad+bc)$.\\
%Pokud $p \mid (ac+bd)$, pak z
%\[
%p^2 = (ac+bd)^2 + (ad-bc)^2
%\]
%dostáváme, že $ad = bc$. Přitom $a>c$ dává $d < b$. Pak ale $a^2 + b^2 > c^2 + d^2$, což je spor.\\
%Pokud $p \mid (ad+bc)$, pak z
%\[
%p^2 = (ad+bc)^2 + (ac-bd)^2
%\]
%dostáváme, že $ac = bd$. Protože ale $a>b$ a $c>d$, dostáváme spor.
%\end{reseni}
%%%%%
\begin{prikl}
Nechť $p$ je liché prvočíslo. Dokažte
\[
p \equiv 1 \pmod{4} \quad \Leftrightarrow \quad \exists x,y \in \N \colon p = x^2 + y^2.
\]
\end{prikl}
%\begin{reseni}
%\uv{$\Leftarrow$}: Jistě právě jedno z $x,y$ je sudé, nechť tedy například $2 \mid x$, pak
%\[
%p = x^2 + y^2 \equiv 0 + 1 = 1 \pmod{4}.
%\]
%\uv{$\Rightarrow$}: Nechť $p \equiv 1 \pmod{4}$, tj. $p = 4k+1$. Z Wilsonovy věty podobně jako v příkladu~\ref{priklad1.7} máme pro $m = (2k)!$
%\[
%m^2 \equiv -1 \pmod{p}.
%\]
%Jistě
%\[
%x^2 + y^2 \equiv (x+my)(x-my) \pmod{p}.
%\]
%Počet dvojic $\ce{x,y} \in \Z$ takových, že
%\[
%0 \leq x < \sqrt{p}, \quad 0 \leq y < \sqrt{p}
%\]
%existuje právě $\lceil \sqrt{p} \rceil \cdot \lceil \sqrt{p} \rceil > \sqrt{p}^2 = p$. Nutně tedy existují dvě různé dvojice $\ce{x,y}, \ce{x',y'}$ takové, že
%\[
%x+my \equiv x'+my' \pmod{p}.
%\]
%Položme $x_0 = x-x'$ a $y_0 = y-y'$. Pak platí
%\[
%x_0 + my_0 = (x-x') + m(y-y') = (x + my) - (x' + my') \equiv 0 \pmod{p}.
%\]
%Přitom jistě $\ce{x_0,y_0} \neq \ce{0,0}$ a zároveň $|x_0| < \sqrt{p}$, $|y_0| < \sqrt{p}$. Odtud
%\[
%0 < x_0^2 + y_0^2 < 2p,
%\]
%přitom $p \mid x_0^2 + y_0^2$, tedy
%\[
%x_0^2 + y_0^2 = p.
%\]
%\end{reseni}
%%%%%
\begin{prikl}% Engel, 6 Number Theory, E12
Řešte v $\Z$
\[
x^2 + y^2 + z^2 = 2xyz.
\]
\end{prikl}
%\begin{reseni}
%Jistě $x=y=z=0$ je řešení. Ukažme, že je jediné. Předpokládejme sporem, že $\ce{x,y,z} \neq \ce{0,0,0}$ je řešení. Buď $2^k$, $k \geq 0$ největší mocnina dvou, která dělí $x,y,z$. Pak
%\[
%x=2^k x_1, \quad y = 2^k y_1, \quad z = 2^k z_1.
%\]
%Dosazením do původní rovnice dostáváme
%\begin{align*}
%2^{2k} x_1^2 + 2^{2k} y_1^2 + 2^{2k} z_1^2 &= 2^{3k+1}x_1y_1z_1,\\
%x_1^2 + y_1^2 + z_1^2 &= 2^{k+1} x_1y_1z_1.
%\end{align*}
%Dvojka dělí pravou stranu, musí dělit i levou. S ohledem na volbu $k$ je právě jeden člen sudý. BÚNO $x_1 = 2x_2$, přitom $y_1,z_1$ jsou liché.
%\[
%2 \equiv y_1^2 + z_1^2 = 2^{k+2} x_2y_1z_1 - 4x_2^2 \equiv 0 \pmod{4},
%\]
%což je spor.
%\end{reseni}
\begin{pozn}
K posledním třem úlohám se možná vrátíme na poslední lize 16. prosince, řešení proto zveřejníme později.
\end{pozn}
\end{document}




%%%%%%%%%% Pro případné budoucí užití %%%%%%%%%%
% Teorie
\begin{lemma}[Factoring lemma]
Buďte $a,b,c,d \in \N$ taková, že $ab = cd$. Pak existují $m,n,p,q \in \N$ taková, že $\gcd\ce{n,p} = 1$ a
\[
a = mn, \quad b = pq, \quad c = mp, \quad d = nq.
\]
\end{lemma}
\begin{lemma}[Vietovy vzorce]
Nechť je dán polynom $ax^2 + bx + c$. Pro kořeny $x_1,x_2$ tohoto polynomu platí
\[
x_1 + x_2 = -\frac{b}{a}, \quad x_1 \cdot x_2 = \frac{c}{a}.
\]
\end{lemma}


% Příklady
\begin{prikl} % Factoring lemma
Nechť $a,b,c,d \in \N$ splňují $ab = cd$. Dokažte, že $a+b+c+d$ je složené číslo.
\end{prikl}
\begin{prikl} % Vieta_Jumping
Buďte $x,y \in \N$ takové, že $xy \mid x^2 + y^2 + 1$. Dokažte, že
\[
\frac{x^2 + y^2 +1}{xy} = 3.
\]
\end{prikl}
\begin{prikl} % Vieta Jumping
Buďte $a,b \in \N$ takové, že $ab+1 \mid a^2 + b^2$. Dokažte, že $\frac{a^2+b^2}{ab+1}$ je druhou mocninou přirozeného čísla.
\end{prikl}