\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{\ind}{\mathop{\mathrm{ind}}}
\newcommand{\hf}{\hskip -25pt $\bullet$ \hskip 17pt}
\newcommand{\hfa}{\hskip -47pt $\bullet$ \hskip 39pt}
\newcommand{\moenu}{{\bf Megoldás:}}
\newcommand{\mo}{\moenu\\}
\newcommand{\moszam}[1]{{\bf #1. megoldás:\\}}

\begin{document}

\begin{center}
{\Large \bf Számelmélet 1.~ZH megoldások\\}
{\bf 2006 november 7.}
\end{center}

\begin{enumerate}
\item Adjuk meg a $66\,049x+32\,639y = 7\,967$ diofantikus egyenlet egy
egész megoldását.

\mo
Euklideszi algoritmussal számolva kapjuk, hogy 
\[\begin{array}{rcl|ccc|}
	 & &			   & 66\,049\cdot x &+& 32\,639\cdot y\\
66\,049 &=& 32\,639\cdot2+771      & 1		    & & 0\\
10\,403 &=& 771\cdot42+257	   & 0		    & & 1\\
771     &=& 257\cdot3+0	           & 1		    & & -2\\
257	& & 			   & -42	    & & 85
\end{array}\]
azaz a legnagyobb közös osztó $257$ és  
$66\,049\cdot(-42)+32\,639\cdot85 = 257$. Miután $\frac{7\,967}{257}=31$,
ezért az utóbbi egyenletet 31-gyel szorozva kapjuk a megoldást:
$x=-42\cdot31=-1302$ és $y=85\cdot31=2635$.


\item 
Melyik az a legkisebb pozitív egész $x$ szám, amelyre 
\[
x\equiv13^{11^{17}}\pod9
\]
teljesül.

\mo
Miután $\varphi(9)=6$ és $11^{17}\equiv(-1)^{17}=-1\pod6$, ezért 
$13^{11^{17}}\equiv 13^{-1}\equiv4^{-1}\pod9$, tehát 4 modulo 9 inverzét
kell kiszámolni: $4\cdot2=8\equiv-1\pod9$, azaz $4^{-1}\equiv-2\equiv7\pod9$,
$x=7$.


\item
Keressük meg a
\[
39x^{5}\equiv8\pod7
\]
és a 
\[
39x^{5}\equiv8\pod{19}
\]
kongruenciák összes megoldásait (külön-külön a kettőt).

\mo
Ha $39x^5\equiv 8 \pod7$, akkor $4x^5\equiv 1 \pod7$, így 
$x^5\equiv2 \pod7$. Mivel $3^2\equiv2\pod 7$, $3^3\equiv-1\pod7$, és 
$\varphi(7)=6$, ezért a 3 primitív gyök modulo 7. Ha bevezetjük 
az $y=\ind_3 x$ új változót, akkor az egyenletünk $3^{5y}\equiv3^2\pod7$, 
tehát $5y\equiv2\pod6$. Innen $y\equiv4\pod6$, $x\equiv3^4\equiv-3\pod7$.

Ha $39x^5\equiv8\pod{19}$, akkor $x^5\equiv 8 \pod{19}$. Mivel $2$
primitiv gyök modulo $19$ és $\ind_2 8=3$, tehát ha $x=2^y$, akkor
$5y\equiv 3 \pod{18}$. Ezt megoldva kapjuk, hogy $y\equiv15 \pod{18}$, azaz
$x\equiv2^y=2^{15}\equiv-2^6\equiv-7\pod{19}$.


\item
Adjuk meg a 
\[
39x^{5}\equiv8\pod{931}
\]
kongruencia összes megoldását! (Segítség: $931=7^2\cdot19$)

\mo
Tanultuk, hogy a megadott kongruencia megoldása ekvivalens 
a $39x^{5}\equiv8\pod{7^2}$, $39x^{5}\equiv8\pod{19}$ kongruenciarendszer
megoldásával. Ehhez a $39x^{5}\equiv8\pod7$ kongruencia előző feladatban 
kiszámolt megoldását fogjuk felemelni modulo $7^2$ megoldássá.

Legyen $f(x)=39x^5-8$. Ekkor $f'(x)=195x^4\equiv-x^4\pod7$, innen
$f(-3)\equiv 21\pod{49}$ és $f'(-3)\equiv3\pod7$.
Tehát az $x=-3+7y$ alakú megoldásokra felírhatjuk a
\[
0\equiv f(-3)+7y\cdot f'(-3) \pod{49}
\]
egyenletet. Héttel leosztva és $f(-3)$, $f'(-3)$-at behelyettesítve:
\[
0\equiv3+3y\pod7,
\]
tehát $y\equiv -1 \pod7$, azaz $x=-3-7=-10$ a keresett megoldás modulo 49.

Az eredeti $39x^{5}\equiv8\pod{931}$ egyenlet megoldásásait úgy kapjuk, 
hogy kínai maradéktétellel összerakjuk a modulo 49 és a modulo 19 megoldásokat.
Tehát meg kell oldanunk az
\begin{eqnarray*}
x&\equiv&-10\pod{49}\\
x&\equiv&-7\pod{19}
\end{eqnarray*}
rendszert. A megoldáshoz az euklideszi algoritmus segítségével 
kapjuk, hogy $49\cdot7+19\cdot(-18)=1$, tehát $19^{-1}\equiv-18\pod{49}$ 
és $49^{-1}\equiv7\pod{19}$. Innen 
$x\equiv49\cdot7\cdot(-7)+19\cdot(-18)\cdot(-10)\equiv88\pod{931}$.


\item
Egy $k$ számot köbmentesnek nevezünk, ha $m^3\mid k$-ból következik $m=\pm1$.
Mutassuk meg, hogy ha $n\in\N^+$, akkor $n$ 
egyértelműen bontható fel egy pozitív köbmentes szám és egy pozitív 
harmadik hatvány szorzatára. 
(Tehát létezik $k\in\N^+$ köbmentes és $m$ természetes
szám, hogy $n=k\cdot m^3$, továbbá $k$ és $m$ egyértelmű.)

\mo
Először is vegyük észre, hogy $k$ pontosan akkor köbmentes, ha minden 
$p\mid k$ prímszám legfeljebb második hatványon  szerepel kanonikus alakjában.

Legyen $n=\prod\limits_{i=1}^rp_i^{\alpha_i}$, ahol $p_i$ prímek 
különbözőek és legyen 
$\beta_i=\left\lfloor\frac{\alpha_i}3\right\rfloor$,  
$\gamma_i=\alpha_i-3\beta_i$. Ekkor 
$m=\prod\limits_{i=1}^rp_i^{\beta_i}$ és 
$k=\prod\limits_{i=1}^rp_i^{\gamma_i}$ a kívánt felbontást adja:\\
$k\cdot m^3=n$, mert minden $i$-re $\gamma_i+3\beta_i=\alpha_i$,\\
$k$ köbmentes, mert $\gamma_i<3$. 

Egyértelműség:\\
Tegyük fel, hogy $n=k\cdot m^3$. Megmutatjuk, hogy $k$ és $m$ csak a 
fent definiált lehet. Miután $m$ és $k$ is osztója $n$-nek, ezért $m$ 
és $k$ kanonikus alakjában ugyanazok a prímek fordulhatnak elő, mint 
$n$ felbontásában. Legyen tehát $n$, $k$ és $m$ kanonikus alakja 
$n=\prod\limits_{i=1}^rp_i^{\alpha_i}$, $k=\prod\limits_{i=1}^rp_i^{\gamma_i}$
és $m=\prod\limits_{i=1}^rp_i^{\beta_i}$, ahol természetesen $\beta_i=0$ és
$\gamma_i=0$ előfordulhat. Az $n=k\cdot m^3$ összefüggésből
$\gamma_i+3\beta_i=\alpha_i$ következik, abból pedig, hogy $k$ köbmentes,
azt látjuk, hogy $\gamma_i<3$. Ezt a két egyenlőséget
pontosan $\beta_i=\left\lfloor\frac{\alpha_i}3\right\rfloor$ és
$\gamma_i=\alpha_i-3\beta_i$ elégíti ki. 


\item
Legyen $p$ prím és $a$ egész, amelyre $o_p(a)=6$. 
\begin{enumerate}
\item Igazoljuk, hogy $a^2-a+1\equiv0\pod p$
\item Mutassuk meg, hogy $a-1$ modulo $p$ rendje 3.
\end{enumerate}

\moenu
\begin{enumerate}
\item Abból, hogy $1\equiv a^6\pod p$, következik
\[
0\equiv a^6-1=\left(a^3-1\right)\left(a^3+1\right)=
\left(a^3-1\right)\left(a+1\right)\left(a^2-a+1\right) \pod p.
\]
Miután $\Z_p$ nullosztómentes (prímtulajdonság), ezért az utóbbi
szorzat valamelyik tényezője 0 modulo $p$. Az $a^3-1\equiv0\pod p$
kongruencia azt jelentené, hogy $a$ rendje legfeljebb 3, 
$a+1\equiv0\pod p$-ből pedig $o_p(a)=o_p(-1)\le2$ következne.
Marad tehát, hogy $ a^2-a+1\equiv0\pod p$.
\item Nézzük meg, hogy mi $a-1$ harmadik hatványa. Alkalmazva az 
előbb igazolt összefüggést, $a^2$ lecserélhető $a-1$-re.
\[
(a-1)^3=a^3-3a^2+3a-1 \equiv a(a-1)-3(a-1)+3a-1 = a^2-a+2 \equiv 1 \pod p
\]
Ezek szerint $o_p(a-1)$ osztója 3-nak. Annyit kell látni, hogy a rend nem
egy, azaz $a-1\equiv1\pod p$ lehetetlen. Ha mégis így lenne, akkor
$a\equiv2\pod p$-ből következik $o_p(2)=6$ tehát $2^6\equiv1\pod p$, azaz
$p\mid2^6-1=63$, így $p=3$, vagy $p=7$. Viszont $o_3(2)=2$ és $o_7(2)=3$ 
miatt ezen prímekre sem 6 a 2 rendje.
\end{enumerate}


\item
Legyenek $p$ és $q$ különböző páratlan prímszámok.
\begin{enumerate}
\item Mutassuk meg, hogy ha $(a,pq)=1$, akkor az $x^2\equiv a\pod{pq}$ 
kongruenciának  vagy 0, vagy 4 modulo $pq$ különböző megoldása van.
\item Bizonyítsuk be, hogy a $pq$-hoz relatív prím, modulo $pq$ különböző 
négyzetelemek száma $\frac{\varphi(pq)}4$.
\end{enumerate}

\moenu
\begin{enumerate}
\item 
Tegyük fel, hogy $x^2\equiv a\pod{pq}$ kongruenciának van 
megoldása. Belátjuk, hogy ekkor pontosan 4 megoldás van. 

Ha $x^2\equiv a\pod{pq}$ megoldható, akkor $x^2\equiv a\pod p$ is az, 
tehát $a$ négyzetelem modulo $p$. Legyenek a négyzetgyökei $\pm b$.
Hasonlóan $x^2\equiv a\pod q$ megoldásai legyenek $\pm c$.
A kínai maradéktétel szerint az\\
(1) $y\equiv b\pod p$, $y\equiv c\pod q$\\
(2) $y\equiv b\pod p$, $y\equiv -c\pod q$\\
(3) $y\equiv -b\pod p$, $y\equiv c\pod q$\\
(4) $y\equiv -b\pod p$, $y\equiv -c\pod q$\\
kongruenciarendszereknek egy-egy megoldása van modulo $pq$, amelyek
mind kielégítik az $x^2\equiv a\pod{pq}$ egyenletet, hiszen mind a négy
esetben $y^2\equiv b^2\equiv a\pod p$ és $y^2\equiv c^2\equiv a\pod q$,
tehát $y^2\equiv a\pod{pq}$. Négy különböző megoldást
tudtunk mutatni. 

Azt kell még látni, hogy több megoldás nincs.
Ha egy $d$ az eredeti egyenlet egy tetszőleges megoldása, akkor 
$d$ megoldása az $x^2\equiv a\pod p$ és $x^2\equiv a\pod q$
kongruenciáknak is. Tanultuk, hogy modulo egy prímszám legfeljebb két
négyzetgyöke van $a$-nak , tehát $d\equiv\pm b\pod p$ és $d\equiv\pm c\pod q$,
ami azt jelenti, hogy $d$ a fenti négy egyenletrendszer egyikének megoldása.

\item 
Legyen $\{b_1,\dots,b_{\varphi(pq)}\}$ redukált maradékrendszer modulo $pq$.
Ekkor az összes négyzetelemek halmaza nyilván 
$\{b_1^2,\dots,b_{\varphi(pq)}^2\}$. Utóbbiak között minden négyzetelem 
pontosan 4-szer szerepel, hiszen egy a feladat előző része szerint egy
négyzetelemnek pontosan négy négyzetgyöke van modulo $pq$. Ez azt jelenti,
hogy a négyzetelemek száma épp $\frac{\varphi(pq)}4$.
\end{enumerate}












\end{enumerate}
\end{document}
