\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 2006/2007 ősz\\
2. gyakorlat: Euklideszi algoritmus, szorzattá alakítás}
\end{center}

\begin{enumerate}

\item Határozzuk meg a $(693, 147)$ és a $(233, 377)$ legnagyobb közös
osztókat és adjuk meg a $693x+147y=(693, 147)$, illetve a 
$233x+377y=1$ egyenletek egy-egy $x$, $y$ egész megoldását.

\item \hf
Számoljuk ki a $132\,239$ és a $11\,819$ számok legnagyobb közös osztóját és 
adjuk meg a $132\,239x+11\,819y=(132\,239,11\,819)$ diofantikus egyenlet egy 
megoldását!

\item Igazoljuk, hogy adott $a$, $b$ és $c$ egészek mellett az $ax+by=c$ 
diofantikus egyenlet pontosan akkor megoldható $x$, $y$-ra, ha $(a,b)\mid c$.
Speciálisan tehát $a$ és $b$ pontosan akkor relatív prím, ha van olyan $x$ és
$y$, amire $ax+by=1$.

\item Mutassuk meg, hogy minden $k\ge1$ esetén $6k+5$ és $7k+6$
relatív prímek!

\item \hf
 Lássuk be, hogy a $\frac{k^3+2k}{k^4+3k^2+1}$ tört egyetlen $k$ egészre 
sem egyszerűsíthető.

\item \nehez
Bizonyítsuk, hogy az euklideszi algoritmus Fibonacci-számokra
a leglassabb, azaz ha $a\ge b$ legnagyobb közös osztóját keresve az 
algoritmus $n$ maradékos osztást végez, akkor $a\ge F_{n+1}$.
(Útmutatás: igazoljuk $j$-re vonatkozó indukcióval, hogy $0\le j\le n$ esetén
$a_{n-j}\ge F_{j+1}$, ahol az algoritmusban az \\
$a_0:=a$\\
$a_1:=b$\\
$a_0=a_1q_1+a_2$\\
$a_1=a_2q_2+a_3$\\
$a_2=a_3q_3+a_4$\\
$\dots$\\
$a_{n-1}=a_nq_n$\\
jelöléseket használjuk.)

\item Legyen $(a,b)=5$. Milyen értékeket vehet fel $(a+b,a-b)$ és 
milyeneket $(a+2b,4a-b)$?

\item Mely pozitív egész $n$ számokra prímszám
\begin{enumerate}
\item $n^3-n+3$,
\item $n^3-27$,
%\item $n$, $n+2$ és $n+4$ egyszerre
\item $n^8+n^7+n^6+n^5+n^4+n^3+n^2+n+1$?
\end{enumerate}

\item Legyenek $a$ és $k$ egynél nagyobb egészek. Igazoljuk, hogy
\begin{enumerate}
\item ha $a^k-1$ prím, akkor $a=2$ és $k$ prím;
\item ha $a^k+1$ prím, akkor $k$ kettőhatvány.
\end{enumerate}
A $2^p-1$ alakú prímek a Mersenne-prímek, a $2^{2^n}+1$ alakúak pedig
a Fermat-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 \nehez
Bizonyítsuk be, hogy ha veszünk 501 darab 1 és 1000 közötti egész 
számot,  akkor van közöttük olyan szám, ami osztható a választottak közül 
egy másikkal. Igaz-e ugyanez 500-ra is? 



\end{enumerate}
\end{document}
