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

\begin{document}

\begin{center}
{\Large \bf Számelmélet ZH megoldások\\}
{\bf 2005 december 1.}
\end{center}

\begin{enumerate}

\item 
Számoljuk ki a $11\,413$ és a $10\,403$ számok legnagyobb közös osztóját és 
adjuk meg a $11\,413x+10\,403y=(11\,413,10\,403)$ diofantikus egyenlet egy 
megoldását!

\mo
Euklideszi algoritmussal számolva kapjuk, hogy 
\[\begin{array}{rcl|ccc|}
	 & &			   & 11\,413\cdot x &+& 10\,403\cdot y\\
11\,413 &=& 10\,403\cdot1+1010     & 1		    & & 0\\
10\,403 &=& 1\,010\cdot10+303	   & 0		    & & 1\\
1\,010  &=& 303\cdot3+101	   & 1		    & & -1\\
303     &=& 101\cdot3		   & -10	    & & 11\\
101	& & 			   & 31		    & & -34
\end{array}\]
azaz a legnagyobb közös osztó $101$ és  
$11\,413\cdot31+10\,403\cdot(-34)=101$.


\item Keressük meg az 
\[
x^5+x^2+x+1\equiv0\pod{27}
\]
kongruencia összes megoldását!

\mo
Miután $27=3^3$, ezért oldjuk meg először modulo $3$. 
Az $x_1\equiv0\pod3$ nem megoldás, ezért $(x_1,3)=1$ minden 
megoldásra, tehát az $x_1^2\equiv1\pod3$ azonosságot kihasználva
$0\equiv x_1^5+x_1^2+x_1+1\equiv x_1+1+x_1+1\equiv 2x_1+2\pod3$, így 
$x_1\equiv2\pod3$.

Keressük $x^5+x^2+x+1\equiv0\pod{3^2}$ megoldását $x_2=x_1+3y$ alakban.
Legyen $f(x)=x^5+x^2+x+1$, így az egyenlet
\begin{eqnarray*}
0 &\equiv& f(2+3y)\equiv f(2)+3yf'(2)\pod{3^2}\text{, azaz}\\
0 &\equiv& \frac{f(2)}3+yf'(2)\pod{3}.
\end{eqnarray*}
Miután $f(2)\equiv3\pod{3^2}$ és $f'(2)\equiv1\pod3$, azt kaptuk, hogy 
$0\equiv1+y\pod3$, amiből $y\equiv2\pod3$, tehát 
$x_2\equiv2+3\cdot2=8\pod{3^2}$.

Végül $x^5+x^2+x+1\equiv0\pod{3^3}$ megoldásához legyen $x_3=x_2+3^2y$,
így $0\equiv f(8)+3^2yf'(8)\pod{3^3}$. Nyilván $f'(8)\equiv f'(2)\equiv1\pod3$,
továbbá $f(8)\equiv9\pod{3^3}$, tehát az egyenlet 
$0\equiv9+3^2y\pod{3^3}$, azaz $0\equiv1+y\pod3$. Ezek szerint ismét
$y\equiv2\pod3$, tehát $x_3\equiv8+3^2\cdot2=26\pod{3^3}$.
A Hensel-felemelésről szóló tétel szerint más megoldása nem lehet a
kongruenciának.

Lehettünk volna ügyesebbek is, látható ugyanis, hogy $-1$ gyöke $f(x)$-nek.
Miután kiszámoltuk, hogy modulo 3 egyetlen megoldás ($x_1\equiv2\pod3$) van, 
továbbá hogy $f'(x_1)\not\equiv0\pod3$, már tudjuk az előbb említett 
tételből, hogy modulo $3^n$ is egyetlen megoldás van, ami csak $-1$ lehet.


\item
Mennyi $13$ rendje modulo $49$?

\mo
Tudjuk, hogy $o_{49}(13)\mid\varphi(49)=42$, ezért $42=2\cdot3\cdot7$ 
osztóival kell csak próbálkoznunk. $13^2\equiv22\pod{49}$, 
$13^3\equiv-8\pod{49}$, $13^6\equiv15\pod{49}$, $13^7\equiv-1\pod{49}$.
Utóbbiból $13^{14}\equiv1\pod{49}$, tehát $o_{49}(13)=14$.


\item
Keressünk primitív gyököt modulo 50. Határozzuk meg az
\[
x^{26}\equiv31\pod{50}
\]
összes megoldását.

\mo
$\varphi(50)=20$, tehát olyan elemet keresünk, aminek 20 a rendje modulo 50.
A 3 jó is lesz: $3^2\equiv9\pod{50}$, $3^4\equiv31\pod{50}$,
$3^5\equiv-7\pod{50}$ és $3^{10}\equiv-1\pod{50}$. 

Ha $x=3^y$, akkor az egyenlet $3^{26y}\equiv3^4\pod{50}$, tehát
$26y\equiv4\pod{20}$, azaz $3y\equiv2\pod{10}$, $y\equiv4\pod{10}$.
Tehát $y\equiv4\pod{20}$ vagy $y\equiv14\pod{20}$, ezért 
$x\equiv3^4\equiv31\pod{50}$ vagy 
$x\equiv3^{14}=3^4\cdot3^{10}\equiv-31\pod{50}$.

\item
Adjuk meg azt a legkisebb $z$ pozitív egész számot, amelyre
\[
\sum_{a=1}^{17}(a^2-13)^{16}\equiv z\pod{17}.
\]

\mo
A kis Fermat-tétel szerint $(a^2-13)^{16}\equiv1\pod{17}$, ha 
$a^2-13\not\equiv0\pod{17}$. Miután 
\[
\legendre{13}{17}=\legendre{-4}{17}=
\legendre{-1}{17}\cdot \legendre{2}{17}^2=
(-1)^{\frac{17-1}2}=1,
\]
ezért 13 négyzetelem, amiből következik, hogy pontosan két olyan 
$a\in\{1,2,\dots,17\}$ szám van, amire $a^2\equiv13\pod{17}$.
Erre a két $a$-ra $(a^2-13)^{16}\equiv0\pod{17}$. Ezek szerint 
két nullát és 15 egyest adunk össze, azaz $z\equiv15\pod{17}$.


\item
Határozzuk meg az összes olyan $m\ge2$ egész számot, amely rendelkezik a 
következő tulajdonsággal:
\[
\text{ha $a\in\Z$, $a\not\equiv0\pod m$ akkor minden $n\in \N$ esetén 
$a^n\not\equiv0\pod m$.}
\]

\mo
A négyzetmentes számokra igaz a fenti tulajdonság. Ha ugyanis $m$ 
négyzetmentes, akkor $a\not\equiv0\pod m$-ből következik, hogy 
$m$ valamelyik $p$ prímosztója nem osztja $a$-t. Ekkor viszont 
$a$ semelyik hatványát nem osztja $p$, tehát $m$ sem.

Ha pedig $m$ nem négyzetmentes, mondjuk $p^2\mid m$, akkor például 
$a=\frac mp$ egész, amelyet nem oszt $m$, de 
$a^2=m\cdot\frac m{p^2}\equiv0\pod m$, hiszen $\frac m{p^2}$ egész szám.


\item
Mutassuk meg, hogy $(m_1,m_2)=d$ esetén az $x\equiv c_1\pod{m_1}$,
$x\equiv c_2\pod{m_2}$ kongruenciarendszer akkor és csak akkor oldható 
meg, ha $c_1\equiv c_2\pod d$.\\
(Segítség: ha $c_1\equiv c_2\pod d$, akkor mutassuk meg, hogy a
$dy\equiv d\pod{m_1}$, $dy\equiv0\pod{m_2}$ rendszer megoldható és 
$x=y(c_1-c_2)+c_2$ megoldása az eredeti kongruenciáknak.)

\mo
Tegyük fel, hogy a kongruenciarendszer megoldható, $x$ egy megoldás.
Ekkor $x\equiv c_i\pod{m_i}$ és $d\mid m_i$ miatt 
$x\equiv c_i\pod d$ is, tehát $c_1\equiv x \equiv c_2\pod d$, azaz
a feltétel szükséges.

Megfordítva, legyen $d\mid c_1-c_2$. Az útmutatás szerint eljárva 
tekintsük a $dy\equiv d\pod{m_1}$, $dy\equiv0\pod{m_2}$ kongruenciarendszert.
Mindkettőt leosztva $d$-vel, azt kapjuk, hogy
$y\equiv 1\pod{\frac{m_1}d}$, $y\equiv0\pod{\frac{m_2}d}$, ami megoldható 
a kínai maradéktétel szerint, hiszen $(\frac{m_1}d,\frac{m_2}d)=1$.
Legyen $x=y(c_1-c_2)+c_2 = yd\cdot \frac{c_1-c_2}d+c_2$. Miután 
$\frac{c_1-c_2}d$ egész szám a feltétel szerint, így 
$dy\equiv d\pod{m_1}$ miatt $x\equiv d\cdot \frac{c_1-c_2}d+c_2=c_1\pod{m_1}$
és $dy\equiv0\pod{m_2}$ miatt $x\equiv 0\cdot\frac{c_1-c_2}d+c_2=c_2\pod{m_2}$.
Ezzel beláttuk, hogy $x$ valóban megoldása a kongruenciarendszernek.

Az egyértelműségről a következő mondható:\\
Ha $x_1$ megoldás, akkor $x_2\in\Z$ pontosan akkor
megoldás, ha $x_1\equiv x_2\pod D$, ahol $D=[m_1,m_2]$.
Ha ugyanis $x_1$ és $x_2$ megoldások, akkor 
$x_1-x_2\equiv c_i-c_i=0\pod{m_i}$, amiből következik, hogy $x_1-x_2$ 
osztható $m_1$ és $m_2$ legkisebb közös többszörösével is.
Ha pedig $x_1$ megoldás és $x_2\equiv x_1\pod D$, akkor persze 
$x_2\equiv x_1\pod{m_i}$ is, amiből látszik, hogy $x_2$ is megoldás.


\end{enumerate}
\end{document}
