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

\begin{document}

\begin{center}
{\Large \bf Számelmélet 2005/2006 ősz\\
8. gyakorlat: Hensel-felemelés
}
\end{center}
\begin{enumerate}

\item
Mutassuk meg, hogy tetszőleges $p$ prím, $\alpha$ pozitív egész és $f(x)$ 
egész együtthatós polinom esetén 
\begin{enumerate}
\item $f(z+p^\alpha y)\equiv f(z)+p^\alpha yf'(z) \pod{p^{\alpha+1}}$;
\item ha $f(z)\equiv0\pod{p^\alpha}$ és $f'(z)\not\equiv0\pod p$, akkor 
$f(z+p^\alpha y)\equiv0\pod{p^{\alpha+1}}$ megoldható $y$-ra és 
a megoldás modulo $p$ egyértelmű.
\end{enumerate}

\item  (\emph{Hensel-felemelés})\\
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$
é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}$.
\item Az $f(x)\equiv0 \pod{7^2}$ megoldását $x=c+7y$ alakban keressük.
Az előző feladat szerint $0\equiv f(x)=f(c+7y)\equiv f(c)+7yf'(c)\pod{7^2}$.
\end{enumerate}

\item Keressük meg az 
\begin{enumerate}
\item $x^5-23\equiv0\pod{27}$;
\item $x^5-23\equiv0\pod{25}$;
\item $x^{18}+3x-4\equiv0\pod{49}$;
\item\hfa $x^{11}+x+1\equiv0\pod{363}$.
\end{enumerate}
kongruenciák összes megoldását a Hensel-felemelés segítségével.


\item\hf
Tegyük fel, hogy $p$ prím, $\alpha\ge2$ egész és $f(x)$ egész 
együtthatós polinom, amelyre $f(x_1)\equiv0\pod p$. Bizonyítsuk be,
hogy
\begin{enumerate}
\item amennyiben $f'(x_1)\not\equiv0\pod p$, akkor modulo $p^\alpha$ 
egyetlen olyan $x_{\alpha}$ van, amelyre $f(x_\alpha)\equiv0\pod{p^\alpha}$
és $x_\alpha\equiv x_1\pod p$;
\item amennyiben $f'(x_1)\equiv0\pod p$, akkor az előbbi egyenlet megoldásainak
száma osztható $p$-vel, azaz
\[
\left|\left\{
x_{\alpha}\in\Z\,:\,\, f(x_\alpha)\equiv0\pod{p^\alpha},\,\,\, 
x_\alpha\equiv x_1\pod p\,\,\, \text{ és } 0\le x_{\alpha}< p^{\alpha}
\right\}\right|
\]
osztható $p$-vel.
\end{enumerate}

\item\hf
Legyen $p$ prím és jelölje az $f(x)\equiv0\pod p$ kongruencia
(modulo $p$ páronként különböző) megoldásainak számát $r$. Lássuk be, hogy
\[
r\equiv-\sum_{a=1}^pf(a)^{p-1}\pod p.
\]


\end{enumerate}
\end{document}
