\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\\
1. gyakorlat: Euklideszi algoritmus, Fibonacci-számok}
\end{center}

\begin{enumerate}

\item Jelölje az $n$-edik Fibonacci-számot $F_n$, tehát $F_0=0$, $F_1=1$ 
és $n\ge2$-re $F_n=F_{n-1}+F_{n-2}$. Igazoljuk az alábbi összefüggéseket:
\begin{enumerate}
\item $\sum_{i=1}^nF_i=F_{n+2}-1$
\item $\sum_{i=1}^nF_{2i-1}=F_{2n}$
\item \hfa $\sum_{i=1}^nF_i^2=F_nF_{n+1}$
\end{enumerate}

\item Van-e, olyan hárommal osztható Fibonacci-szám, amelyre a kettővel 
rákövetkező is osztható 3-mal?

\item \hf
Bizonyítsuk be teljes indukcióval, hogy
\[
F_n=\frac1{\sqrt5}\left(\left(\frac{1+\sqrt5}2\right)^n-
\left(\frac{1-\sqrt5}2\right)^n\right)
\]

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


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

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

\end{enumerate}
\end{document}
