\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}
\setcounter{chapter}{5}
\chapter{Teorie čísel II}
\section{Teorie}
\begin{definice}
Buď $n \in \N$. Pro každé prvočíslo $p$ je jednoznačně určený exponent v~prvočíselném rozkladu čísla~$n$. Tento exponent budeme označovat $v_p(n)$ a říkat mu $p$-valuace čísla $n$. Je-li $(p,n)=1$, pak $v_p(n)=0$.
\end{definice}
%%
\begin{veta}
Pro libovolná $a,b \in \N$ a prvočíslo $p$ platí
\begin{enumerate}[(i)]
\item $v_p(ab)=v_p(a)+v_p(b)$
\item $v_p(a+b)\geq \min\{v_p(a),v_p(b)\}$
\item Pokud $v_p(a) \neq v_p(b)$, pak dokonce $v_p(a+b)=\min\{v_p(a),v_p(b)\}$.
\item $v_p((a,b))=\min\{v_p(a),v_p(b)\}$
\item $v_p([a,b])=\max\{v_p(a),v_p(b)\}$
\end{enumerate}
\end{veta}
%%
\begin{veta}
Buď $p$ liché prvočíslo. Buďte $a,b \in \N$ nedělitelná $p$ taková, že $p \mid (a-b)$. Pak pro všechna $n \in \N$ platí
\[
v_p(a^n-b^n)=v_p(n)+v_p(a-b).
\]
\end{veta}
%%
\begin{veta}
Buď $p$ liché prvočíslo. Buďte $a,b \in \N$ nedělitelná $p$ taková, že $p \mid a+b$. Pak pro všechna $n \in \N$ {\bf lichá } platí
\[
v_p(a^n+b^n)=v_p(n)+v_p(a+b).
\]
\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}
Nechť pro $a,b,c \in \N$ platí $a\mid b^3$, $b\mid c^3$, $c \mid a^3$. Dokažte, že $abc \mid (a+b+c)^{13}$.
\end{prikl}
\begin{reseni}
Z definice $p$-valuace pro přirozená $x,y$ vyplývá, že $x \mid y$ právě tehdy, když $v_p(x)=v_p(y)$ pro všechna prvočísla $p$. Přeložme dokazované tvrzení do řeči $p$-valuací: Pokud $v_p(a) \leq 3v_p(b)$, $v_p(b) \leq 3v_p(c)$, $v_p(c) \leq 3v_p(a)$, pak $v_p(abc) \leq v_p((a+b+c)^{13})$. Bez újmy na obecnosti předpokládejme, že $v_p(a)$ je nejmenší z čísel $v_p(a)$, $v_p(b)$, $v_p(c)$. Pak 
\[
v_p((a+b+c)^{13}) \geq 13\cdot \min( v_p(a), v_p(b), v_p(c)) = 13v_p(a),
\]
ale
\[
v_p(abc)=v_p(a)+v_p(b)+v_p(c) \leq v_p(a)+4v_p(c) \leq 13v_p(a) \leq v_p((a+b+c)^{13}).
\]
Což jsme chtěli dokázat.
\end{reseni}
%%%%%
\begin{prikl}
Nechť $a,b,c,d \in \N$ splňují $ab=cd$. Ukažte, že platí
\[
(a,c)\cdot (a,d)=a\cdot (a,b,c,d).
\]
\end{prikl}
\begin{reseni}
Označme $v_p(a)=x$, $v_p(b)=y$, $v_p(c)=z$, $v_p(d)=w$. Snažíme se dokázat
\[
\min(x,z)+ \min(x,w)=x+\min(x,y,z,w)
\]
za předpokladu, že $x+y=z+w$. Bez újmy na obecnosti $z\leq w$. Pokud $x$ minimum, pak díky dané rovnosti je $y$ maximum. Naopak pokud $x$ je maximum, pak $y$ je minimum. V prvním případě dostaneme $x+x=x+x$ a v druhém $z+w=x+y$, což platí. Pokud $x$ není minimum ani maximum, pak totéž platí pro $y$. Dokazovaná rovnost je pak tvaru $z+x=x+z$, což opět platí. Jelikož tyto úvahy platí pro každé prvočíslo $p$, tak je zadaná rovnost dokázaná.
\end{reseni}
%%%%%
\begin{prikl}
Buďte $a_1,a_2,\dots,a_k,b_1,b_2,\dots,b_k \in \N$ taková, že $(a_i,b_i)=1$ pro každé $i\in\{1,2,\dots,k\}$. Dále buď $m=[b_1,\dots,b_k]$. Ukažte, že platí
\[
\left( \frac{a_1m}{b_1},\frac{a_2m}{b_2},\dots,\frac{a_km}{b_k} \right)=(a_1,a_2,\dots,a_k).
\]
\end{prikl}
\begin{reseni}
Vezměme si libovolné prvočíslo $p$. Stačí nám dokázat, že $p$-valuace levé $(L)$ a pravé $(P)$ strany je stejná.
\begin{align*}
v_p(L)&=\min\left(v_p\left(\frac{a_1m}{b_1}\right), v_p\left(\frac{a_2m}{b_2}\right), \dots,v_p\left(\frac{a_km}{b_k}\right)\right),\\
v_p(P)&=\min(v_p(a_1),v_p(a_2),\dots,v_p(a_k)).
\end{align*}
Ale zároveň platí $v_p(a_im/b_i)=v_p(a_i)+v_p(m)-v_p(b_i)$ a $v_p(m)=\max (v_p(b_1),\dots,v_p(b_k))$. Nyní rozebereme dvě možnosti.\\
Pokud $v_p(b_i)=0$ pro všechna $i$, tak i $v_p(m)=0$. Poté zřejmě $v_p(a_i)+v_p(m)-v_p(b_i)=v_p(a_i)$ pro každé $i$. Pak je ale $v_p(a_im/b_i)=v_p(a_i)$, a to znamená, že také $v_p(L)=v_p(P)$. \\
Nechť pro nějaké $b_i$ platí $v_p(b_i)\neq 0$. Vezměme $i$ takové, že $v_p(b_i)$ je největší, takže $v_p(m)=v_p(b_i)$. Pak $v_p(a_i)+v_p(m)-v_p(b_i)=v_p(a_i)$. Jelikož ale $p \mid b_i$ a protože $(a_i,b_i)=1$, tak $p \nmid a_i$. To znamená, že $v_p(a_i)=0$. Proto $v_p(a_im/b_i)=0$ a levá strana není dělitelná prvočíslem $p$, stejně jako pravá.
\end{reseni}
%%%%%
\begin{prikl}
Najděte všechna přirozená čísla $n$, pro která existují přirozená $x,y$ a $k$ taková, že $(x,y)=1, k>1$  a $3^n=x^k+y^k$.
\end{prikl}
\begin{reseni}
$k$ musí být liché. Pokud by bylo sudé, pak je součet dvou čtverců $x^k+y^k$ dělitelný $3$, z toho plyne $3 \mid x$, $3\mid y$ a to je spor s $(x,y)=1$. Zvolme prvočíslo splňující $p\mid x+y$, $p$ je nutně liché, takže $v_p(3^n)=v_p(x^k+y^k)$. S využitím LTE lemma dostaneme $v_p(3^n)=v_p(x^k+y^k)=v_p(k)+v_p(x+y)$. Ale $p \mid x+y$ znamená, že $v_p(x+y) \geq 1 >0$ a tedy $v_p(3^n)=v_p(k)+v_p(x+y)>0$, proto $p=3$. Protože jsme zvolili $p$ libovolné, pak $x+y=3^m$ pro přirozené $m$. Máme dva případy:
\begin{enumerate}  
\item $m>1$. Indukcí se snadno dokáže, že $3^a\geq a+2$ pro všechna $a\geq 1$, takže $v_3(k)\leq k-2$. Nechť $M=\max (x,y)$. Jelikož $x+y=3^m\geq 9$, máme $M\geq 5$. Potom
\[
x^k+y^k\geq M^k=M\cdot M^{k-1}>\frac{1}{2}3^m5^{k-1} \geq 3^m5^{k-2} \geq 3^{m+k-2}\geq 3^{m+v_3(k)}=3^n,
\]
což je spor.
\item $m=1$. Potom $x+y=3$, $x=1$, $y=2$ (nebo naopak). Dále $3^{1+v_3(k)}=1+2^k$. Ale $3^{v_3(k)}\leq k$. Proto
$$1+2^k=3^{v_3(k)+1}\leq 3k \Rightarrow 2^k+1\leq3k.$$
Poslední nerovnost splňuje jen $k=3$. Dopočítáme $(x,y,n,k)=(1,2,2,3)$, $(2,1,2,3)$.
\end{enumerate}
Odpověd je $n=2$. 
\end{reseni}

%%%%%
\begin{prikl}
Nechť $p$ je prvočíslo a $m>1$ je přirozené číslo. Ukažte, že pokud pro přirozená $x>1$, $y>1$ platí
\[
\frac{x^p+y^p}{2}=\left( \frac{x+y}{2}\right)^m,
\]
pak $m=p$.
\end{prikl}
\begin{reseni}
Indukcí vzhledem k $p$ snadno dokážeme, že $\frac{x^p+y^p}{2}\geq \left(\frac{x+y}{2}\right)^p$ pro všechna přirozená $p$. Jelikož $\frac{x^p+y^p}{2}= \left(\frac{x+y}{2}\right)^m$, tak nutně $m\geq p$. Nechť $d=(x,y)$, $x=dx_1$, $y=dy_1$, kde $(x_1,y_1)=1$. Dosaďme $2^{m-1}(x_1^p+y_1^p)=d^{m-p}(x_1+y_1)^m$. Předpokládejme, že $p$ je liché. Zvolme $q$ prvočíselného dělitele $x_1+y_1$. Buď $v=v_q(x_1+y_1)$. Pokud $q$ je liché, pak $v_q(x_1^p+y_1^p)=v+v_q(p)$ a $v_q(d^{m-p}(x_1+y_1)^m)\geq mv$. Takže $m \leq 2$ a $p \leq 2$, což je spor. Pokud je $q=2$, pak $m-1+v \geq mv$, tedy $v \leq 1$ a $x_1+y_1=2$. Nutně $x=y$, což hned dává $m=p$.\\
Nyní předpokládejme, že  $p=2$. Vidíme, že $x+y \geq 4$ a $\frac{x^2+y^2}{2}<2\left(\frac{x+y}{2}\right)^2\leq \left(\frac{x+y}{2}\right)^3$. Dostáváme $m=2$. Stačí už jen ukázat, že případy $(x,y)=(1,2)$, $(2,1)$ nevyhovují.
\end{reseni}

%%%%%
\begin{prikl}
Najděte všechna přirozená $a,b>1$ splňující $b^a \mid a^b-1$.
\end{prikl}
\begin{reseni}
Nechť $p$ je nejmenší prvočíselný dělitel $b$ a $m$ nejmenší přirozené číslo, pro které $p \mid a^m-1$. Potom $m\mid b$ a $m \mid p-1$, takže každý prvočíselný dělitel $m$ dělí $b$ a je menší než $p$. Nutně proto $m=1$. Pokud je $p$ liché, máme $av_p(b)\leq v_p(a-1)+v_p(b)$ a $a-1\leq (a-1)v_p(b) \leq v_p(a-1)$ - spor. Zbývá $p=2$, $b$ je sudé, $a$ je liché a $av_2(b)\leq v_2(a-1)+v_2(a+1)+v_2(b)-1$. Dále $a \leq (a-1)v_2(b)+1\leq v_2(a-1)+v_2(a+1)$, což je možné jen pokud $a=3$, $v_2(b)=1$. Položme $b=2B$ a dosaďme $8b^3 \mid 3^{2B}-1$. Buď $q$ nejmenší prvočíselný dělitel $B$ (jistě lichý) a $n$ nejmenší přirozené číslo splňující $q \mid 3^n-1$. Poté $n\mid 2B$ a $n \mid q-1$, proto $n$ je 1 nebo 2, takže $q \mid 3-1=2$ nebo $q \mid 3^2-1=8$, a to nelze. Proto $B=1$ a $b=2$. Zadání splňuje jen dvojice $(a,b)=(3,2)$. 
\end{reseni}
%%%%%%
\begin{prikl}\label{priklad6.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 (až na pořadí a volbu znamének).
\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{priklad6.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}
Nechť $n \in \N_0$ je libovolné. Dokažte, že existují čísla $a,b,c,d \in \Z$ taková, že
\[
a^2 + b^2 + c^2 + d^2 = n.
\]
Můžete využít Eulerovu identitu o čtyřech čtvercích:
\begin{align*}
(a_1^2 + a_2^2 + a_3^2 + a_4^2) \cdot (b_1^2 + b_2^2 + b_3^2 + b_4^2) &= (a_1b_1 + a_2b_2 + a_3b_3 + a_4b_4)^2 +\\
&+ (a_1b_2 - a_2b_1 + a_3b_4 - a_4b_3)^2 +\\
&+ (a_1b_3 - a_2b_4 -a_3b_1 + a_4b_2)^2 +\\
&+ (a_1b_4 +a_2b_3 - a_3b_2 - a_4b_1)^2
\end{align*}
\end{prikl}
\begin{reseni}
Zřejmě tvrzení platí pro 0,1 a 2. Stačí jej proto dokázat pro lichá prvočísla, zbytek pak plyne z Eulerovy identity o čtyřech čtvercích. Buď proto $p$ libovolné liché prvočíslo. Zbytkové třídy $a^2$ jsou různé pro různá $a \in \{0,1,\dots, \frac{p-1}2\}$, vždyť kongruence $x^2 - a^2$ pro dané $a$ má modulo $p$ právě dvě řešení, přičemž druhé je $-a$, které v dané množině neleží. Podobně pro $b \in \{0,1,\dots,\frac{p-1}2\}$ jsou zbytkové třídy $-1-b^2$ rozdílné.

Máme $\frac{p+1}{2}$ zbytkových tříd pro $a^2$ a $\frac{p+1}{2}$ zbytkových tříd pro $-1-b^2$. Z Dirichletova principu tedy existují $a,b \in \{0,1,\dots,\frac{p-1}2\}$ taková, že
\[
a^2 \equiv - b^2 - 1 \pmod{p} \quad \text{ekvivalentně} \quad a^2 + b^2 + 1^2 + 0^2 = kp
\]
přitom určitě platí, že $k < p$ (vzhledem k tomu, že $a,b \leq \frac{p-1}{2}$).

Zvolme nyní $m\in\N$ nejmenší takové, že $mp = x_1^2 + x_2^2 + x_3^2 + x_4^2$ pro nějaká $x_i \in \Z$. Ukážeme sporem, že $m = 1$. Předpokládáme tedy, že $m \geq 2$.

Uvažme $y_i \equiv x_i \pmod{m}$, kde $y_i \in \langle \frac{-m+1}2, \frac{m}2 \rangle \cap \Z$. Máme
\[
0 \equiv x_1^2 + x_2^2 + x_3^2 + x_4^2 \equiv y_1^2 + y_2^2 + y_3^2 + y_4^2 \pmod{m}.
\]
Jistě tedy
\[
y_1^2 + y_2^2 + y_3^2 + y_4^2 = rm
\]
pro nějaké $0 \leq r \leq m$.

Pokud by nastal případ $r = m$, pak $y_1 = y_2 = y_3 = y_4 = \frac{m}2$ a nutně jsou všechna $x_i$ dělitelná $\frac{m}{2}$. Odtud pak $m^2 \mid mp$, tedy $m \mid p$, ale $2 \leq m< p$, což je spor.

Pokud by nastal případ $r = 0$, pak $y_1 = y_2 = y_3 = y_4 = 0$ a opět $m^2 \mid mp$, což dá spor.

Vynásobme rovnosti a využijme Eulerovy identity o čtyřech čtvercích
\begin{align*}
x_1^2 + x_2^2 + x_3^2 + x_4^2 &= mp,\\
y_1^2 + y_2^2 + y_3^2 + y_4^2 &= mr,\\
z_1^2 + z_2^2 + z_3^2 + z_4^2 &= m^2rp.
\end{align*}
Při pohledu na Eulerovu identitu modulo $m^2$ vidíme, že pro všechna $i$ platí $m \mid z_i$. Můžeme tudíž uvážit
\[
\ce{\frac{z_1}{m}}^2 + \ce{\frac{z_2}{m}}^2 + \ce{\frac{z_3}{m}}^2 + \ce{\frac{z_4}{m}}^2 = rp,
\]
kde ale $1 \leq r < m$. To je spor s minimalitou $m$. Nutně tedy $m = 1$.
\end{reseni}
%%%%%
\begin{prikl}
Dokažte, že neexistuje žádný polynom $f$ s celočíselnými koeficienty takový, že
\[
f(23) =  36 \quad \text{a} \quad f(11) = 6.
\]
\end{prikl}
\begin{reseni}
Uvažme libovolný polynom $f = \sum_{i=1}^n a_i x^i$, $a_i \in \Z$. Uvažme $f(a) - f(b)$ pro nějaká $a,b \in \Z$. Pak
\[
f(a) - f(b) = a_n(a^n - b^n) + a_{n-1}(a^{n-1} - b^{n-1}) + \dots + a_1 \cdot (a-b) + a_0 \cdot 0.
\]
Jistě pro každé $k \in \N_0$
\[
(a-b) \mid (a^k - b^k) \quad \text{vždyť} \quad a^k - b^k = (a-b) \cdot (a^{k-1} + a^{k-2}b + \dots + ab^{k-2} + b^{k-1}).
\]
Nutně proto $(a-b) \mid (f(a)-f(b))$, ale
\[
a-b = 23-11 = 12 \nmid 30 = 36-6 = f(a) - f(b).
\]
\end{reseni}
\end{document}

\begin{prikl}
Pro $a,b \in \N$ platí, že $a^n+n\mid b^n+n$ pro každé $n\in \N$. Ukažte, že $a=b$.
\end{prikl}
%%%%%
\begin{prikl}
Najděte všechna $n \in \N$ pro něž $n^2 \mid 2^n+1$.
\end{prikl}
%%%%%
\begin{prikl}
Nechť $p$ je prvočíslo. Dokažte, že existuje prvočíslo $q$ takové, že pro žádné $n \in \N$ není $n^p-p$ dělitelné $q$.
\end{prikl}
%%%%%
\begin{prikl}
Najděte všechna přirozená čísla $n$, pro která existují přirozená $x,y$ a $k$ taková, že $(x,y)=1, k>1$  a $3^n=x^k+y^k$.
\end{prikl}