\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{\ind}{\mathop{\mathrm{ind}}}
\newcommand{\legendre}[2]{\genfrac(){}{}{#1}{#2}}
\newcommand{\hf}{\hskip -25pt $\bullet$ \hskip 17pt}
\newcommand{\hfa}{\hskip -47pt $\bullet$ \hskip 39pt}
\newcommand{\nehez}{\hskip -30pt ($*$) \hskip 13pt}

\pagestyle{empty}

\begin{document}

\begin{center}
{\Large \bf Számelmélet 2009/2010 ősz\\
8. gyakorlat: Kvadratikus maradékok, Hensel-felemelés}
\end{center}

A feladatokban $p$ páratlan prím.

\begin{enumerate}

\item Számítsuk ki az alábbi Legendre-szimbólumok értékét.
\[
\legendre{37}{19},~~~~~~\legendre{-100}{19},~~~~~~\legendre{26123}{65537}
\]

\item Legyen $g$ primitív gyök modulo $p$. Számoljuk ki minden $k$-ra a 
$\legendre {g^k}p$ kvadratikus karaktereket.

\item Bizonyítsuk be, hogy ha $o_p(a)$ páratlan, akkor $a$ kvadratikus 
maradék modulo $p$. Mely prímekre igaz az állítás megfordítása?

\item Tegyük fel, hogy $\legendre a{97}=-1$ és $a$ nem primitív 
gyök modulo $97$. Számítsuk ki $o_{97}(a)$ értékét.

%\item Legyen $p-1=2^s\cdot t$, ahol $t$ páratlan. Igazoljuk, hogy 
%egy $p$-hez relatív prím $a$ pontosan akkor kvadratikus nem-maradék, ha
%$2^s\mid o_p(a)$.

\item \hf
Igazoljuk, hogy az alábbi állítások ekvivalensek.
\begin{enumerate}
\item[($i$)] $ab$, $ac$ és $bc$ is kvadratikus maradék.
\item[($ii$)] Vagy $a$, $b$ és $c$ is kvadratikus maradék, vagy mindhárom 
kvadratikus nem-maradék. 
\end{enumerate}

\item Mutassuk meg, hogy egy $8c^2-1$ alakú számnak minden prímosztója
$8k\pm1$ alakú és $c\neq0$ esetén van $8k-1$ alakú prímosztója.

\item \hf 
Mely $p$ prímekre van az $x^2+y^2\equiv0\pod p$ kongruenciának nemtriviális
megoldása. (Triviális megoldás az $x\equiv0\pod p$, $y\equiv0\pod p$; 
minden egyéb megoldás nemtriviális.)

\item
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(x_1)\equiv0 \pod{7}$, számojuk ki $f(x_1)\mod 7^2$
értékét.
% \emph{gyors hatványozás}sal. Ez a következőt jelenti: határozzuk meg a $x_1$, $x_1^2$, $x_1^4$, $x_1^8$, $x_1^{16}$ számokat modulo $7^2$ és használjuk ki, hogy $22=16+4+2$ miatt $x_1^{22}\equiv x_1^{16}x_1^4x_1^2\pod{7^2}$.
\item Az $f(x)\equiv0 \pod{7^2}$ megoldását $x_2=x_1+7y$ alakban keressük, így
\[
0\equiv f(x_2)=f(x_1+7y)\equiv f(x_1)+7yf'(x_1)\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 $x^9-x^8+x+3\equiv0\pod{100}$;
\item $x^{11}+x+1\equiv0\pod{363}$
\end{enumerate}
kongruenciák összes megoldását a Hensel-felemelés segítségével.



\end{enumerate}
\end{document}
