\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}

\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{graphics}
\usepackage{fullpage}
\pagestyle{empty}
%\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{\legendre}[2]{\genfrac(){}{}{#1}{#2}}
\newcommand{\hf}{\hskip -25pt $\bullet$ \hskip 17pt}
\newcommand{\hfa}{\hskip -47pt $\bullet$ \hskip 39pt}
\newcommand{\defi}{\medskip\hskip -25pt}

\begin{document}

\begin{center}
{\Large \bf Számelmélet 2005/2006 ősz\\
3. gyakorlat: Euklideszi algoritmus, kongruenciák bevezető
}
\end{center}

\begin{enumerate}

\item\hf
Határozzuk meg a $(693, 147)$ és a $(233, 377)$ legnagyobb közös
osztókat és adjuk meg a $693x+147y=(693, 147)$ egyenlet egy $x$, $y$ egész 
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$.

\defi 
$a,b,m\in\Z$-re $a$ kongruens $b$-vel modulo $m$, azaz $a\equiv b\pod m$,
ha $m\mid a-b$. Nyilván igaz, hogy 
\begin{enumerate}
\item $a\equiv a\pod m$ (reflexív),
\item ha $a\equiv b\pod m$, akkor $b\equiv a\pod m$ (szimmetrikus) és 
\item ha $a\equiv b\pod m$, $b\equiv c\pod m$, akkor  $a\equiv c\pod m$
(tranzitív),
\end{enumerate}
azaz $\equiv$ \emph{ekvivalenciareláció}.

\item
Bizonyítsuk be, hogy amennyiben $a\equiv a'\pod m$, $b\equiv b'\pod m$, akkor
\begin{enumerate}
\item $a+b\equiv a'+b'\pod m$,
\item $a\cdot b\equiv a'\cdot b'\pod m$,
\end{enumerate}
azaz $\equiv$ \emph{kompatibilis a szorzással és az összeadással}.
Mutassunk példát arra, hogy $r\equiv s\pod m$, de $a^r\not\equiv a^s\pod m$.

\item Lássuk be, hogy $a\equiv b\pod{m_i}$ minden $i=1,2,\dots,r$ esetén, 
akkor és csak akkor, ha $a\equiv b\pod{[m_1,\dots,m_r]}$.

\item\hf
Igazoljuk az alábbi, kongruenciákra vonatkozó összefüggéseket:
\begin{enumerate}
\item ha $a\equiv b\pod{cm}$, akkor $a\equiv b\pod m$;
\item $c\neq0$ egészre $a\equiv b\pod m$ akkor és csak akkor, ha 
$ac\equiv bc\pod{mc}$;
\item $c\neq0$ egészre $ac\equiv bc\pod m$ akkor és csak akkor, ha 
$a\equiv b\pod{\frac{m}{(m,c)}}$.
\end{enumerate}

\item\hf
Bizonyítsuk be, hogy tetszőleges $a,c,m$ egészek esetén az
$ax\equiv c\pod{m}$ kongruencia pontosan akkor oldható meg $x$-re,
ha $(a,m)\mid c$.

\item 
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.)

\end{enumerate}
\end{document}
