\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\\
3. gyakorlat}
\end{center}

\begin{enumerate}

\item Bizonyítsuk be, hogy $a$, $b$ és $c$ egészekre pontosan akkor teljesül,
hogy $c\mid ab$, ha léteznek $a_1$ és $b_1$ egészek, amelyekre $a_1\mid a$,
$b_1\mid b$ és $c=a_1b_1$. Mutassuk meg, hogy ha $(a,b)=1$ és $c\mid ab$, 
akkor egyértelmű $a_1$ és $b_1$. 

\item Egy természetes szám \emph{négyzetmentes}, ha nincs 1-től különböző 
négyzetszám az osztói között. Legyen $n$ négyzetmentes osztóinak száma
$A(n)$, a négyzetszám osztók száma $B(n)$, az összes osztók száma pedig $d(n)$.
Igazoljuk, hogy $A(n)B(n)\ge d(n)$. Mikor áll fenn egyenlőség?

\item \hf
Egy kegyetlen várúr börtönének 400 szűk cellájában egy-egy rab sínylődik. 
A cellák ajtaján levő zár úgy működik, hogy egy elfordítás esetén nyílik,
még egy elfordítás esetén ismét bezárul, stb. Jelenleg minden ajtó zárva van.
A várúr a születésnapján elhatározza, hogy nagylelkű lesz, és megparancsolja 
az egyik őrnek, hogy fordítson egyet valamennyi záron. Közben azonban 
meggondolja magát és utánaküld egy másik őrt, akit azzal bíz meg, hogy minden 
második záron fordítson egyet. Ezt követi a harmadik őr, aki minden harmadik 
záron változtat stb. Végül a négyszázadik őr a négyszázadik cella zárjának 
az állását módosítja. Azok a rabok szabadulnak ki, akiknek most nyitva áll
az ajtaja. Hány rabot bocsátott szabadon a várúr?

\item \hf Melyik az a legkisebb pozitív egész, amelynek pontosan
\begin{enumerate}
\item 31
\item 33
\item 32
\end{enumerate}
pozitív osztója van?

\item A $10^n$ osztói közül maximum hányat lehet kiválasztani úgy, hogy 
ezek közül semelyik se legyen osztója semelyik másik kiválasztottnak?

\item Mely pozitív egész $n$ számok rendelkeznek a
\[
\forall\,k\in\N^+\,\colon\,n\mid k^2\Rightarrow n\mid k
\]
tulajdonsággal?

\item (*) Tekintsünk 5000 különböző pozitív egész számot, amelyek közül 
bármely tíznek ugyanaz a legkisebb közös többszöröse. Maximálisan 
hány szám lehet közöttük, amelyek páronként relatív prímek?

\item \hf Igazoljuk, hogy ha $s$ és $t$ különböző természetes
számok, $a$ páros, akkor $(a^{2^s}+1,a^{2^t}+1)=1$.

\item (*) Mutassuk meg, hogy $a>1$, $n>0$ és $k>0$ egészekre
\[
(a^n-1,a^k-1)=a^{(n,k)}-1.
\]

\item (*) Igazoljuk, hogy minden pozitív egész számnak van olyan többszöröse,
amely a tízes számrendszeben csupa 1 és 0 jegyből áll.



\end{enumerate}
\end{document}
 