\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{\defi}{\medskip\hskip -25pt}
\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 2006/2007 ősz\\
12. gyakorlat: Négyzetösszeg probléma, számelméleti függvények}
\end{center}

\begin{enumerate}

\vskip 1.5 cm

\item
Tudjuk, hogy minden $4k+1$ alakú pozitív prím felírható két négyzetszám
összegeként. Adjunk erre a tényre új bizonyítást a végtelen leszállás 
módszerével.

\item\hf
Igazoljuk, hogy $n$ pozitív egész számra az alábbi két állítás ekvivalens.
\begin{enumerate}
\item $2n$ előáll három négyzetszám összegeként.
\item $n$ előáll négy négyzetszám összegeként, úgy, hogy az összeadandók 
között van (legalább) két azonos.
\end{enumerate}

\vskip 1cm

\defi
Jelölje $\sigma(n)$ az $n$ egész osztóinak összegét, $\delta$ az osztók száma, 
$\mu(n)$ pedig a Möbius-függvényt.

\item 
Legyen $f$ multiplikatív számelméleti függvény. Bizonyítsuk be, hogy minden 
pozitív egész $a$, $b$-re
\[
f(a)\cdot f(b)=f((a,b))\cdot f([a,b]),
\]
ahol $(a,b)$ a legnagyobb közös osztója, $[a,b]$ a legkisebb közös többszöröse
$a$ és $b$ számoknak.

\item\hf
Igazoljuk, hogy ha $2^{p}-1$ (Mersenne-)prím, akkor $n=2^{p-1}(2^p-1)$
tökéletes szám, azaz
\[
\sigma(n)=2n.
\]

\item
Bizonyítsuk be, hogy a $\sigma(n)$ függvény értékkészletéből végtelen sok
természetes szám kimarad.

\item 
Milyen értéket vesz fel
\[
g(n)=\sum_{k | 100!} \mu(kn)?
\]

\item Számoljuk ki a 
\begin{enumerate}
\item $\sum\limits_{d\mid n}\mu(d)\sigma\left(\frac nd\right)$,
\item $\sum\limits_{d\mid n}\mu\left(\frac nd\right)\delta(d)$
\end{enumerate}
összegeket.

\item 
Adjuk meg $g(n)$ megfordítási függvényét, ha
\begin{enumerate}
\item $g(n)=c$ valamely $c\in\C$ számra;
\item $g(n)=\frac{(-1)^n+1}2$;
\end{enumerate}

\item 
\begin{enumerate}
\item Igazoljuk, hogy a modulo $p$ primitív gyökök összege éppen
$\mu(p-1)$-gyel kongruens modulo $p$. (Útmutatás: Legyen $S(n)$ a pontosan 
$n$-edrendű elemek összege, $T(n)$ pedig azon $a$ elemek összege, amelyekre 
$a^n\equiv1\pod p$. Mutassuk meg, hogy $T(n)=0$, ha $n\neq1$ és használjuk 
a Möbius-inverziós formulát.)
\item\hfa 
Bizonyítsuk be, hogy az $n$-edik komplex primitív egységgyökök összege 
$\mu(n)$.
\end{enumerate}

\end{enumerate}
\end{document}
