\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{verbatim}

\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

\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 }

\begin{document}
\setcounter{chapter}{6}
\chapter{Teorie čísel II}
%\section{Teorie}

\begin{prikl}% Netusim odkud
Dokažte, že v posloupnosti $\ce{2^n-3}_{n=0}^{\infty}$ je nekonečně mnoho násobků $5$ a nekonečně mnoho násobků $13$, ale žádný násobek $65$.
\end{prikl}
\begin{reseni}
Nejprve vyřešme kongruence $2^n \equiv 3$ modulo 5 a 13.
\begin{itemize}
\item Modulo 5:
\[
2^n \equiv 3 \pmod{5}
\]
nejprve uvažme čísla $2^n$ modulo 5
\begin{center}
\begin{tabular}{c|ccccccc}
$n$			& 0 & 1 & 2 & 3 & 4 & 5 & $\dots$\\\hline
$2^n \pmod{5}$	& 1 & 2 & -1 & -2 & 1 & 2 & $\dots$
\end{tabular}
\end{center}
Vidíme, že řešení závisí jen na zbytku $n$ po dělení 4, tj. řešení jsou právě $n \equiv 3 \pmod{4}$.
\item Modulo 13:
\[
2^n \equiv 3 \pmod{13}
\]
opět uvažme následující tabulku
\begin{center}
\begin{tabular}{c||ccc|ccc|ccc|ccc|cc}
$n$			& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & $\dots$\\\hline
$2^n \pmod{13}$	& 1 & 2 & 4 & 8 & 3 & 6 & -1 & -2 & -4 & -8 & -3 & -6 & 1 & $\dots$
\end{tabular}
\end{center}
Řešení jsou tedy $n \equiv 4 \pmod{12}$.
\end{itemize}
Zbývá ukázat, že neexistuje řešení modulo 65. To by znamenalo, že $n \equiv 3 \pmod{4}$ a zároveň $n \equiv 4 \pmod{12}$, což je spor.
\end{reseni}


\begin{prikl}% MO - A59ii - 3
Určete všechna přirozená čísla $m$, $n$ taková, že $n \mid 2m-1$ a $m \mid 2n-1$.
\end{prikl}
\begin{reseni}
Pokud neplatí $m = 2n-1$ ani $n = 2m-1$, pak $2n-1 \geq 2m$ a $2m-1 \geq 2n$. Což dává spor. Proto platí alespoň jedna z rovností.
\begin{itemize}
\item Jestliže $m = 2n-1$, pak $2m - 1 = 4n-3$ a dostáváme $n \mid 4n-3$, tj. $n \mid 3$. Odtud $n$ může být 1 nebo 3, čemuž odpovídají řešení $(1,1)$ a $(5,3)$.
\item Z $n = 2m-1$ dostaneme opět řešení $(1,1)$ a jedno nové řešení $(3,5)$.
\end{itemize}
Řešení $(m,n)$ jsou $(1,1)$, $(3,5)$ a $(5,3)$.
\end{reseni}

\begin{prikl}%77
Nechť $n \in \N$. Dokažte, že pokud $2 + 2\cdot\sqrt{28n^2 + 1} \in \N$, pak je též druhou mocninou nějakého přirozeného čísla.
\end{prikl}
\begin{reseni}
Nechť $2 + 2\cdot\sqrt{28n^2 + 1} = m \in \N$. Pak $2\cdot\sqrt{28n^2 + 1} = m-2$, tj. 
\[
4\cdot\ce{28n^2 + 1} = m^2 - 4m + 4.
\]
Podíváme-li se na obě dvě strany rovnice modulo 4, vidíme, že $2 \mid m$, tedy $m = 2k$. Po dosazení a vydělení rovnice čtyřmi dostáváme
\[
28n^2 + 1 = k^2 - 2k + 1,
\]
tedy $28n^2 = k^2 - 2k$. Nutně $2 \mid k$, položme $k = 2q$, dosaďme a vydělme čtyřmi
\[
7n^2 = q\cdot\ce{q-1}.
\]
Protože dvě po sobě jdoucí čísla jsou vždy nesoudělná, dostáváme, že jedno z čísel $q$ a $q-1$ je čtverec a druhé sedminásobek čtverce (druhé mocniny přirozeného čísla). Rozeberme tyto případy zvlášť
\begin{itemize}
\item Nechť $q = 7x^2$, $q-1 = y^2$. Pak $7x^2 - y^2 = 1$. Podívejme se na tuto rovnici modulo 7. Dostáváme $y^2 \equiv -1 \pmod{7}$, což nelze.
\item Nechť $q = x^2$, $q-1 = 7y^2$. V tomto případě $m = 2k = 4q = 4x^2 = (2x)^2$, tedy $m$ je čtverec, což jsme chtěli dokázat.
\end{itemize}
Ze zadání nebylo naším cílem nalézt nějaké řešení. Poznamenejme však, že řešení existuje nekonečně mnoho. Řešili bychom Pellovu rovnici
\[
x^2 - 7y^2 = 1.
\]
Jedno z řešení je například $(8,3)$.
\end{reseni}

\begin{prikl}%6-59
Najděte čtyřciferné číslo~$abcd$ takové, že $4\cdot abcd = dcba$.
\end{prikl}
\begin{reseni}
$a,b,c,d$ jsou cifry, tj.~čísla z~množiny $\zm{0,1,\dots,9}$.\\
Z ~$4\cdot abcd = dcba$ jednak plyne, že $a<3$, neboť jednak, že $dcba$ je sudé. Čili~$a$ je sudá cifra, menší než~tři, a~různá od~nuly ($abcd$ je čtyřciferné). Tedy $a=2$.\\
Z ~$4\cdot 2bcd = dcb2$ plyne, že $d\geq8$ a~součin $4\cdot d$ končí na~2. Tedy $d=8$.\\
Nyní máme $4\cdot 2bc8=8cb2$, neboli
\begin{align*}
8000+400b+40c+32&=8000+100c+10b+2\\
390b+30&=60c\\
13b+1&=2c
\end{align*}
Protože je pravá strana sudá, musí být i~levá, tedy $b$ je liché. Pravá je navíc nejvíce~18. Celkem~$b=1$, odkud $c=7$. Takže $abcd=2178$.
\end{reseni}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl}%6-62
Dokažte, že posloupnost $a_n=\sqrt{24n+1}, n\in\N$, obsahuje všechna prvočísla kromě~2 a~3.
\end{prikl}
\begin{reseni}
Nejprve zjištěme, pro~které hodnoty~$n$ jsou~$a_n$ přirozená čísla. Je to ekvivalentní tomu, že existuje $q\in\N$ takové, že $24n+1=q^2$, neboli $$n=\frac{q^2-1}{24}=\frac{(q-1)(q+1)}{24}.$$
Protože $n\in\N$, musí $24\mid(q-1)(q+1)$. Proto je $q$ liché a~$q-1$, $q+1$ jsou dvě po sobě jdoucí sudá čísla. Právě jedno z~nich je tedy dělitelné dokonce čtyřmi, jejich součin tedy osmi. Jedno z~čísel $q-1$, $q+1$ navíc musí být dělitelné třemi. Celkem $q\pm1=6s$, neboli $q=6s\pm 1$, kde $s\in\N$. Přirozených hodnot nabývá posloupnost~$a_n$ pro~čísla $$n=\frac{6s(6s\pm2)}{24}=\frac{s(3s\pm1)}2,\quad s\in\N,$$
přičemž $a_n=6s\pm1$. Každé prvočíslo od~$5$ lze ale vyjádřit ve~tvaru~$6s\pm1$ (čísla ze zbylých zbytkových tříd modulo~6 jsou dělitelné~2 -- zbytky $0,\pm2$, či~3 -- zbytky $0,3$).
\end{reseni}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl}%6-81
Najděte nejmenší $a\in\N$ takové, že $1971\mid \zk{50^n+a\cdot 23^n}$, pro~libovolné liché~$n$.
\end{prikl}
\begin{reseni}
Požadujeme, aby $50^n+a\cdot 23^n \equiv 0\pmod{1971}$.\\
Protože $1971=27\cdot 73$ a~$(27,73)=1$, řešme problém modulo~27 a~73 zvlášť, a~poté využijme Čínskou zbytkovou větu.\\
Protože $n$ je liché, platí $$0\equiv 50^n+a\cdot 23^n\equiv \zk{-4}^n + \zk{-4}^n a \equiv -4^n(a+1)\pmod{27}.$$ Kvůli nesoudělnosti~4 a~27 můžeme obě strany kongruence $0 \equiv -4^n(a+1)\pmod{27}$ podělit $-4^n$, odkud $0\equiv a+1\pmod{27}$, tedy $a\equiv -1 \pmod{27}$.\\
Analogicky $$0\equiv 50^n+a\cdot 23^n\equiv \zk{-23}^n +a\cdot 23^n \equiv 23^n(a-1) \pmod{73}$$ a~z~nesoudělnosti~23 a~73 můžeme obě strany kongruence $0\equiv 23^n(a-1) \pmod{73}$ podělit $23^n$, odkud $0\equiv a-1\pmod{73}$, tedy $a\equiv 1 \pmod{73}$.\\
Z~druhé kongruence vyjádřeme $a=73s+1$, $s\in\N_0$, dosaďme do~první, a~upravujme přičítáním násobků modulu k~jednotlivým stranám, či~vydělením obou stran číslem nesoudělným s~modulem.
\begin{align*}
73s+1&\equiv -1 \pmod{27}\\
73s&\equiv -2 \pmod{27}\\
-8s&\equiv -2 \pmod{27}\\
4s&\equiv 1 \pmod{27}\\
4s&\equiv 28 \pmod{27}\\
s&\equiv 7 \pmod{27}
\end{align*}
Tedy $s=27r+7$, $r\in\N_0$, a~dosazením $a=73(27r+7)+1=1971r+512$, $r\in\N_0$, neboli $a\equiv 512\pmod{1971}$. Nejmenší přirozené~$a$ zřejmě dostaneme volbou~$r=0$, a~to~$a=512$.
\end{reseni}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl}%6-95 aktualizováno
Dokažte, že součet $1^1+2^2+3^3+\dots+2015^{2015}$ není mocninou přirozeného čísla~$m^k$ s~$k\in\N$, $k\geq3$.
\end{prikl}
\begin{reseni}
Podíváme-li se na~součet modulo~4, zjistíme, že se v~něm periodicky opakuje sekvence $1,0,-1,0$ délky~4. Přičemž $2015\equiv3 \pmod{4}$, tedy součet končí~$-1$. Je tedy dělitelný~4.\\
Součet je sudý a~má-li být roven $m^k$ s~$k\geq3$, musí být dělitelný minimálně~8. Podívejme se tak na~něj modulo~8.\\
Buď $n \in \N$ sudé, $n > 2$, pak $8\mid n^n$. Je-li $n\in\N$ liché, a~$s\in\N$, $s\geq3$, pak $n^s\equiv n\pmod{8}$. Odtud $1^1+2^2+3^3+\dots+2015^{2015} \equiv 2^2+1+3+\dots +2015 =4+ \frac{1008(1+2015)}{2}=1\,016\,068\equiv 4 \pmod{8}$. Není tedy dělitelný~8, proto nelze zapsat jako~$m^k$ s~$k\geq3$.
\end{reseni}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl}%6-157
V~$\N^2$ řešte rovnici $19x^3-84y^2=1984$.
\end{prikl}
\begin{reseni}
Přepišme rovnici do tvaru $19\zk{x^3-100}=84\zk{y^2+1}$. Protože $7\mid 84$, dělí~7 pravou stranu, musí tak dělit i~levou. Navíc $(19,7)=1$.
\begin{align*}
19\zk{x^3-100}\equiv 0 \pmod{7}\\
x^3-100\equiv 0 \pmod{7}\\
x^3\equiv 2 \pmod{7}
\end{align*}
Podíváme-li se na~třetí mocniny zbytkových tříd modulo~7,
$$\begin{array}{c|*{7}{c}}
x\pmod7& 0& 1& 2& 3& 4\equiv-3& 5\equiv-2& 6\equiv-1\\ \hline
x^3\pmod7& 0& 1& 1& -1& 1& -1& -1
\end{array}$$
tedy neexistuje žádné přirozené číslo, jehož třetí mocnina by dávala zbytek~2 modulo~7. Proto rovnice nemá řešení.
\end{reseni}
%%%%%%%%%%%%%%%%%%%%

\begin{prikl}%6-142
Dokažte, že jsou-li $p,q\in\N$ taková čísla, že $$1-\frac12+\frac13-\frac14+\dots-\frac1{1318}+\frac1{1319}=\frac{p}q,$$
pak $1979\mid p$.
\end{prikl}
\begin{reseni}
Označme~$s$ uvedený součet. Zde $$s=\sum_{k=1}^{1319} \frac1{k} - 2\zk{\sum_{k=1}^{659} \frac1{2k}}= \sum_{k=1}^{1319} \frac1{k} - {\sum_{k=1}^{659} \frac1{k}} =  \sum_{k=660}^{1319} \frac1{k}.$$
Všimněme si, že $1979=660+1319$. Místo \uv{jednostranného celkového} sčítání sčítejme nyní \uv{z~obou stran do~poloviny}. Tedy $$s=\sum_{k=660}^{989} \zk{\frac1{k}+\frac1{1979-k} }=\sum_{k=660}^{989} \frac{1979}{k(1979-k)} = 1979\sum_{k=660}^{989} \frac{1}{k(1979-k)}=1979\cdot \frac{p_1}{q_1},$$
kde jsme poslední sumu vyjádřili jako podíl přirozených čísel~$p_1,q_1, (p_1,q_1)=1$.  Protože je 1979 prvočíslo, jsou s~ním jmenovatelé $ k(1979-k)$ nesoudělní, tedy i~jejich nejmenší společný násobek~a každý jeho dělitel, zejména $q_1$, je s~1979 nesoudělný.\\
Celkem $(1979\cdot p_1) \mid p$, odkud $1979\mid p$.
\end{reseni}
%%%%%%%%%%%%%%%%%%%%
\end{document}