\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{\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\\
7. gyakorlat: Magasabb fokú kongruenciák, primitív gyök}
\end{center}

\begin{enumerate}

% g prim gyok iff o(g)=\varphi(m)
% g prim gyok iff 1, g, g^2, \dots, g^{\varphi(m)} red mar rsz.
% g prim gyok. g^k prim gyok iff (k,\varphi(m))=1

\item Igazoljuk, hogy amennyiben $g$ primitív gyök modulo $m$, akkor 
\begin{enumerate} 
\item $g^k$ primitív gyök $\iff$ $(k,\varphi(m))=1$ és
\item modulo $m$ pontosan $\varphi(\varphi(m))$ (páronként inkongruens)
primitív gyök van.
\end{enumerate}

\item Legyen $p$ prím, $k$ egész. Mivel kongruens 
\[
\sum_{a=1}^{p-1}a^k
\]
modulo $p$?

\item \hf
Legyen $p$ prím, $d\mid p-1$, $g$ primitív gyök modulo $p$ és $(a,p)=1$.
Mutassuk meg, hogy 
\[
o_p(a)=d \iff \exists t
\text{, amelyre $(t,d)=1$ és $j=\frac{t(p-1)}d$ esetén }a\equiv g^j\pod p
\]

\item \hf
Tegyük fel, hogy az $x^k\equiv1\pod p$ összes megoldása a $b_1$, $b_2$,
\dots, $b_r$ (modulo $p$ különböző) számok. Legyen $(a,p)=1$ és 
$x^k\equiv a\pod p$ egy megoldása $c$. Bizonyítsuk be, hogy ekkor 
$x^k\equiv a\pod p$ összes (modulo $p$ különböző) megoldása éppen $cb_1$, 
$cb_2$, \dots, $cb_r$.
 
\item Oldjuk meg a $3x^5\equiv2\pod{13}$ és a $3x^{10}\equiv4\pod{13}$ 
kongruenciákat!

\item 
Keressük meg az $x^3+2x-22\equiv0\pod{125}$ kongruencia egy megoldását!

\item \hf
Keressük meg az $5x^{22}\equiv6 \pod{7^2}$ kongruencia összes megoldását!
\begin{enumerate} 
\item Oldjuk meg először $f(x)=5x^{22}-6\equiv0 \pod{7}$-et. 
\item Ha $f(c)\equiv0 \pod{7}$, számojuk ki $f(c)\mod 7^2$ és
$f'(c)\mod 7^2$ értékét \emph{gyors hatványozás}sal. Ez a következőt jelenti:
határozzuk meg a $c$, $c^2$, $c^4$, $c^8$, $c^{16}$ számokat modulo 
$7^2$ és használjuk ki, hogy $22=16+4+2$ miatt 
$c^{22}\equiv c^{16}c^4c^2\pod{7^2}$, illetve $21=16+4+1$ miatt 
$c^{21}\equiv c^{16}c^4c\pod{7^2}$.
\item Az $f(x)\equiv0 \pod{7^2}$ megoldását $x=c+7y$ alakban keressük.
Tudjuk, hogy $0\equiv f(x)=f(c+7y)\equiv f(c)+7yf'(c)\pod{7^2}$, ami
$y$-ra nézve lineáris kongruencia, tehát meg tudjuk oldani.
\item Ne feledjük, hogy a fenti $f(x)$ esetén $f(x)\equiv0 \pod{7}$ minden 
egyes megoldásához pontosan egy megoldása tartozik az $f(x)\equiv0 \pod{7^2}$
kongruenciának!
\end{enumerate}

\end{enumerate}
\end{document}
