\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{prikl} %15
Nalezněte všechna prvočísla $p$, $q$ taková, že $p^2 - 2q^2 = 1$.
\end{prikl}
%%%%%%%%%%%%%%%%%%%%

\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{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{prikl} %57
Nalezněte nejmenší přirozené číslo takové, že odstraněním první cifry se toto číslo zmenší 57krát.
\end{prikl}
%%%%%%%%%%%%%%%%%%%%

\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{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{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{prikl} %Modifikace 108
Dokažte, že $2015 \mid \underbrace{55\dots5}_{360}$.
\end{prikl}
%%%%%%%%%%%%%%%%%%%%

\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{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{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{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}
\end{document}