\documentclass[11pt]{article}
\usepackage{a4wide}
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}

\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\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

\newtheorem{pr}{Příklad}
\newtheorem{hint}{Hint}

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

\begin{document}
\section*{Návodné příklady}
\begin{pr}%[MO - A52ii - 1]
Najděte základy $z$ všech číselných soustav, ve kterých $(41)_z$ dělí $(1001)_z$.
\end{pr}


\vfill

\begin{pr}%[MO - A52i - 4]
Určete všechna přirozená čísla $n>1$ taková, že v některé číselné soustavě o~základu $z \geq 5$ platí následující kritérium dělitelnosti: trojmístné číslo $(abc)_z$ je dělitelné číslem $n$, právě když je číslem $n$ dělitelné číslo $c + 3b - 4a$.
\end{pr}


\vfill


\begin{pr}%[MO - A58i - 3]
Najděte všechny dvojice přirozených čísel $x,y$ takové, že
\[
\frac{xy^2}{x+y}
\]
je prvočíslo.
\end{pr}


\vfill


\begin{pr}%[MO - A58ii - 1]
Hledané čtyřmístné přirozené číslo je dělitelné sedmi. Zapíšeme-li jeho číslice v~opačném pořadí, dostaneme větší číslo, které je také dělitelné sedmi. Navíc při dělení číslem~37 dávají obě zmíněná čtyřmístná čísla stejný zbytek. Určete původní čtyřmístné číslo.
\end{pr}


\vfill


\begin{pr}%[MO - A47ii - 1]
Dokažte, že pro každé přirozené číslo $n$ platí: 
\[
3^{n+3} \mid 1997^{3^n}  +1.
\]
\end{pr}


\vfill


\begin{pr}%[SNMÚ]
Dokažte, že pro každé přirozené číslo $n$ platí:
\[
n \mid \ce{3^n-2} \quad\Rightarrow\quad 3^n -1 \mid \ce{3^{3^n-1}-3}.
\]
\end{pr}


\vfill


\begin{pr}%[MO - A48ii - 1]
Aritmetický průměr několika navzájem různých prvočísel se rovná 27. Určete, jaké největší prvočíslo mezi nimi může být.
\end{pr}
\newpage
\section*{Nápověda k příkladům}
\begin{hint}
Uvědomte si, jak převést číslo zapsané v soustavě o základu $z$ do standardní desítkové soustavy. Podobně jako v desítkové soustavě můžeme rozepsat
\[
1568 = 1 \cdot 10^3 + 5\cdot 10^2 + 6\cdot 10^1 + 8 \cdot 10^0,
\]
lze tuto úvahu snadno zobecnit pro libovolný základ $z \in \N$
\[
(1568)_{z} = z^3 + 5z^2 + 6z + 8.
\]
Dále můžete využít Euklidův algoritmus.
\end{hint}


\vfill


\begin{hint}
Podobně jako v předchozím využijte přepisu původního čísla do desítkové soustavy. Protože se jedná o kritérium dělitelnosti, musí platit pro všechna $(abc)_z$. Vhodnou volbou cifer $a,b,c$ lze získat některá čísla, která $n$ musí dělit. 
\end{hint}


\vfill


\begin{hint}
Uvažme $m,n \in \Z$ taková, že $\ce{m,n} = 1$, kde $\ce{m,n}$ značí největšího společného dělitele čísel $m$, $n$. Pak platí
\[
\ce{m,m+n} = 1\qquad \text{a} \qquad \ce{m^2, m+n} = 1.
\]
\end{hint}


\vfill


\begin{hint}
Uvědomte si, že čísla $m,n$ dávají stejný zbytek po dělení číslem $k$ právě tehdy, když $k$ dělí jejich rozdíl.
\end{hint}


\vfill


\begin{hint}
Zápis $a^{b^c}$ lze zapsat s využitím závorek jako $a^{\ce{b^c}}$. Dále lze například využít vztahů
\begin{gather*}
a^{b+1} = a\cdot a^b,\\
a^{b\cdot c} = \ce{a^b}^c = \ce{a^{c}}^b,\\
a^3 + b^3 = (a+b)(a^2 - ab + b^2).
\end{gather*}
\end{hint}


\vfill


\begin{hint}
Využijte následující definice dělitelnosti pro celá čísla $a,b$:\\
Řekneme, že číslo $a$ dělí číslo $b$, píšeme $a \mid b$, jestliže existuje $k \in \Z$ takové, že $a\cdot k = b$.
\end{hint}


\vfill


\begin{hint}
Nalezněte horní hranici, pro hledané prvočíslo (tj. omezte ho shora). Je možné, aby v uvažovaném aritmetickém průměru mohla být všechna \uv{malá} prvočísla?
\end{hint}
\newpage


\section*{Řešení}
\begin{proof}[Řešení]
Protože se v čísle $(41)_z$ nachází cifra $4$, dostáváme, že $z \geq 5$. Nyní přepíšeme čísla v~soustavě o základu $z$ do desítkové soustavy. Budeme chtít určit, pro která $z$ platí
\[
4z + 1 \mid z^3 +1.
\]
Využijeme krok Euklidova algoritmu pro výpočet největšího společného dělitele
\[
z^3 + 1 = \ce{4z+1} \cdot \ce{\frac{z^2}{4} - \frac{z}{4^2} + \frac{1}{4^3}} + \frac{63}{4^3}.
\]
Protože jsou čísla $4$ a $4z+1$ nesoudělná, platí
\[
4z+1 \mid z^3 +1 \qquad \Leftrightarrow \qquad 4z+1 \mid 4^3\ce{z^3 +1}.
\]
Můžeme se proto zbavit zlomků
\[
4^3\ce{z^3 + 1} = \ce{4z+1}\cdot \ce{4^2z^2 - 4z + 1} + 63.
\]
Jistě $4z +1$ dělí levou stranu právě tehdy, když dělí pravou stranu této rovnosti. Celkem $4z + 1 \mid z^3 +1$, právě když $4z + 1 \mid 63$. Odtud $4z+1 \in \{1,3,7,9,21,63\}$. Spolu s odhadem $z \geq 5$ tj. $4z +1 \geq 21$ dostáváme jediné řešení $z = 5$ (vždyť $4z + 1 = 63$ nemá celočíselné řešení).
\end{proof}


\vfill


\begin{proof}[Řešení]
Přepíšeme podmínku do desítkové soustavy
\[
n \mid a\cdot z^2 + b\cdot z + c \qquad \Leftrightarrow \qquad n \mid c + 3b - 4a.
\]
Zvolme $a = b = c = 1$, pak
\[
n \mid z^2 + z + 1 \qquad \Leftrightarrow \qquad n \mid 0.
\]
Protože pravá strana ekvivalence platí vždy, dostáváme, že $n \mid z^2 + z + 1$. Dále zvolme $a = 1$, $b = 0$, $c = 4$, pak
\[
n \mid z^2 + 4 \qquad \Leftrightarrow \qquad n \mid 0.
\]
Opět odtud plyne, že $n \mid z^2 + 4$. Provedeme dva kroky Euklidova algoritmu
\begin{align*}
z^2 + z + 1 &= \ce{z^2 + 4} \cdot 1 + \ce{z - 3},\\
z^2 + 4 &= \ce{z-3}\cdot\ce{z+3} + 13.
\end{align*}
Dostáváme, že $n \mid 13$. Protože $13$ je prvočíslo a $n > 1$, je nutně $n = 13$. Dostali jsme podmínku nutnou. Dokážeme, že je i postačující, tj. nalezneme vhodné $z$, aby zadané kritérium platilo. V prvním kroku Euklidova algoritmu jsme dostali, že $n \mid z - 3$. Zvolme tedy $z = 16$ a ověřme, že
\[
13 \mid a\cdot 16^2 + b\cdot 16 + c \qquad \Leftrightarrow \qquad 13 \mid c + 3b - 4a.
\]
To snadno rozmyslíme, vždyť
\[
a\cdot 16^2 + b\cdot 16 + c = 13 \cdot \ce{20 a + b} + \ce{c + 3b - 4a}.
\]
Úloha má tedy jediné řešení $n = 13$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{proof}[Řešení]
Buď $d$ největší společný dělitel čísel $x$ a $y$. Pak platí $x = da$, $y = db$ pro nějaká $a,b \in \N$. Buď dále $p$ prvočíslo, pak můžeme psát
\begin{align*}
\frac{xy^2}{x+y} &= p,\\
d^3ab^2 &= dp\ce{a+b},\\
d^2ab^2 &= p\ce{a+b}.
\end{align*}
Jistě $b^2$ dělí levou stranu rovnice, musí dělit i pravou. Protože $\ce{b^2, a+b} = 1$, musí platit $b^2 \mid p$, proto $b = 1$. Dostáváme
\[
d^2a = p\ce{a+1}.
\]
Protože $a$ dělí levou stranu rovnice, musí dělit i pravou a $\ce{a, a+1} = 1$, musí proto platít $a \mid p$. Odtud $a = 1$, nebo $a = p$. Tyto dvě možnosti vyšetříme zvlášť
\begin{itemize}
\item Jestliže $a = 1$, dostáváme
\[
d^2 = 2p.
\]
Pak nutně $d = p = 2$ a dostáváme řešení $x = 2$, $y = 2$.
\item Jestliže $a = p$, dostáváme
\begin{align*}
d^2p &= p\ce{p+1},\\
d^2 &= p+1,\\
p &= \ce{d+1}\ce{d-1}.
\end{align*}
Odtud nutně plyne, že $d+1 = p$ a $d-1 = 1$. Tedy $d = 2$ a $p = 3$. To nám dává řešení $x = 6$, $y = 2$.
\end{itemize}
Celkem tedy dostáváme dvě řešení $\ce{x,y}$, a to $\ce{2,2}$ a $\ce{6,2}$.
\end{proof}


\vfill


\begin{proof}[Řešení]
Zapišme hledané číslo $n$ ve tvaru $\overline{abcd} = 1000a + 100b + 10c + d$. Položme $k = \overline{dcba}$. Nejprve uvažme poslední podmínku o dělitelnosti 37, kterou aplikujeme na rozdíl $n-k$ 
\[
37 \mid 1000a + 100b + 10c + d - 1000d - 100c - 10 b - a = 999\ce{a-d} + 90\ce{b-c} = 27\cdot37\ce{a-d} + 90\ce{b-c}.
\]
Protože $\ce{37, 90} = 1$, platí $37 \mid b-c$ a protože $0 \leq b,c \leq 9$, nastává rovnost $b = c$. Hledané číslo je tedy tvaru $\overline{abbd}$. Nyní aplikujeme podmínku o dělení sedmi na rozdíl $n-k$
\[
7 \mid 999\ce{a-d} + 90\ce{b-b} = 999\ce{a-d}.
\]
Protože $\ce{7,999} = 1$, platí $7 \mid a-d$. Protože $k>n$, je také $d > a$, navíc $n$ je tvaru $\overline{1bb8}$, nebo $\overline{2bb9}$. Abychom určili $b$, použijeme předpoklad o dělitelnosti sedmi na číslo $n$ v obou případech
\begin{gather*}
7 \mid 1000 + 100b + 10b + 8 \quad \Rightarrow \quad 7 \mid b,\\
7 \mid 2000 + 100b + 10b + 9 \quad \Rightarrow \quad 7 \mid b.
\end{gather*}
Dostáváme právě čtyři řešení: 1008, 1778, 2009, 2779.
\end{proof}

%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{proof}[Řešení]
Rozepíšeme číslo $1997^{3^n} + 1$ podle vzorce $a^3 + b^3 = \ce{a+b}\ce{a^2 - ab + b^2}$
\begin{multline*}
1997^{3^n} + 1 =  \ce{1997^{3^{n-1}} + 1}\ce{\ce{1997^{3^{n-1}}}^2 - 1997^{3^{n-1}} + 1} =\\
= \ce{1997^{3^{n-2}} + 1} \ce{\ce{1997^{3^{n-2}}}^2 - 1997^{3^{n-2}} + 1} \ce{\ce{1997^{3^{n-1}}}^2 - 1997^{3^{n-1}} + 1}=\\
= \ce{1997^{3^{0}} + 1} \prod_{i = 0}^{n-1} \ce{\ce{1997^{3^i}}^2 - 1997^{3^i} + 1} = 1998 \prod_{i = 0}^{n-1} \ce{\ce{1997^{3^i}}^2 - 1997^{3^i} + 1}.
\end{multline*}
Protože $3^3 \mid 1998$, stačí ukázat, že pro každé $i = 0,\dots,n-1$ platí $3 \mid ((1997^{3^i})^2 - 1997^{3^i} + 1)$.
Protože $1997 = 1998-1$, plyne z binomické věty, že
\[
3 \mid ((1997^{3^i})^2 - 1997^{3^i} + 1) \qquad \Leftrightarrow \qquad 3 \mid ((-1)^{3^i})^2 - (-1)^{3^i} + 1 = 3.
\]
Pravá strana ekvivalence zřejmě platí, proto $3^{n+3} \mid 1997^{3^n} + 1$ pro každé přirozené $n$.
\end{proof}


\vfill


\begin{proof}[Řešení]
Z podmínky $n \mid \ce{3^n - 2}$ dostáváme, že $3^n - 2 = kn$ pro vhodné $k \in \N$. Upravme nyní pravou stranu implikace
\[
3^n - 1 \mid \ce{3^{3^n - 1} - 3} = 3\ce{3^{3^n-2} - 1} = 3\ce{3^{kn} -1} = 3\ce{(3^{n})^k - 1}
\]
poslední výraz stačí rozepsat podle vzorce $a^k - b^k = \ce{a-b}\ce{a^{k-1} + a^{k-2}b + \dots + ab^{k-2} + b^{k-1}}$, tj.
\[
\ce{(3^n)^k - 1} = \ce{3^n - 1}\ce{(3^n)^{k-1} + (3^n)^{k-2} + \dots + 3^n + 1}.
\]
Tímto je důkaz hotov.
\end{proof}


\vfill


\begin{proof}[Řešení]
Označme $P$ množinu prvočísel, jejichž aritmetický průměr je 27 a která obsahuje hledané prvočíslo  $p^*$. Má-li být průměrem celé liché číslo, musí být součet sudého počtu čísel sudý a lichého počtu čísel lichý. Touto úvahou snadno zjistíme, že $2 \notin P$. Udělejme nyní horní odhad pro $p^*$
\[
\frac{3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + p^*}{9} \leq 27.
\]
Vyjádřením $p^*$ z této nerovnice dostáváme
\[
p^* \leq 145.
\]
Nyní stačí brát sestupně prvočísla od 145 a provádět příslušnou kontrolu. Největší prvočíslo menší než 145 je 139.
\[
\frac{3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 139}{9} = \frac{237}{9} = 26 + \frac{3}{9} .
\]
Můžeme zkusit nějaké použité prvočíslo odebrat nebo naopak nějaké nové přidat. Lze uvážit následující postupy
\begin{itemize}
\item Můžeme si všimnout, že jsme od požadované hodnoty vzáleni o $\frac{6}{9}$. Stačí tedy místo 23 vzít 23+6 = 29, což je také prvočíslo, a dostáváme
\[
\frac{3 + 5 + 7 + 11 + 13 + 17 + 19 + 29 + 139}{9} = 27.
\]
\item Bez odebírání prvočísel menších než 27 lze také dospět k výsledku
\[
\frac{3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 139}{11} = 27.
\]
\end{itemize}
Hledaným prvočíslem je $p^* = 139$.
\end{proof}
\end{document}