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

\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\addtolength\textwidth{2cm}
\addtolength\hoffset{-1.5cm}
\addtolength\textheight{4.5cm}
\setlength\topmargin{-1.8cm}

\newcommand{\mod}{\textrm{mod}}

\newcounter{bak}

\begin{document}

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

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

\vspace*{12mm}

\begin{enumerate}
\setcounter{enumi}{80}

\item Az $x \equiv 2 (3)$ és az $x \equiv 5 (6)$ állítások közül melyik
következik a másikból? Ami nem következik, arra mutassunk ellenpéldát!

\item Melyek igazak az alábbi állítások közül?\\
\vspace*{-5mm}
\begin{enumerate}
\item $k\mid n,\; a\equiv b \; (\mod\; n) \Rightarrow a\equiv b \;
(\mod\; k)$ \item $k\mid n,\; a\equiv b \; (\mod\; k) \Rightarrow
a\equiv b \; (\mod\; n)$ \item $a\equiv b \; (\mod\; k),\;a\equiv
b \; (\mod\; n) \Leftrightarrow a\equiv b \; (\mod\; kn)$ \item
$a\equiv b \; (\mod\; k),\;a\equiv b \; (\mod\; n) \Leftrightarrow
a\equiv b \; (\mod\; [k,n])$ \item $a\equiv b \; (\mod\; n)
\Leftrightarrow ka\equiv kb \; (\mod\; kn)$ \item $a\equiv b \;
(\mod\; n),\;c\equiv d \; (\mod\; k) \Rightarrow ac\equiv bd \;
(\mod\; kn)$ \item $a^2\equiv b^2 \; (\mod\; n) \Leftrightarrow
a\equiv \pm b \; (\mod\; n)$ \item $a^2\equiv b^2 \; (\mod\; 101)
\Leftrightarrow a\equiv \pm b \; (\mod\; 101)$
\end{enumerate}

%\item Számítsuk ki az euklideszi algoritmus segítségével 504 és 372
%legnagyobb közös osztóját.

%\item Melyik a legkisebb olyan, 3-mal nem osztható szám, melynek 15
%osztója van?

%\item Ha $b$ osztója $a$-nak, mik a lehetséges értékei a $d(a,a+b)$ és a
%$d(2a,a-b)$ legnagyobb közös osztóknak?

\item Melyek azok a $p$ prímszámok, amelyekre $p+10$ és $p+14$ is
prím?

\item Mutassunk három olyan relatív prím számot, melyek közül semelyik kettő
nem relatív prím.

%\item Bizonyítsuk be, hogy ha $(a,4)=(b,4)=2$, akkor $a+b$ osztható
%$4$-gyel.

%\item Legyen $a$ és $b$ páratlan. Mennyi $(a^2+b^2,4)$?

%\item Van-e olyan $a,b$ pár, hogy $(a,b)=3$ és $a+b=100$? És olyan, hogy
%$(a,b)=5$ és $a+b=100$? Ahol igen, ott hányféle?

\item Bizonyítsuk be, hogy nem létezik olyan 3 jegyű szám, melynek osztóinak
száma osztható volna 11-gyel.

\item Bizonyítsuk be, hogy végtelen sok $n$-re teljesül, hogy
$d(n+1)\geq 2d(n)$.

\item Bizonyítsuk be, hogy minden $a,b$ egészre $d(ab)\leq d(a)d(b)$ és
egyenlőség pontosan akkor teljesül, ha $a$ és $b$ relatív prímek.

\item Bizonyítsuk be, hogy minden $a$ egészre $d(a)\leq 2\sqrt{a}$.

\item Két pozitív egész szám összege prím, az egyik a másik 30-szorosa. Mik
lehetnek ezek?

\item Bizonyítsuk be, hogy ha $2^n-1$ prím, akkor $n$ is prím.

%\item Bizonyítsuk be, hogy ha $2^n+1$ prím, akkor $n$ kettőhatvány.

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

%\item Maximum hány szám adható meg az $\{1,2,\dots,2n\}$ halmazból úgy,
%hogy egyik se legyen osztója semelyik másiknak?

%\item Maximum hány szám adható meg 1-től $2n$-ig úgy, hogy semelyik
%kettő ne legyen relatív prím?

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

\item Biz.\ tetszőleges $n$ természetes számra $n^5-5n^3+4n$ osztható
120-szal.

\item Oldjuk meg az $5x \equiv 8$ (mod 17) kongruenciát.

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

%\item Határozzuk meg 1998 olyan osztóinak a számát, melyek nem
%oszthatóak 9-cel.

\item Mely pozitív egész számoknak van ugyanannyi páros osztója, 
mint páratlan?

%\item Bizonyítsd be, hogy végtelen sok $4k-1$ alakú prímszám van!

\item Biz.\ tetszőleges $n$ természetes szám mellett $n(n^2+5)$ osztható
6-tal.

\item Legyen $n$ páratlan egész szám, amely nem osztható egyetlen
prímszám négyzetével sem. Bizonyítsuk be, hogy $n$ osztóinak
átlaga egész szám!

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

\item Igazoljuk, hogy ha az $a$ szám osztóinak a száma páratlan, akkor
minden $n>1$ egészre $a^n$ osztóinak a száma is páratlan.

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

%\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 $\phi(n)$ is
%osztható $\phi(k)$-val.

%\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 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 Legyenek $p_1$, $p_2$, \dots, $p_n$ különböző prímek. Hány osztója
%van az $m=p_1 \cdotp p_2 \cdotp \dots \cdotp p_n$ számnak?

%\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 Biz.\ ha egy prímszámot 30-cal osztunk, akkor maradékul vagy 1-et,
%vagy ismét egy prímszámot kapunk.

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

%\item Bontsuk fel 367-et két természetes szám összegére úgy, hogy az egyik
%osztható legyen 17-tel, a másik 21-gyel. Hányféleképpen lehetséges ez?

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

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

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

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

%\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$).

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

\end{enumerate}

\textbf{HF}

\begin{enumerate}

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

\item Oldjuk meg a kongruenciát: $170x \equiv 78$ (mod 2006).

\item Melyik az a legkisebb szám, melynek 10 osztója van? (Csak a pozitív
osztókat vesszük figyelembe.)

\end{enumerate}

\end{document}
