\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}
\newcommand{\nehez}{\hskip -30pt ($*$) \hskip 13pt}

\pagestyle{empty}

\begin{document}

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

\begin{enumerate}

\item
Legyen $b\in\N^+$ tizes számrendszerbeli felírása 
$a_na_{n-1}\dots a_0$. Igazoljuk, hogy
\begin{enumerate}
\item $b\equiv a_0+a_1+\dots+a_n\pod3$;
\item $b\equiv a_0+a_1+\dots+a_n\pod9$;
\item $b\equiv a_0-a_1+a_2-a_3+\dots+(-1)^na_n\pod{11}$.
\end{enumerate}
Adjunk hasonló szabályt a 4-gyel és a 7-tel való osztási maradék 
kiszámítására.

\item Bizonyítsuk be, hogy ha $m\mid a-b$, akkor $m^2\mid a^m-b^m$.

\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^{17}}$-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\nehez
Legyen $f(x)\in\Z[x]$ egész együtthatós nem konstans polinom. 
Bizonyítsuk be, hogy $f(n)$ nem lehet minden $n$ természetes szám esetén prím.

\item\nehez
Mi a $4^{4^{4^4}}$ szám számjegyei összegének a számjegyeinek az 
összegének a számjegyeinek az összegének a számjegyeinek az összege?

\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}


\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}

