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

\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{graphics}
%\usepackage{fullpage}
%\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}

\begin{document}

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

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

\item \hf
Oldjuk meg az előző feladatot 1729-re.

\item 
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 \hf
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 \hf
Bizonyítsuk be, hogy egy álprímnek legalább három prímosztója van.

\end{enumerate}
\end{document}
