\documentclass[a4paper]{article}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
\sloppy
\pagestyle{empty}

\setlength\marginparsep{0cm}
\setlength\oddsidemargin{0cm}
\setlength\evensidemargin{0cm}
\setlength\topmargin{-1.5cm}
\addtolength\textwidth{5.8cm}
\addtolength\hoffset{-1.0cm}
\addtolength\textheight{4cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\newcounter{bak}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe II.}
\\\vspace*{1mm}
10. gyakorlat, 2005. április 22.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace*{10mm}
\textbf{\LARGE Számelmélet II.}
\end{center}

\vspace*{12mm}

\begin{enumerate}
\setcounter{enumi}{98}

\item Milyen maradékot ad a $2 \cdot 4 \cdot 6 \cdot \dots \cdot 200$
szorzat 101-gyel osztva?

\item Legyen $p$ prímszám. ${2p}\choose{p}$ $\equiv$ ? (mod $p$)

\item Legyen $m \geq 3$. Bizonyítsuk be, hogy $m$ akkor és csak akkor prím,
ha $(m-2)! \equiv 1$ (mod $m$).

%\item Bizonyítsuk be, hogy $n^{1998}+36n^{18}$ osztható 37-tel.

%\item Biz.\ be, hogy $2^{1998}-1$ osztható $(2^{37}-1)$-gyel.

\item Teljes maradékrendszer-e modulo 77 az \{ 1, 11, 21, \dots, 761 \}
számhalmaz?

\item Redukált maradékrendszer-e modulo 32 az \{ 5, 15, 25, \dots, 155 \}
számhalmaz?

\item Mivel kongruens mod 77 az $1998^{1979}$ szám?

\item Mi $7^{6^{5^{4^{3^2}}}}$ utolsó számjegye a 10-es számrendszerben?

\item Milyen maradékot ad 37-tel osztva az a szám, melynek 10-es
számrendszerbeli alakja 37 db egyesből áll?

\item Oldjuk meg: $15x \equiv 2$ (mod 5) és $7x \equiv 1$ (mod 13)

\item Oldjuk meg: $4x \equiv 2$ (mod 6) és $2x \equiv 1$ (mod 5)

\item Mennyi lehet az $a$, ha $a^{1997} \equiv 4$ (mod 81) ?

\item Legyen $n$ osztható $k$-val. Bizonyítsuk be, hogy $\varphi(n)$ is
osztható $\varphi(k)$-val.

\item Biz.\ be, hogy ha $n$ egész szám, $a$ és $b$ pedig nemnegatív
egész számok, és $n^{6a}+n^{6b}$ osztható 7-tel, akkor $n$ is osztható
7-tel.

%\item Keressük meg az alábbi két számtani sorozat legkisebb közös
%elemét: 30, 50, 70, \dots; illetve 12, 25, 38, \dots

\item Mi $1997^{7^{2000}}$ utolsó két számjegye?

\item Biz.\ 7 osztja $(5555^{2222}-2)$-t.

\item Kiszámítandó $(((43^{43})^{43})^{43})^{43}$ modulo 49.

\item Biz.\ be, hogy a $10^n+3$ alakú számok között végtelen sok
osztható 13-mal.

\item Legyen a $p$ prím esetén $a_1, a_2, \dots, a_{p-1}$ RMR (mod $p$).
Biz: $a_1^{p-2}, a_2^{p-2}, \dots, a_{p-1}^{p-2}$ szintén RMR (mod $p$).

\item Biz.\ minden $n$-re $\varphi(n^3)=n^2\varphi(n)$.

\item Milyen $n$-ekre teljesül, hogy $2\varphi(n)=n$?

\item Milyen $n$-ekre teljesül, hogy $\varphi(7n)=7\varphi(n)$?

\setcounter{bak}{\value{enumi}}

\end{enumerate}

\textbf{HF}

\begin{enumerate}

\setcounter{enumi}{\value{bak}}

\item Mennyi az $1993^{1993}$ szám 2004-gyel való osztáskor keletkező
maradéka?

\item Az Euler–Fermat-tétel szerint az $a$ és $m$ pozitív egészekre,
amennyiben azok relatív prímek, $a^{\varphi(m)} \equiv 1$ mod $m$. Keressünk
olyan $a$ és $m$ számokat, melyek nem relatív prímek, de szintén fennáll
rájuk a kongruencia.

\end{enumerate}

\end{document}
