\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{\hf}{\hskip -25pt $\bullet$ \hskip 17pt}
\newcommand{\hfa}{\hskip -47pt $\bullet$ \hskip 39pt}

\begin{document}

\begin{center}
{\Large \bf Számelmélet 2004/2005 ősz\\
4. gyakorlat: Kongruenciák, Euler--Fermat-tétel}
\end{center}

\begin{enumerate}

%\item Határozzuk meg azt a legnagyobb $\alpha$ egész számot, amelyre 
%$3^\alpha\mid125!$.

\item Hány 0-ra végződik $1516!$ a tizes számrendszerben?

\item Legyen $m>1$ egész és tekintsük a következő állítást.\\
Ha $a,b\in\Z$-re $a^2\equiv b^2 \pod m$, akkor $a\equiv \pm b \pod m$.
\begin{enumerate}
\item Mutassuk meg, hogy amennyiben $m$ prím, vagy egy prímszám kétszerese,
de $m\neq4$, akkor igaz az állítás!
\item\hfa Adjunk ellenpéldát az állításra minden egyéb $m$ esetén!
\end{enumerate}

\item Mennyi $\varphi(8800)$?

\item \hf Hány különböző $n$ csúcsú csillagot lehet rajzolni a ceruza
felemelése nélkül?

\item Számítsuk ki $11^{23}\mod9$-et és $39^{7^5}\mod7$-et!

\item \hf Mi az utolsó két számjegye a $303^{404}$-nek? És az utolsó
két bináris jegye?

\item Mutassuk meg, hogy amennyiben $11\mid a^{30}+b^{30}+c^{30}$ valamely
$a,b,c\in\Z$ számokra, akkor fennáll $11^{30}\mid a^{30}+b^{30}+c^{30}$ is.

\item Relatív prím-e a $2^{100}-1$ és $3^{100}-1$?

\item (*) Adjunk a szita formula segítségével új bizonyítást a
\[
\varphi (n)=n\prod\limits_{j=1}^r\left(1-\frac1{p_i}\right)
\]
összefüggésre, ahol $p_1$, $p_2$, \dots, $p_r$ éppen $n$ különböző 
prímosztói.\\ 
(Útmutatás: Legyen $A_j=\left\{a\in\N^+:\,\,a\le n\text{, amelyre }
p_j\mid a\right\}$. Mennyi 
$\left\{1,2,\dots,n\right\}\setminus\left(\bigcup\limits_{j=1}^r A_j\right)$ 
elemszáma? Mit jelent, hogy $a\in\left\{1,2,\dots,n\right\}\setminus
\left(\bigcup\limits_{j=1}^r A_j\right)$?)

\end{enumerate}
\end{document}
 