\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage[T1]{fontenc}
\usepackage [utf8]{inputenc}
\usepackage[magyar]{babel}
\usepackage {amsmath}
\usepackage {amsthm}
\usepackage {amssymb}
\usepackage{graphicx}
\usepackage{indentfirst}

\evensidemargin 2cm
\textwidth 15cm

\hyphenation{}

\newtheorem{tetel}{Tétel}
\newtheorem{lemma}[tetel]{Lemma}
\newtheorem*{allitas}{Állítás}
\theoremstyle{definition}
\newtheorem{defi}{Definíció}
\newtheorem{pelda}{Példa}

\title{9. gyakorlat}
\author{Tóth Ágnes}
\date{2009. november 4.}

\begin{document}
\frenchspacing
\maketitle

Az alábbi részletek forrása \acite{bak} könyv.\marginpar{cite}

\section{Hat bizonyítás a prímszámok létezésére}\marginpar{section}

Ez már csak természetes, hogy ezen jegyzeteket a valószínűleg legrégebbi Könyv-Bizonyítással kezdjük, melyet általában Euklidésznek tulajdonítanak (\emph{Elemek} IX, 20)\marginpar{emph}. Azt mutatja meg, hogy a prímszámok sorozata nem ér véget.

\subsection{Második bizonyítás}
Vizsgáljuk először az $F_n=2^{2^n}+1$ \emph{Fermat számokat}\marginpar{emph} $n=1,2,\dots$-re\marginpar{dots}. Azt fogjuk megmutatni, hogy bármely két Fermat szám relatív prím, ezért végtelen sok prímszámnak kell lennie. E célból belátjuk a\marginpar{prod,qquad,ge}
$$\prod _{k=0}^{n-1} F_k = F_n-2\qquad (n\ge 1)$$
rekurziót, amiből allításunk azonnal következik. Valóban, ha $m$ osztja például $F_k$-t és $F_n$-et ($k<n$), akkor $m$ osztja $2$-t is, tehát $m=1$ vagy $2$. De $m=2$ nem lehet, hiszen minden Fermat szám páratlan.
A rekurziót $n$ szerinti indukcióval bizonyítjuk. Ha $n=1$, akkor $F_0=3$ és $F_1-2=3$. Az indukciós feltevés szerint következik, hogy
\marginpar{multline*, stackrel, textrm}
\begin{multline*}
\prod _{k=0}^n F_k = \left(\prod _{k=0}^{n-1} F_k\right) F_n\stackrel{\textrm{ind. felt.}}{=}(F_n-2)F_n=\\
=(2^{2^n}-1)(2^{2^n}+1)=(2^{2^{n+1}}-1)=F_{n+1}-2.
\end{multline*}


\subsection{Negyedik bizonyítás}

Legyen $\pi (x) := \{p\le x\,:\,p\in\mathbb{P}\}$\marginpar{mathbb} az $x$ valós számnál kisebb vagy egyenlő prímek száma.\footnote{Itt és a továbbiakban $\# A$ az $A$ halmaz elemszámát jelöli.}\marginpar{footnote} Számozzuk meg a prímszámokat növekvő sorrendben: $\mathbb{P}=\{p_1,p_2,p_3,\dots\}$ és tekintsük $x$ természetes logaritmusát, melyet a $\log (x) = \int _1^x \frac 1t\,\mathrm{d}t$\marginpar{int, frac, mathrm} kifejezéssel definiálunk.
Hasonlítsuk össze az $f(t)=\frac 1t$ függvény grafikonja alatti területet egy a függvény grafikonját felülről közelítő lépcsős függvénnyel (lásd \aref{kep}. ábra)\marginpar{aref}.
Így $n\le x\le n+1$-re
$$\log x\le 1+\frac 12+\frac 13+\dots +\frac1{n-1}+\frac 1n\le\sum \frac 1m\textrm{-et}$$
kapunk, ahol az összegzést valamennyi $m\in\mathbb{N}$-re kiterjesztjük, melynek csak $p\le x$ osztója van.\marginpar{figure, center, includegraphics, scale, caption, label}
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{kep}
\caption{Lépcsős függvény az $f(t)=\frac 1t$ függvény grafikonja felett.}
\label{kep}
\end{center}
\end{figure}
Mivel minden ilyen $m$ egyértelműen írható fel $\prod _{p\le x}p^{k_p}$ alakban, látható, hogy az utóbbi összeg egyenlő
$$\prod _{p\in \mathbb{P}, p\le x}\left(\sum _{k\ge 0} \frac 1{p^k}\right)\textrm{-val.}$$
A belső összeg egy $\frac 1p$ kvóciensű mértani sor, azaz
$$\log x\le\prod _{p\in\mathbb{P}, p\le x} \frac 1{1-\frac 1p}=\prod \frac p{p-1}=\prod _{k=1}^{\pi (x)}\frac{p_k}{p_k-1}.$$
Nos, nyilvánvalóan $p_k\ge k+1$, így
$$\frac{p_k}{p_k-1}=1+\frac 1{p_{k-1}}\le 1+\frac 1k=\frac{k+1}k,$$
tehát
$$\log x\le\prod _{k=1}^{\pi(x)} \frac{k+1}{k}=\pi(x)+1.$$
Mint tudjuk $\log x$ nem korlátos, a fentiekből következik, hogy $\pi(x)$ sem korlátos, azaz végtelen sok prímszám van.


\section{Számok előállítása két négyzetszám összegeként}

\emph{Mely számok írhatók fel két négyzetszám összegeként?}
\marginpar{newtheorem, label}

\begin{lemma}\label{lemma1}
A $4m+1$ alakú prímekre az $s^2 \equiv -1 \pmod{p}$\marginpar{equiv, pmod} egyenletnek két megoldása van az $\{1,2,\dots p-1\}$ halmazon, $p=2$-re egy megoldás van, míg $4m+3$ alakú prímekre nincs megoldás.
\end{lemma}

\begin{lemma}
Az $n=4m+3$ alakú számok nem írhatók fel két négyzetszám összegeként.
\end{lemma}

\begin{allitas}
Minden $p=4m+1$ alakú prím előáll két négyzetszám összegeként, azaz felírható $p=x^2+y^2$ alakban, ahol $x$ és $y$ természetes számok.
\end{allitas}

\begin{proof}
A bizonyítás használja \aref{lemma1}. lemmát.\marginpar{aref}
\end{proof}

\begin{tetel}
Egy $n$ természetes szám akkor és csak akkor állítható elő két négyzetszám összegeként, ha prímtényezős felbontásában minden $p=4m+3$ alakú prím páros kitevőn szerepel.
\end{tetel}

\marginpar{align*, quad}
\begin{pelda}
\begin{align*}
1 &= 1^2+0^2 & 2 &= 1^2+1^2 & 3 &= ? & 4 &= 2^2+0^2 \\
5 &= 2^2+1^2 & 6 &= ? & 7 &= ? & 8 &= 2^2+2^2 \\
9 &= 3^2+0^2 & 10 &= 3^2+1^2 & 11 &= ?\quad \dots
\end{align*}
\end{pelda}

\subsection{Prímtestek}

Összeadás és szorzás $\mathbb{Z} _5$-ben:

\marginpar{array, hline}
$
\begin{array}{c|ccccc}
\mathrm{+} & 0 & 1 & 2 & 3 & 4\\ \hline
0 & 0 & 1 & 2 & 3 & 4 \\
1 & 1 & 2 & 3 & 4 & 0 \\
2 & 2 & 3 & 4 & 0 & 1 \\
3 & 3 & 4 & 0 & 1 & 2 \\
4 & 4 & 0 & 1 & 2 & 3
\end{array}
$
$\hspace{2cm}$
\marginpar{hspace, tabular, cdot}
\begin{tabular}{c|ccccc}
$\cdot$ & $0$ & $1$ & $2$ & $3$ & $4$\\ \hline
$0$ & $0$ & $0$ & $0$ & $0$ & $0$ \\
$1$ & $0$ & $1$ & $2$ & $3$ & $4$ \\
$2$ & $0$ & $2$ & $4$ & $1$ & $3$ \\
$3$ & $0$ & $3$ & $1$ & $4$ & $2$ \\
$4$ & $0$ & $4$ & $3$ & $2$ & $1$
\end{tabular}

\begin{thebibliography}{9}
\marginpar{thebibliography, bibitem}
\bibitem{bak} Martin Aigner, Günter M. Ziegler: \textit{Bizonyítások a Könyvből}, Typotex, Budapest, 2004.
\end{thebibliography}

\end{document}
