\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}

\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{graphics}
%\usepackage{fullpage}\pagestyle{empty}
%\addtolength{\textheight}{2 cm}

\newcommand{\Q}{\mathbb Q}
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\legendre}[2]{\genfrac(){}{}{#1}{#2}}
\newcommand{\hf}{\hskip -25pt $\bullet$ \hskip 17pt}
\newcommand{\hfa}{\hskip -47pt $\bullet$ \hskip 39pt}
\newcommand{\defi}{\medskip\hskip -25pt}
\newcommand{\ind}{\mathop{\mathrm{ind}}}

\begin{document}

\begin{center}
{\Large \bf Számelmélet 2005/2006 ősz\\
13. gyakorlat: Prímtesztek
}
\end{center}

\defi
Legyen $n$ egész összetett és $(a,n)=1$. Ekkor $a$ szám $n$ 
összetettségének \emph{Fermat-tanú}ja, ha $a^{n-1}\not\equiv1\pod n$ és 
$a$ az $n$ \emph{Fermat-cinkos}a, ha $a^{n-1}\equiv1\pod n$.

\defi
Legyen $n$ páratlan összetett szám, $n-1=2^rs$, ahol $s$ páratlan
és $(a,n)=1$. Ekkor az $a$ az $n$ összetettségének
\emph{Rabin--Miller-tanú}ja, ha $a^s\not\equiv1\pod n$, továbbá
$a^{2^is}\not\equiv-1\pod n$ minden $0\le i< r$ esetén.
Egyébként $a$ \emph{Rabin--Miller-cinkos}.

\defi
Ha $n$ összetett számhoz nem létezik Fermat-tanú, akkor $n$ 
\emph{Carmichael-szám}, másnéven \emph{álprím}.

\defi
{\bf Tétel.} Minden páratlan összetett számhoz létezik Rabin--Miller-tanú.

\begin{enumerate}

\item 
Keressünk egy-egy Fermat-tanút 21 és 143 összetettségének bizonyítására.

\item
Igazoljuk, hogy 561 álprím (tehát a Fermat-teszten átmegy).
Mutassunk Rabin--Miller-tanút, amely viszont lebuktatja.
Oldjuk meg a feladatot 1729-re is.

\item
Mutassuk meg, a fenti tétel felhasználásával, hogy ha $n$ páratlan összetett
szám, akkor legalább annyi Rabin--Miller tanúja van, mint cinkosa.

\item 
Az előző feladat alapján hogyan lehet eldönteni legalább 99\%-os 
biztonsággal, hogy 1601 prím-e? És ha 90\%-os biztonsággal is 
beérjük? (Egyébként valóban prím.)

\item
Igazoljuk, hogy amennyiben $m$ páratlan szám összetettségének $a$ 
Fermat-tanúja, akkor $a$ egyben Rabin--Miller-tanú is.

\item 
Mutassuk meg, hogy az álprímek négyzetmentesek.

\item
Bizonyítsuk be, hogy egy álprímnek legalább három prímosztója van.


\end{enumerate}
\end{document}
