\documentclass[a4paper,12pt]{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 pótZH, megoldások\\}
{\bf 2005 december 16.}
\end{center}

%\vskip 1.5cm

\begin{enumerate}

\item Keressük meg az 
\[
5x\equiv561\pod{1968}
\]
kongruencia összes megoldását.

\mo
Először a kibővített euklideszi-algoritmussal számolva megadjuk 
$5$ és $1968$ legnagyobb közös osztójának előállítását $5$ és $1968$ 
lineáris kombinációjaként.
\[\begin{array}{rcl|ccc|}
         & &         & 1968\cdot x &+& 5\cdot y\\
1968 &=& 5\cdot393+3 & 1           & & 0\\
5    &=& 3\cdot1  +2 & 0           & & 1\\
3    &=& 2\cdot1  +1 & 1           & & -393\\
2    &=& 1\cdot2  +0 & -1          & & 394\\
1    & &             & 2           & & -787
\end{array}\]
Ezek szerint $2\cdot1968-787\cdot5=1$, tehát 
$5^{-1}\equiv-787\equiv1181\pod{1968}$. Miután 
$1181\cdot561=662541\equiv1293\pod{1968}$, tehát
$x\equiv1293\pod{1968}$ az egyetlen megoldás.

\item Adjuk meg az 
\[
x^{11}+x+1\equiv0\pod{121}
\]
összes megoldását.

\mo
Miután $121=11^2$, ezért oldjuk meg először modulo $11$. 
Ha $11\mid x$, akkor nem kapunk megoldást, 
tehát feltehető $(x,11)=1$, és így $x^{11}\equiv x\pod{11}$ a kis 
Fermat-tétel szerint. Megoldandó tehát a $2x+1\equiv0\pod{11}$ kongruencia,
aminek egyetlen megoldása $x\equiv5\pod{11}$.

Ezek után kereshetjük a modulo $11^2$ megoldást $5+11y$ alakban. Legyen
$f(x)=x^{11}+x+1$, így azt kapjuk, hogy
\begin{eqnarray*}
0 &\equiv& f(5+11y)\equiv f(5)+11yf'(5)\pod{11^2}\text{, azaz}\\
0 &\equiv& \frac{f(5)}{11}+yf'(5)\pod{11}.
\end{eqnarray*}
$5^3\equiv4\pod{11^2}$, így 
$5^{11}=\left(5^3\right)^3\cdot25\equiv64\cdot25\equiv27\pod{11^2}$,
tehát $f(5)\equiv33\pod{11^2}$. Másrészt 
$f'(x)=11x^{10}+1\equiv1\pod{11}$, így az egyenletünk
\[
0 \equiv 3+y\pod{11}.
\]
Innen $y\equiv8\pod{11}$, és ezért $x\equiv5+11\cdot8=93\pod{11^2}$.

A Hensel-felemelésről szóló tétel miatt más megoldása nincs a kongruenciának.


\item
Mutassuk meg, hogy tetszőleges $p$ prím és $n$ egész szám esetén 
$n^{p^p}-n$ osztható $p$-vel.

\mo
Miután $p^p\equiv1^p=1\pod{p-1}$, így 
$n^{p^p}\equiv n^1 = n\pod{p}$, ami igazolja az állítást.

\item
Bizonyítsuk be, hogy $2^n$ nem osztója $n!$-nak

\mo
Legyen $t=\lfloor\log_2n\rfloor$, azaz $2^t\leq n<2^{t+1}$.  A 2 kitevője 
$n!$ prímtényezős felbontásában 
\[
\sum_{i=1}^t\left\lfloor\frac n{2^i}\right\rfloor \leq
\sum_{i=1}^t\frac n{2^i} =
\frac n2\sum_{i=0}^{t-1}{2^{-i}} =
\frac n2\cdot\frac{2^{-t}-1}{2^{-1}-1} = 
n(1-2^{-t}) < n.
\]

\item
Bizonyítsuk be, hogy 4 semmilyen $m>1$-re nem lehet primitív gyök 
modulo $m$. Melyik az a legkisebb szám, amellyel $o_m(4)=4$?

\mo
Ha $(4,m)\neq1$, akkor természetesen nem lehet 4 primitív gyök.
Egyébként $4^{\frac{\varphi(m)}2} \equiv2^{\varphi(m)}\equiv1\pod m$
igaz az Euler--Fermat-tétel szerint, tehát $4$ rendje kisebb, mint
$\varphi(m)$, azaz nem lehet primitív gyök.

Az $o_m(4)$ akkor értelmes, ha 4 relatív prím $m$-hez, olyan $m$-et
keresünk tehát, amely páratlan. Ráadásul 
$4=o_m(2^2)=\frac{o_m(2)}{(o_m(2),2)}$ miatt $o_m(2)=8$ és ezért 
olyan $m$ jöhet csak szóba, amelyre $8$ osztója $\varphi(m)$-nek.
Az első ilyen a 15, de $o_{15}(4)=2$, a második a 17, ami viszont 
megfelelő.

\item
Legyen $p$ egy $4k+1$ alakú prím. Számítsuk ki az 
$\legendre1p+\legendre3p+\dots+\legendre{p-2}p$ összeget.

\mo
A $4k+1$ alakú prímekre $-1$ négyzetszám, tehát 
$\legendre ip = \legendre{-i}p = \legendre{p-i}p$.
Így $2\left(\legendre1p+\legendre3p+\dots+\legendre{p-2}p\right)=
\legendre1p+\legendre2p+\legendre3p+\dots+\legendre{p-1}p$.
Utóbbi összeg a négyzetelemek száma minusz a nem négyzetek 
száma, ez összesen 0, hiszen mindkettőből $\frac{p-1}2$ van.
\end{enumerate}
\end{document}
