\documentclass[a4paper, 10pt]{article}
\usepackage[estonian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{t1enc}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\renewcommand{\P}{\mathbb{P}}

\topmargin-4em
\oddsidemargin0cm
\textwidth16cm
\textheight27cm
\evensidemargin-2cm

\begin{document}

\pagestyle{empty}

\Large

{\hfill{Kevad 2022} \smallskip %
\vspace{2em}



\begin{center}
{\LARGE Arvuteooria 10. praktikumi ülesanded:\\ 
\vspace{1em}
{\LARGE Algjuured I.}
}

\end{center}

\bigskip\bigskip


\smallskip

\noindent 1. Leida elementide $\overline {19}$, $\overline{29}$, $\overline{39}$, $\overline{40}$, $\overline{41}$ ja $\overline{42}$ j\"argud r\"uhmas $U(\Z_{49})$. Kas m\~oni arvudest $19$, $29$, $39$, $40$, $41$ või $42$ on algjuur mooduli $49$ j\"argi?

\bigskip

\noindent 2. Olgu meil 60-st m\"angukaardist koosnev MTG kaardipakk.
Nummerdame kaardid \"ulemi\-se\-st alumiseni numbritega $1,2,\ldots,60$. 
V\~otame pakist \"ulemise poole ja asetame lauale alumisest 
poolest paremale. Moodustame uue kaardi\-paki, v\~ottes j\"arjest 
ülemisi kaarte vasakpoolsest ja parempoolsest pakist. Sellisel 
viisil kaardipaki segamist illustreerib j\"argmine tabel:
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|}
\hline
koht vanas pakis & 1 & 2 & 3 & \ldots & 29 & 30 & 31 & 32 & 
33 & \ldots & 60 \\ \hline
koht uues pakis & 2 & 4 & 6 & \ldots & 58 & 60 & 1 & 3 & 
5 & \ldots & 59 \\ \hline
\end{tabular}.
\end{center}
Mitu korda peab pakki niimoodi segama, et kaardid oleksid 
j\"alle esialgses j\"arjekorras? 

\bigskip

\noindent 3. Näidata otse, {\bf kõiki} jäägiklassiringi $\mathbb{Z}_{21}$ elemente järjest astendades, et mooduli $21$ järgi ei leidu algjuuri. 

\bigskip

\noindent 4. Leida kõik algjuured moodulite $10$, $13$, $15$, $16$ ja $18$ järgi. 

\bigskip

\noindent 5. Olgu naturaalarv $n$ kujul $k^2+k+1$. Tõestada, et $n$ paaritud algtegurid on kas 3 või kujul $6l+1$. 

\bigskip

\noindent 6. Olgu $p>2$ algarv ja $a$ algjuur mooduli $p$ järgi. Tõestada, et täpselt üks arvudest $a,a+p, a+2p,\ldots,a+(p-1)p$ {\bf ei ole} algjuur mooduli $p^2$ järgi.

\bigskip

\noindent 7. Kasutades fakti, et algarvulise mooduli järgi leidub algjuuri, tõestada \\\emph{Wilsoni teoreem}:
$p\in\N$ on algarv siis ja ainult siis, kui 
$$
(p-1)!\equiv -1 \pmod{p}.
$$

\smallskip

\noindent 8. Olgu $m$ ja $n$ sellised naturaalarvud, et $m$ on paaritu ja $(m,2^n-1) = 1$. Tõestada, et $m\mid 1^n+2^n+\ldots+m^n$. 

\bigskip

\noindent 9${^*}$. Leida kõik naturaalarvud $n$, mille korral $\frac{2^n+1}{n^2}$ on täisarv. 

\bigskip

\noindent 10${^{**}}$. Olgu $p$ algarv ja olgu iga naturaalarvu $i$ korral $r_i$ jääk, mis tekib arvu $i^i$ jagamisel arvuga $p$. Tõestada, et jada $(r_i)$ on perioodiline ja leida selle perioodi minimaalne pikkus. 

\end{document}