\documentclass[11pt,a4paper]{book}
\usepackage{a4wide}
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage[T1]{fontenc}
\usepackage{mathptmx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{array}
\usepackage{enumerate}
\usepackage{paralist}


\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{\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{\kon}[3]{\ensuremath{{#1} \equiv {#2}\pmod{#3}}}
\newcommand{\imp}{\ensuremath{\Rightarrow}}
\newcommand{\ekv}{\ensuremath{\Leftrightarrow}}
\newcommand{\gon}[1]{\ensuremath{ \cos \frac{2\pi}{#1} + \I \sin \frac{2\pi}{#1}}}

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


\newtheorem{pr}{Příklad}
\newtheorem{pr*}[pr]{*Příklad}
\newtheorem*{veta}{Věta}
\newtheorem*{priklad}{Příklad}
\theoremstyle{definition}
\newtheorem*{definice}{Definice}
\theoremstyle{remark}
\newtheorem*{pozn}{Poznámka}


\renewcommand{\qedsymbol}{}		% zmena znaku na konci dukazu

\parindent=0mm
\pagestyle{empty}
\begin{document}
\setcounter{chapter}{7}
\chapter{Diofantické rovnice}
Jedná se o rovnice, u nichž hledáme pouze celočíselná řešení. Dá se dokázat, že neexistuje (a ani existovat nemůže) žádný univerzální postup řešení. Existují však různé metody, které nám v řadě konkrétních případů pomohou řešení nalézt.
\section{Lineární diofantické rovnice}
V této části se budeme zabývat speciální třídou diofantických rovnic, pro kterou univerzální postup řešení existuje.
\begin{definice}
Diofantickou rovnici ve tvaru
\[
a_1 x_1 + a_2 x_2 + \dots + a_n x_n = b,
\]
pro neznámé $x_1, \dots, x_n$ a daná čísla $a_1, \dots, a_n, b \in \Z$, nazveme \emph{lineární diofantickou rovnicí}.
\end{definice}
\begin{veta}
Diofantická rovnice o $n$ proměnných, kde $\ce{a_1, \dots, a_n} = 1$, má vždy řešení v $\Z$ a všechna řešení je možné popsat pomocí $n-1$ celočíselných parametrů.
\end{veta}
Místo důkazu této věty si celý postup předvedeme na konkrétním příkladu.
% Rozmysleme však ještě, co se stane, když nebude splněna podmínka $\ce{a_1, \dots, a_n} = 1$. V takovém případě je levá strana rovnice dělitelná $\ce{a_1, \dots, a_n}$. Pokud je tímto číslem dělitelná i pravá strana, tj. číslo $b$, pak můžeme krátit a po vykrácení již podmínka pro nové koeficienty splněna bude. V opačném případě řešení existovat nebude.
\begin{priklad}
Řešte v $\Z$
\[
18x + 20y + 15z = 1
\]
\end{priklad}
\begin{proof}[Řešení]
Nejprve si zvolíme jednu proměnnou a spočítáme největšího společného dělitele koeficientů všech ostatních. Na diofantickou rovnici se pak podíváme modulo toto číslo. V našem případě zvolme jako tuto proměnnou například $x$. Pak $(20,15) = 5$. Když se podíváme na rovnici modulo~$5$, dostáváme
\begin{align*}
18x &\equiv 1 \pmod{5}\\
3x & \equiv 6 \pmod{5}\\
x &\equiv 2 \pmod{5}\\
x &= 2+5t
\end{align*}
Dosadíme do zadané rovnice a vykrátíme
\begin{align*}
20y + 15z &= 1 - 18\cdot 2 - 18\cdot 5t\\
4y + 3z &= -7 - 18t
\end{align*}
Nyní celý postup opakujeme. Vybereme proměnnou $y$, pak největší společný dělitel koeficientů u zbývajících proměnných je $3$. Dostáváme
\begin{align*}
y &\equiv -1 \pmod{3}\\
y &= -1 + 3s
\end{align*}
Dosadíme a vykrátíme
\begin{align*}
3z &= -3 - 18t - 12s\\
z &= -1 - 6t - 4s
\end{align*}
Řešením jsou trojice
\[
\ce{x,y,z} \in \{ \ce{2+5t, -1+3s, -1 - 6t - 4s}\mid s,t\in \Z \}
\]
%což lze zapsat také jako
%\[
%[2,-1,-1] + \ce{5,0,-6}t + \ce{0,3,-4}s \quad s,t \in \Z
%\]
\end{proof}
\section{Příklady}
\begin{pr}
Je možné na dvouramenných vahách (ramena stejné délky) odvážit 1\,g nějakého zboží, máme-li k~dispozici pouze (libovolný počet) závaží tří hmotností: 153\,g, 135\,g a~425\,g? Pokud ano, jak to udělat? Vhodným způsobem zapište všechna možná řešení.
 %a~některé z~řešení explicitně vyčíslete
\end{pr}
\begin{pr}
Řešte diofantickou rovnici
\[
7x^2 + 5y + 13 = 0
\]
\end{pr}
\begin{pr}
Řešte diofantickou rovnici
\[
x^2 + 4z^2 + 6x + 7y + 8z = 1
\]
\end{pr}
\begin{pr}
Řešte diofantickou rovnici
\[
2x^2+xy=y^2+63.
\]
\end{pr}
\begin{pr}
Řešte diofantickou rovnici
\[
\frac{1}{x} + \frac{1}{y} = \frac{1}{p},
\]
kde $p$ je libovolné prvočíslo.
\end{pr}
\begin{pr}
Řešte diofantickou rovnici
\[
3^x = 4y + 5.
\]
\end{pr}
\begin{pr}
Řešte diofantickou rovnici
\[
x\ce{y+1}^2 = 243y.
\]
\end{pr}
\begin{pr}
Řešte v oboru přirozených čísel
\[
x+y+z = xyz
\]
\end{pr}
\begin{pr}
Řešte diofantickou rovnici
\[
x^2 + xy + y^2 = x^2y^2
\]
\end{pr}

\newpage
\begin{proof}[Řešení 1]
Sestavíme diofantickou rovnici 
\[
153x+ 135y +425z=1
\]
přičemž kladný počet závaží pokládáme na jedno rameno, záporný počet na druhé, kde je zboží.\\
Jde o lineární diofantickou rovnici, $(153,135)=9$.
$$\begin{array}{r@{}l@{}l}
425z&{}\equiv 1 &\pmod{9}\\
2z&{}\equiv 10 &\pmod{9}\\
z&{}\equiv 5 &\pmod{9}\\
z&{}=5+9t 
\end{array}$$
$$153x+ 135y +425(5+9t)=1$$
$$153x+ 135y=-2124-3825t$$
$$\begin{array}{r@{}l@{}l}
135y&{}\equiv -2124-3825t &\pmod{153}\\
-18y&{}\equiv 18 &\pmod{153}\\
-6y&{}\equiv 6 &\pmod{51}\\
-2y&{}\equiv 2 &\pmod{17}\\
y&{}\equiv -1 &\pmod{17}\\
y&{}=-1+17k 
\end{array}$$
$$153x+ 135(-1+17k) +425(5+9t)=1$$\vspace*{-2em}
\begin{align*}
153x&=-1989-2295k-3825t\\
x&=-13-15k-25t
\end{align*}
Množina řešení je tvaru $$K=\left\{ \left[-13-15k-25t;\; -1+51k;\; 5+9t \right], k,t\in\Z \right\}\text.$$
\end{proof}


\begin{proof}[Řešení 2]
Rovnice je lineární v proměnné $y$. Podívejme se na ni modulo 5.
\begin{align*}
7x^2 + 13 &\equiv 0 \pmod{5}\\
2x^2 &\equiv -3 \pmod{5}\\
x^2 &\equiv 1 \pmod{5}\\
x &= \pm 1+5t
\end{align*}
Dosadíme
\[
7(\pm1 + 5t)^2 + 5y + 13 = 5y + 20 \pm 70t + 175t^2
\]
Můžeme vyjádřit $y$ a dostaneme řešení ve tvaru
\[
[x,y] = [1+5t, -35t^2 - 14t -4] \quad \text{nebo} \quad [x,y] = [-1+5t, -35t^2 +14t - 4].
\]
\end{proof}

\begin{proof}[Řešení 3]
Všimněme si, že rovnice je lineární v proměnné $y$. Podívejme se na ni modulo 7.
\begin{align*}
x^2 + 6x + 4z^2 + 8z &\equiv 1 \pmod{7}\\
\ce{x+3}^2 + 4\ce{z+1}^2 \equiv 0 \pmod{7}
\end{align*}
Podívejme se na kvadratické zbytky modulo 7.
\[
\begin{array}{c|ccccccc}
n 	& 0	& 1	& 2	& 3	& 4	& 5	& 6	\\\hline
n^2	& 0	& 1	& 4	& 2	& 2	& 4	& 1
\end{array}
\]
Snadno ověříme, že řešení dostáváme jen pro $x+3 \equiv z+1 \equiv 0 \pmod{7}$. Odtud
\[
x = -3+7t \quad z = -1+7s
\]
a dosadíme do původní rovnice, abychom získali $y$.
\begin{align*}
7y &= -(x+3)^2 - 4(z+1)^2 + 14 = -49t^2 - 196 s^2 + 14\\
y &= -7t^2 - 28s^2 + 2
\end{align*}
\end{proof}

\begin{proof}[Řešení 4]
Řešíme rozkladem
\begin{align*}
2x^2+xy&=y^2+63\\
2x^2+xy-y^2&=63\\
(2x-y)(x+y)&=63=3^2\cdot 7
\end{align*}
Dělitelé 63 jsou $\pm1,\pm 3,\pm 7,\pm 9,\pm 21,\pm 63$.\\
Projdeme postupně všechny možnosti
\begin{align*}
2x-y&=63\;(-63) &2x-y&=21\;(-21) &2x-y&=9\;(-9)  \\
x+y&=1\;(-1) &x+y&=3\;(-3)  &x+y&=7\;(-7)\\
3x&=64\;(-64) &3x&=24\;(-24)  &3x&=16\;(-16)\\\
3\nmid 64&\phantom{={}} \text{NŘ} &x&=8\;(-8) & 3\nmid 16&\phantom{={}} \text{NŘ}\\
&& y&=-5\;(5)
\end{align*}
\begin{align*}
2x-y&=1\;(-1) &2x-y&=3\;(-3) &2x-y&=7\;(-7)  \\
x+y&=63\;(-63) &x+y&=21\;(-21)  &x+y&=9\;(-9)\\
3x&=64\;(-64) &3x&=24\;(-24)  &3x&=16\;(-16)\\\
3\nmid 64&\phantom{={}} \text{NŘ} &x&=8\;(-8) & 3\nmid 16&\phantom{={}} \text{NŘ}\\
&& y&=13\;(-13)
\end{align*}
$K=\left\{ [8,-5], [8,13], [-8,5], [-8,-13]\right\}$.\\
\end{proof}


\begin{proof}[Řešení 5]
Nejprve vynásobíme celou rovnici $xyp$ a dostáváme
\begin{align*}
xy - px - py &= 0\\
xy - px - py + p^2 &= p^2\\
\ce{x-p}\ce{y-p} &= p^2
\end{align*}
Dostáváme 6 možností, které musíme rozebrat (první závorka může být $\pm1, \pm p, \pm p^2$)
\begin{itemize}
\item $x-p = 1$, pak $y-p = p^2$ a dostáváme řešení $[p+1, p^2 + p]$
\item $x-p = p$, pak $y-p = p$ a dostáváme řešení $[2p, 2p]$
\item $x-p = p^2$, pak $y-p = 1$ a dostáváme řešení $[p^2+p, p+1]$
\item $x-p = -1$, pak $y-p = -p^2$ a dostáváme řešení $[p-1, p-p^2]$
\item $x-p = -p$, pak $y-p = -p$ a dostáváme $x=y=0$, což nevyhovuje zadání
\item $x-p = -p^2$, pak $y-p = -1$ a dostáváme řešení $[p-p^2, p-1]$
\end{itemize}
Úloha má tedy právě pět řešení.
\end{proof}


\begin{proof}[Řešení 6]
Rovnice je lineární v proměnné $y$. Podívejme se na ni modulo 4.
\[
\ce{-1}^x \equiv 1 \pmod{4}
\]
Odtud zřejmě $x = 2k$. Dosadíme do původní rovnice a vyjádříme $y$
\[
y = \frac{9^k - 5}{4}.
\]
\end{proof}


\begin{proof}[Řešení 7]
Z rovnice vyjádříme $x$
\[
x = \frac{243 y}{\ce{y+1}^2}
\]
Protože $\ce{y,y+1} = 1$, musí $\ce{y+1}^2 \mid 243 = 3^5$, tj. $\ce{y+1} \in \{\pm1, \pm 3, \pm 9\}$. Dopočítáme příslušná $x$:
\[
\begin{array}{c|cccccc}
y&0	&-2	&2	&-4	&8	&-10\\\hline
x&0	&-486	&54	&-108	&24	&-30
\end{array}
\]
Máme tedy 6 řešení.
\end{proof}


\begin{proof}[Řešení 8]
Rovnice je symetrická v proměnných $x,y,z$. Předpokládejme proto, že $x \leq y \leq z$, pak
\begin{align*}
xyz &= x+y+z \leq 3z\\
xy &\leq 3
\end{align*}
Nutně $x = 1$ a $y \in \{1,2,3\}$. Tyto případy dořešíme
\begin{itemize}
\item $x = y = 1$, pak $z = z+2$, což je spor s celočíselností $z$
\item $2x = y = 2$, pak $2z = z+3$, tedy $z = 3$.
\item $3x = y = 3$, pak $3z = z+4$, tedy $z = 2$, což je spor s $y \leq z$.
\end{itemize}
Dostáváme tedy šest řešení. $\ce{1,2,3}$ a všechny permutace.
\end{proof}

\begin{proof}[Řešení 9]
Rovnice je symetrická v proměnných $x,y$. Předpokládejme proto, že $x \leq y$, pak
\begin{align*}
x^2y^2 &= x^2 + xy + y^2 \leq 3y^2\\
x^2 &\leq 3
\end{align*}
Máme tedy tři možnosti pro $x$
\begin{itemize}
\item $x = 0$, pak $y = 0$
\item $x = 1$, pak $y = -1$, což je spor s předpokladem $x \leq y$
\item $x = -1$, pak $y = 1$
\end{itemize}
Dostáváme tři řešení (díky symetrii se nám vrátí vyloučené řešení).
\[
K = \{[0,0],[-1,1],[1,-1]\}.
\]
\end{proof}
\end{document}