\documentclass[a4paper,12pt,pdftex]{article}
\title{Számelmélet tételsor}
\author{Bácsi László \\ lackac@math.bme.hu}

%-- Magyar formázások és ékezetkezelés ----------------------------------------%
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
%------------------------------------------------------------------------------%


%-- Fejléc, tartalomjegyzék, bibliográfia -------------------------------------%
\usepackage{fancyhdr}			%% oldalfejlécek
%\usepackage[square]{natbib}		%% natbib stílus bibliográfiához
%\usepackage[nottoc]{tocnatbibind}	%% make entry of LoF, LoT, and ...
					%% Ref in ToC but still use natbib-style
%\settocbibname{Bibliográfia}		%% Bibliográfia címe 
%------------------------------------------------------------------------------%


%-- AMS csomagok (matematikai szimbólumok, tételforma definiálás, ...) --------%
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}			%% tételformázás
%------------------------------------------------------------------------------%


%-- PDF-hez beállítások (lapképek, hyperlinkek, pdfinfo, szép fontok) ---------%
\usepackage{color}			%% színdefiniálás
\usepackage{thumbpdf}			%% pdf-be oldalképek
\usepackage[pdftex,			%% hyperlinkek pdflatex-hez
  bookmarks=true,			%% bookmarks generálás számokkal ...
  bookmarksnumbered=true,		%% szükséges a képek korrekt ...
%  hypertexnames=false,			%% linkezéséhez
  breaklinks=true,			%% megtöri a linkeket is ha hosszúak
  colorlinks=true,			%% színezi a linkeket
  linkcolor=linkcol]{hyperref}		%% a linkek színe (lent definiálva)
\definecolor{linkcol}{rgb}{0,0.25,0.5}  %% a fönt használt szín definiálása
\hypersetup{				%% pdf-hez információk megadása
pdfauthor   = {Bácsi László <lackac@math.bme.hu>},
pdftitle    = {Számelmélet tételsor},
%pdfsubject  = {},
%pdfkeywords = {},
}
\usepackage{pslatex}			%% ezzel a csomaggal szép fontok ...
					%% lesznek pdf-ben is
\pdfadjustspacing=1			%% LaTeX-típusú karaktertávolság
%------------------------------------------------------------------------------%


%------------------------------------------------------------------------------%
\setcounter{secnumdepth}{2}		%% a fejezetek és tartalomjegyzék ...
\setcounter{tocdepth}{2}		%% számozásának mélysége
%------------------------------------------------------------------------------%


%-- Fejléc beéllítása - még nem tudom, hogy pontosan hogy működik .. másoltam -%
\pagestyle{fancy}
\fancyhf{}
\fancyhead[EL,OR]{\bfseries\thepage}
\fancyhead[LO]{\bfseries\rightmark}
\fancyhead[RE]{\bfseries\leftmark}
%
\fancypagestyle{plain}{
  \fancyhead{}
  \fancyhead[EL,OR]{\bfseries\thepage}
  \renewcommand{\headrulewidth}{0pt}
}
%------------------------------------------------------------------------------%


%-- Új tételstílus, és tételforma definíciók ----------------------------------%
\newtheoremstyle{mythm}
  {6pt}					%% helyköz fölötte 
  {6pt}					%% helyköz alatta
  {\normalfont}				%% tételszöveg betűtípus
  {}					%% behúzás mértéke ({\parindent} v. {})
  {\scshape}				%% tételcím betűtípus
  {.}					%% pontozás a cím után
  {\newline}				%% helykihagyás a cím után
  					%% (" " v. \newline)
  {}					%% Thm head spec (még nem jöttem rá...)
				
\theoremstyle{mythm}
\newtheorem{dfn}{Definíció}[subsection]
\newtheorem{tet}[dfn]{Tétel}
\newtheorem{lem}[dfn]{Lemma}
\newtheorem{all}[dfn]{Állítás}
\newtheorem{pld}[dfn]{Példa}
%------------------------------------------------------------------------------%

%-- Saját makrók és operátorok definiálása ------------------------------------%
\newcommand{\sor}[2]{#1_1,\ldots,#1_{#2}}
\newcommand{\szsor}[2]{#1_1\cdot\ldots\cdot#1_{#2}}
\newcommand{\pol}[3]{#1_{#3}#2^{#3}+#1_{#3-1}#2^{#3-1}+\ldots+#1_1#2+#1_0}
\newcommand{\kan}[3]{#1_1^{#2_1}\cdot\ldots\cdot#1_{#3}^{#2_{#3}}}

\DeclareMathOperator*{\lnko}{lnko}
\DeclareMathOperator*{\ord}{ord}
\DeclareMathOperator*{\ind}{ind}
\newcommand{\pr}{\ \textrm{prím}\ }

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\ds}{\displaystyle}
%------------------------------------------------------------------------------%


\begin{document}

%-- Címlap --------------------------------------------------------------------%
\pagenumbering{roman}			%% római oldalszámozás
\pdfbookmark[1]{Címlap}{titpage}	%% bejegyzés a tartalomjegyzékbe
\maketitle
\clearpage
%------------------------------------------------------------------------------%

%-- Tartalomjegyzék -----------------------------------------------------------%
\pdfbookmark[1]{Tartalomjegyzék}{toc}	%% bejegyzés a tartalomjegyzékbe
\thispagestyle{plain}			%% innentől a fent definiált fejléc
\tableofcontents
\markboth{Table of Contents}{Table of Contents} %%% for the page header
\clearpage
\pagenumbering{arabic}			%% arab oldalszámozás
%------------------------------------------------------------------------------%


%-- Innen jön a dokumentum ----------------------------------------------------%
\section{Elemi számelmélet}

\subsection{Oszthatósag}
\begin{dfn}
$a,b\in\Z$,\\
$a$ \emph{osztója} $b$-nek, ha $\exists q\in\Z : b=qa$.
\end{dfn}

\begin{tet}
Az oszthatóság $\N$-en \emph{részbenrendezés}
\end{tet}

\begin{tet}
$a,b,c,m,n\in\Z:\ c\mid a, c\mid b \Rightarrow c\mid (am+bn)$ \\
Általanosítva: $a_i,m_i,c\in\Z:\ c\mid a_i, 1\leq i\leq k 
\Rightarrow c\mid \ds\sum_{i=1}^k a_im_i$
\end{tet}

\begin{tet}
$a\mid b, b\ne0:\ a,b\in\Z \Rightarrow 
0<\left|a\right|\leq\left|b\right|$
\end{tet}

\begin{tet}
$n\ne0, a\mid b \Leftrightarrow na\mid nb$
\end{tet}

\subsection{Maradékos osztás}
\begin{tet}[maradékos osztás]
$a,b\in\N^+, b\ne 0:\ \exists! q,r\in\N:
\ a=bq+r$ és $0\leq r<b$\\
Általánosítva: $a,b\in\Z, b\ne 0:\ \exists!
q,r\in\Z:\ a=bq+r$ és $0\leq r<b$ \\
Megjegyzés: $a=bq+r$-nél: $q=\left\{ \begin{array}{ll}
\left\lfloor\frac{a}{b}\right\rfloor & \textrm{ha $b>0$} \\
\left\lceil\frac{a}{b}\right\rceil & \textrm{ha $b<0$}
\end{array} \right.$ 
\end{tet}

\begin{tet}
$t>1,t,n\in\Z^+$,\quad$\exists! \sor{a}{m}\in\Z$,
\quad$a_m\ne 0, 0\leq a_i<t$,\quad$(1\leq i\leq m)$\\
\[ n=\pol{a}{t}{m} \]
\end{tet}

\subsection{\emph{L}eg\emph{N}agyobb \emph{K}özös \emph{O}sztó}
\begin{dfn}
Legyen $a,b\in\Z$, nem mindkettö $0$, a és b 
\emph{legnagyobb közös osztója} $c$, ha $c>0$, közös osztó, 
és $\forall d$ közös osztóra $d\leq c$\\
Jelölés: $(a,b), \gcd(a,b), \lnko(a,b)$
\end{dfn}

\begin{dfn}
$a,b\in\Z$ \emph{relatív prímek}, ha $(a,b)=1$\\
Általánosítva: $\sor{a}{n}$ relatív prímek, ha $(\sor{a}{n})=1$\\
\emph{páronként} relatív prímek, ha $\forall i<j :
(a_i,a_j)=1$\quad$(1\leq i,j\leq n)$
\end{dfn}

\begin{tet}
$d=(a,b) \Rightarrow\exists m,n\in\Z : d=am+bn$
\end{tet}

\begin{tet}
$d\in\N^+, a,b,\in\Z$ nem mindkettö $0$. Az alábbi
állítasok ekvivalensek:\\
\begin{enumerate}
\item $d=(a,b)$
\item $d=\min \left\{ax+by : x,y\in\Z, ax+by>0\right\}$
\item $d$ közös osztó és $\forall c$ közös osztóra $c\mid d$
\end{enumerate}
\end{tet}

\begin{tet}[LNKO tulajdonságai]
\begin{enumerate}
\item $\forall c\in\N^+ : (ca,cb)=c(a,b)$
\item $(a,c)=(b,c)=1 \Rightarrow (ab,c)=1$
\item $a,b,c\in\Z : (a,b)=(b,a)=(a,-b)=(a,b+ac)$
\item $c\mid ab, (a,c)=1 \Rightarrow c\mid b$
\end{enumerate}
\end{tet}

\begin{tet}
$a,b\in\N^+$
\[ {\setlength{\arraycolsep}{.13889em}
\begin{array}{rcll}
a	& =	& bq_1 + r_1		& \quad 0<r_1<b \\
b	& =	& r_1q_2 + r_2		& \quad 0<r_2<r_1 \\
r_1	& =	& r_2q_3 + r_3		& \quad 0<r_3<r_2 \\
\vdots	&	& \vdots		& \quad \vdots \\
r_{k-2}	& =	& r_{k-1}q_k + r_k	& \quad 0<r_k<r_{k-1} \\
r_{k-1}	& =	& r_kq_{k+1}		& \\
\end{array}} \]
A fenti egyenletek sorozata véges és $r_k=(a,b)$
\end{tet}

\subsection{Lineáris diofantoszi egyenletek}
\begin{tet}
Az $ax+by=m$ egyenlet
\begin{enumerate}
\item megoldható $\Leftrightarrow (a,b)\mid m$
\item ha $x_0, y_0$ jó megoldás $\Rightarrow$ az összes megoldás:
\[ x=x_0+\frac{b}{(a,b)}k,\quad y=y_0-\frac{a}{(a,b)}k \]
\end{enumerate}
\end{tet}

\begin{tet}
$a,b>0, ax+by=m$ pozitív megoldásainak száma egyenlő azon $k$
értékek számával, melyekre $-(a,b)\frac{x_0}{b}<k<(a,b)\frac{y_0}{a}$
\end{tet}

\subsection{Prímszámok}
\begin{dfn}
A $p>1$ egészt \emph{felbonthatatlannak} (\emph{irreducibilisnek})
nevezzük, ha\\
$p=ab \Rightarrow a$ vagy $b$ egység.\\
Megjegyzés: ezzel ekvivalens: $p>1$ felbonthatatlan, ha $1$-en és
önmagán kívül nincs pozitív osztója.
\end{dfn}

\begin{dfn}
A $p>1$ egész \emph{prím}, ha $p\mid ab \Rightarrow p\mid a$ vagy $p\mid b$.
\end{dfn}

\begin{tet}
$p\in\N \pr \Leftrightarrow p$ felbonthatatlan.
\end{tet}

\begin{lem}
$n>1 \Rightarrow$ van felbonthatatlan osztója.
\end{lem}

\begin{tet}[Számelmélet alaptétele]
$\forall n>1$ egész egyértelműen előáll prímek nem csökkenő
sorozatának szorzataként.
\end{tet}

\begin{dfn}
$n>1$, $n$ \emph{kanonikus alakja}:\\
$n=\kan{p}{\alpha}{r}$, ahol $\alpha_i>0\ (i=1,\dots,r)\ (p_1<p_2<\dots<p_r)$
\end{dfn}

\begin{tet}[kanonikus alakról]
\begin{enumerate}
\item $a=\kan{p}{\alpha}{r}$-nek $d$ osztója $\Leftrightarrow
d=\kan{p}{\beta}{r}$\quad$0\leq\beta_i\leq\alpha_i$
\item $a$ osztóinak száma:
$\delta(a)=(\alpha_1+1)(\alpha_2+1)\cdot\ldots\cdot(\alpha_r+1)$
\item $a=\kan{p}{\alpha}{r}$ $(\alpha_i\geq0)$, $b=\kan{p}{\beta}{r}$
$(\beta_i\geq0)$\\
\[ (a,b)=\prod_{i=1}^{r}p_i^{\min(\alpha_i,\beta_i)}
\qquad\left[a,b\right]=\prod_{i=1}^{r}p_i^{\max(\alpha_i,\beta_i)} \]
\end{enumerate}
\end{tet}

\begin{tet}[$n!$ kanonikus alakja]
\begin{enumerate}
\item $p\pr e=\ds\sum_{k=1}^{\infty}
\left\lfloor\frac{n}{p^k}\right\rfloor \Rightarrow 
p^e\parallel n!$\quad($p^e\mid n!$, de $p^{e+1}\nmid n!$)
\item $n!=\ds\prod_{p\leq n}p^{e_p}$, ahol
$e_p=\ds\sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^k}\right\rfloor$
\end{enumerate}
\end{tet}

\begin{dfn}
$a,b\in\Z$ \emph{legkisebb közös többszöröse} az a legkisebb
$c\geq0, c\in\Z$, melyre $a\mid c, b\mid c$\\
Jelölés: $\left[a,b\right]=c$
\end{dfn}

\begin{tet}[LKKT tulajdonságai]
\begin{enumerate}
\item $\left[0,0\right]=0,\ \left[a,0\right]=0,\ 
\left[a,a\right]=\left|a\right|$
\item $a\mid b \Rightarrow \left[a,b\right]=\left|b\right|$
\item $\left[a,b\right]=n\in\N$:
  \begin{itemize}
  \item $a\mid n, b\mid n$
  \item $a\mid m, b\mid m \Rightarrow n\mid m$
  \end{itemize}
\item $\left[a,b\right](a,b)=\left|a,b\right|$
\end{enumerate}
\end{tet}

\begin{tet}[Lame]
A legnagyobb közös osztó megtalálásában az euklidészi
algoritmusban szükséges lépések száma $\leq 5\cdot$ a kisebbik szám
számjegyeinek a száma.
\end{tet}


\section{Kongruenciák}

\begin{dfn}
Ha $a\in\Z$ és $m\in\Z\backslash\left\{0\right\}$, akkor
$a$-nak $m$-mel vett (legkisebb nemnegatív) osztási maradékát $a\bmod
m$ jelöli.
\end{dfn}

\begin{dfn}
$x,y\in\R,\ y\ne0\quad x\bmod
y:=x-\left|y\right|\left\lfloor\frac{x}{\left|y\right|}\right\rfloor$
\end{dfn}

\begin{dfn}
$m\ne0,\ m\in\Z$ Azt mondjuk, hogy
\emph{$a$ kongruens $b$-vel modulo $m$}, ha $a\bmod m=b\bmod m$\\
Jelölés: $a\equiv b\pmod m,\ a\equiv b\ (m)$
\end{dfn}

\subsection{Kongruenciák tulajdonságai}
\begin{tet}
\begin{enumerate}
\item $a\equiv b\pmod m \Leftrightarrow a\equiv b\pmod {-m}$
\item $\forall a,b\in\Z:\ a\equiv b\pmod 1$
\item $a\equiv b\pmod m,\ b\equiv a\pmod m,\ a-b\equiv 0\pmod m,\ m\mid b-a$
ekvivalensek
\item $a\equiv b\pmod m,\ b\equiv c\pmod m \Rightarrow a\equiv c\pmod m$
\item[$\Rightarrow$] a "$\equiv$" $\pmod m$ \emph{ekvivalenciareláció} 
(reflexív, szimmetrikus, tranzitív)
\item $a\equiv b\pmod m \Leftrightarrow a\equiv b+mq\pmod m\ (q\in\Z)$
\item $a\equiv b\pmod m,\ c\equiv d\pmod m \Rightarrow$
  \begin{itemize}
  \item $a\pm c\equiv b\pm d\pmod m$
  \item $ac\equiv bd\pmod m$
  \end{itemize}
\item[$\Rightarrow$] $a\equiv b\pmod m \Rightarrow$
  \begin{itemize}
  \item $a+c\equiv b+c\pmod m$
  \item $ac\equiv bc\pmod m$
  \item $a^n\equiv b^n\pmod m\ (n\in\N^+)$
  \end{itemize}
\item[$\Rightarrow$] $f$ tetszőleges egész együtthatós polinom
$(f\in\Z\left[x\right])$, és $a\equiv b\pmod m$ \\
$\Rightarrow f(a)\equiv f(b)\pmod m$
\end{enumerate}
\end{tet}

\begin{tet}[kongruenciák kapcsolata]
\begin{enumerate}
\item $a\equiv b\pmod m,\ d\mid m \Rightarrow a\equiv b\pmod d$
\item $a\equiv b\pmod m,\ c\ne0 \Rightarrow ac\equiv bc\pmod {mc}$
\item $ax\equiv bx\pmod m \Leftrightarrow a\equiv b\pmod {\frac{m}{(x,m)}}$
\item $ax\equiv bx\pmod m,\ (x,m)=1 \Rightarrow a\equiv b\pmod m$
\item $a\equiv b\pmod {m_i},\ i=1,2,\dots,r \Leftrightarrow a\equiv b 
\pmod {\left[\sor{m}{r}\right]}$
\end{enumerate}
\end{tet}

\subsection{Maradékosztályok, maradékrendszerek}
\begin{dfn}
Az $a$-val kongruens $\pmod m$ számok halmazát az $a$ által
reprezentált \emph{maradékosztálynak} nevezzük.\\
Jelölés: $\left[a\right]_m,\ \left[a\right]\pmod m,\ (a)_m,\ (a)\pmod m,\
\left[a\right],\ (a),\ a$
\end{dfn}

\begin{dfn}
modulo $m$ \emph{teljes maradékrendszer} $m$ szám halmaza, melyben minden
maradékosztályból van reprezentáns.
\end{dfn}

\begin{lem}
$a\equiv b\pmod m \Rightarrow (a,m)=(b,m)$
\end{lem}

\begin{dfn}
modulo $m$ \emph{redukált maradékrendszer} $m$-hez relatív prím,
$\pmod m$ inkongruens egészek olyan halmaza, mely $\varphi(m)$ elemű.
\end{dfn}

\begin{all}
\begin{enumerate}
\item $T\subseteq\Z$ tmrsz. $\pmod m \Leftrightarrow$
  \begin{itemize}
  \item $\left|T\right|=m$
  \item $r_i,r_j\in T:\ r_i\not\equiv r_j\pmod m$
  \end{itemize}
\item $R\subseteq\Z$ rmrsz. $\pmod m \Leftrightarrow$
  \begin{itemize}
  \item $\left|R\right|=\varphi(m)$
  \item $r_i,r_j\in R:\ r_i\not\equiv r_j\pmod m$
  \item $(r_i,r_j)=1\ (\forall i\in R)$
  \end{itemize}
\end{enumerate}
\end{all}

\begin{tet}
$(a,m)=1$ és $\left\{\sor{r}{k}\right\}$ teljes/redukált mrsz. $\pmod m$\\
$\Rightarrow \left\{\sor{ar}{k}\right\}$ is teljes/redukált mrsz. $\pmod m$
\end{tet}

\subsection{Euler- és Fermat-tételek}
\begin{tet}[kis-Fermat-tétel]
\begin{itemize}
\item $p\pr \Rightarrow a^p\equiv a\pmod p$
\item $p\pr, (a,p)=1 \Rightarrow a^{p-1}\equiv 1\pmod p$
\end{itemize}
\end{tet}

\begin{tet}[Euler-Fermat-tétel]
$(a,m)=1 \Rightarrow a^{\varphi(m)}\equiv 1\pmod m$
\end{tet}

\begin{all}
$(m,n)=1 \Rightarrow \varphi(m,n)=\varphi(m)\varphi(n)$
\end{all}

\begin{all}
$\varphi(p^{\alpha})=p^{\alpha}-p^{\alpha-1}=p^{\alpha}(1-\frac{1}{p})$\\
$\Rightarrow n=\kan{p}{\alpha}{r} \Rightarrow
\varphi(n)=n\prod_{i=1}^{r}(1-\frac{1}{p})$
\end{all}

\subsection{Moduláris aritmetika}
\begin{dfn}
\begin{itemize}
\item $\left[a\right]_m+\left[b\right]_m:=\left[a+b\right]_m$
\item $\left[a\right]_m\cdot\left[b\right]_m:=\left[ab\right]_m$
\end{itemize}
\end{dfn}

\begin{pld}
$\pmod 5$ művelettáblák
\[ \begin{array}{c||c|c|c|c|c|}
{\bf +}	& 0 & 1 & 2 & 3 & 4 \\ \hline\hline
0	& 0 & 1 & 2 & 3 & 4 \\ \hline
1	& 1 & 2 & 3 & 4 & 0 \\ \hline
2	& 2 & 3 & 4 & 0 & 1 \\ \hline
3	& 3 & 4 & 0 & 1 & 2 \\ \hline
4	& 4 & 0 & 1 & 2 & 3 \\ \hline
\end{array}
\qquad \text{és} \qquad
\begin {array}{c||c|c|c|c|c|}
{\bf *}	& 0 & 1 & 2 & 3 & 4 \\ \hline\hline
0	& 0 & 0 & 0 & 0 & 0 \\ \hline
1	& 0 & 1 & 2 & 3 & 4 \\ \hline
2	& 0 & 2 & 4 & 1 & 3 \\ \hline
3	& 0 & 3 & 1 & 4 & 2 \\ \hline
4	& 0 & 4 & 3 & 2 & 1 \\ \hline
\end{array} \]
\end{pld}

\begin{all}
A $\pmod m$ maradékosztályok a fenti két művelettel kommutatív
egységelemes gyűrűt adnak.\\
Ha $m\pr \Rightarrow$ a mardékosztályok testet adnak.
\end{all}

\begin{dfn}
$\left[a\right]_m$ \emph{inverze} $\left[\bar{a}\right]_m$:\quad
$\left[a\right]_m\cdot\left[\bar{a}\right]_m=\left[1\right]_m\quad
a\bar{a}\equiv 1\pmod m$\\
($\left[a\right]_m$ \emph{invertálható}, ha $\exists$ inverze)\\
Jelölés: $\left[a\right]_m^{-1},\ a^{-1}\pmod m$
\end{dfn}

\begin{tet}
\begin{enumerate}
\item $a$ invertálható $\pmod m \Leftrightarrow (a,m)=1$
\item $a$ invertálható $\pmod m \Rightarrow \pmod m$ egyértelmű
\end{enumerate}
\end{tet}


\section{Lineáris kongruenciák}

\subsection{Lineáris kongruenciák megoldása}
\begin{tet}
\begin{enumerate}
\item $ax\equiv b\pmod m$ megoldható $\Leftrightarrow (a,m)\mid b$
\item a megoldások száma: $(a,m)$
\end{enumerate}
Megjegyzés: $ax\equiv b\pmod m \Leftrightarrow ax+my=b$
\end{tet}

\begin{tet}[Wilson]
\begin{enumerate}
\item $p\pr \Rightarrow (p-1)!\equiv -1\pmod p$
\item $m=4 \Rightarrow (m-1)!\equiv 2\pmod m$
\item $m>4 \Rightarrow (m-1)!\equiv 0\pmod m$
\item[$\Rightarrow$] $m>1 \pr \Leftrightarrow (m-1)!\equiv -1\pmod m$
\end{enumerate}
\end{tet}

\subsection{Lineáris kongruenciarendszerek}

\begin{tet}
\begin{enumerate}
\item $\left. \begin{array}{l}
  x\equiv c_1\pmod {m_1} \\
  x\equiv c_2\pmod {m_2}
  \end{array} \right\}
  \text{megoldható} \Leftrightarrow (m_1,m_2)\mid c_2-c_1$
\item $\exists! \pmod {\left[m_1,m_2\right]}$
\end{enumerate}
\end{tet}

\begin{tet}[Kínai maradéktétel]
$\sor{m}{r}>0$ páronként relatív prímek,\\
$\sor{a}{r}\in\Z$ ekkor az\\
\[ \left. \begin{array}{c}
  x\equiv a_1\pmod {m_1} \\
  x\equiv a_2\pmod {m_2} \\
  \vdots \\
  x\equiv a_r\pmod {m_r}
  \end{array} \right\}
  \begin{array}{l}
  \text{szimultán lineáris} \\
  \text{kongruenciarendszer \emph{megoldható}} \\
  \exists!\ \text{mo.} \pmod {\left[\sor{m}{r}\right]}
  \end{array} \]
azaz $\forall$ mo. $x=x_0+k\szsor{m}{r}\quad(k\in\Z)$ alakú
\end{tet}


\section{Magasabb fokú kongruenciák}

\subsection{Magasabb fokú kongruenciák megoldása}
\begin{tet}
Tetszőleges $n$-edfokú polinom kongruens egy legfeljebb $p-1$-edfokú
polinommal $\pmod p$, ha $p$ prím.
\end{tet}

\begin{dfn}
A $k$ egész az $f(x)\equiv 0\pmod m$ polinom kongruencia egy
\emph{megoldása}, ha $f(k)\equiv 0\pmod m$.
\end{dfn}

\begin{tet}
$f(x)=\pol{a}{x}{n}$ egészegyütthatós\\
$\Rightarrow f(x+y)=f(x)+yf'(x)+y^2g(x,y)$ Ezt felhasználva:
\[ f(a+tp)=f(a)+tpf'(a)+t^2p^2g(a,tp)\equiv f(a)+tpf'(a) \pmod {p^2} \]
Ha $f(a)\equiv 0\pmod p$ és $f(a+tp)\equiv 0\pmod {p^2}$, 
akkor $p$-vel osztva:
\[ tf'(a)\equiv -(f(a)/p)\pmod p \]
és ennek a lineáris kongruenciának egyetlen megoldása van.
\end{tet}

\begin{tet}
Legyen $a$ az $f(x)\equiv 0\pmod {p^r}$ egy megoldása.
\begin{enumerate}
\item $p\nmid f'(a) \Rightarrow f(x)\equiv 0\pmod {p^{r+1}}$ egyetlen
  megoldása $x=a+p^rt$, ahol $t$ az egyetlen megoldása a
  $p^rtf'(a)\equiv -f(a)\pmod {p^{r+1}}$ kongruenciának.
\item $p\mid f'(a)$ és $p^{r+1}\mid f(a) \Rightarrow
  f(x)\equiv 0\pmod {p^{r+1}}$ megoldásainak száma $p$, és ezek
  alakja $x\equiv a+p^rt\pmod {p^{r+1}}$, $t$ tetszőleges.
\item $p\mid f'(a)$ és $p^{r+1}\nmid f(a) \Rightarrow 
  f(x)\equiv 0\pmod {p^{r+1}}$ nem oldható meg úgy, hogy
  $x\equiv a\pmod {p^r}$ legyen.
\end{enumerate}
\end{tet}
		    
\subsection{Polinomok modulo prím}
\begin{tet}
Ha $f$ $n$-edfokú polinom, $p$ prím és $f$ nem mindegyik
együtthatója osztható $p$-vel, akkor az $f(x)\equiv 0\pmod p$
kongruenciának legfeljebb $n$ megoldása van $\pmod p$.
\end{tet}

\begin{tet}
$F: \Z_p\to\Z_p \Rightarrow 
\exists f \max (p-1)$-edfokú polinom $: F(x)\equiv f(x)\pmod p\ \forall x$
\end{tet}

\begin{tet}
$f(x)\equiv 0\pmod p$, $f$ $n$-edfokú, főegyütthatója $1$\\
$f$-nek pontosan $n$ különböző megoldása van 
$\Leftrightarrow f(x)$ az $x^p-x$ tényezője.
\[ x^p-x=f(x)\cdot q(x)+p\cdot s(x),\ \deg q=p-n,\ \deg s<n \]
Követekezmény: $d\mid p-1 \Rightarrow x^d\equiv 1\pmod p$ kongruenciának
$d$ különböző megoldása van.
\end{tet}


\section{Rend, hatványmaradékok}

\subsection{Rend}
\begin{dfn}
$m>0,\ m,a\in\Z,\ (a,m)=1$ Azt mondjuk, hogy\\
\emph{$a$ rendje $h$}, ha $a^h\equiv 1\pmod m$, de 
$a^k\not\equiv 1\pmod m$, ha $0<k<h$\\
Jelölés: $\ord_ma=h,\ o_m(a)=h$
\end{dfn}

\begin{tet}[Rend tulajdonságai]
\begin{enumerate}
\item $\ord_ma=h \Rightarrow a^k\equiv 1\pmod m \Leftrightarrow h\mid k$
\item[$\Rightarrow$] $(a,m)=1 \Rightarrow \ord_ma\mid\varphi(m)$
\item[$\Rightarrow$] $(a,m)=1, a^i\equiv a^j\pmod m \Leftrightarrow 
  i\equiv j\pmod {\ord_ma}$
\item $\ord_ma=h \Rightarrow \ord_ma^k=\frac{h}{(h,k)}$
\end{enumerate}
\end{tet}

\begin{dfn}
$g$ \emph{primitív gyök} $\pmod m$, ha $\ord_mg=\varphi(m)$
\end{dfn}

\begin{tet}
$m$-nek ($m>1$) pontosan akkor van primitív gyöke, ha $m=2$ vagy
$m=4$ vagy $m=p^{\alpha}$ vagy $m=2\cdot p^{\alpha}$, ahol $p$ 
páratlan prím és $\alpha>0$.
\end{tet}

\begin{tet}
a $\pmod m$ primitív gyökök száma $\varphi(\varphi(m))$.
\end{tet}

\begin{dfn}
$p\pr, (a,p)=1$ és $x^n\equiv a\pmod p$-nek van megoldása, akkor $a$
\emph{$n$. hatványmaradék}.
\end{dfn}

\begin{dfn}
$g$ primitív gyök $\pmod m$, $(a,m)=1$ és $g^n\equiv a\pmod m \Rightarrow
\ind_ga=n$ ($n$ $a$-nak $g$ \emph{alapú indexe}) ($1\leq n\leq \varphi(m)$).\\
Megjegyzés: az index ugyanúgy működik, mint a logaritmus.
\end{dfn}

\begin{tet}
$p\pr (a,p)=1$ a $x^n\equiv a\pmod p$ kongruenciának
\[ \begin{array}{cc}
  (n,p-1) & \text{megoldása van} \\
  0       & \text{megoldása van}
   \end{array} \Leftrightarrow
   \begin{array}{c}
  a^{\frac{p-1}{(n,p-1)}}\equiv 1\pmod p \\
  a^{\frac{p-1}{(n,p-1)}}\not\equiv 1\pmod p
   \end{array} \Leftrightarrow
   \begin{array}{c}
  (n,p-1)\mid\ind_ga \\
  (n,p-1)\nmid\ind_ga
   \end{array} \]
\end{tet}

\subsection{Négyzetes (kvadratikus) maradékok}
\begin{dfn}
$(a,m)=1$, $a$ \emph{négyzetes (kvadratikus) maradék/nemmaradék}, ha
$x^2\equiv a\pmod m$-nek van/nincs megoldása.
\end{dfn}

\begin{dfn}
$p$ páratlan prím, ekkor $\left(\frac{a}{p}\right)$-t \emph{Legendre-jelnek
(Legendre-szimbólumnak)} nevezzük és a következőképp definiáljuk:
\[ \left(\frac{a}{p}\right)=\left\{\begin{array}{ll}
  1,  & a \text{kvadratikus maradék} \\
  -1, & a \text{kvadratikus nemmaradék} \\
  0   & a\equiv 0\pmod p
   \end{array}\right. \]
\end{dfn}

\begin{tet}[A Legendre-jel tulajdonságai]
$p$ páratlan prím
\begin{enumerate}
\item $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p$
\item a kvadratikus maradékok száma $\pmod p$ $\frac{p-1}{2}$
\item $\left(\frac{a}{p}\right)\cdot\left(\frac{b}{p}\right)=
  \left(\frac{ab}{p}\right),\quad
  \left(\frac{a_1}{p}\right)\cdot\ldots\cdot\left(\frac{a_k}{p}\right)=
  \left(\frac{\sor{a}{k}}{p}\right)$
\item $a\equiv b\pmod p \Rightarrow
  \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$
\item $(a,p)=1 \Rightarrow \left(\frac{a^2}{p}\right)=1,\ 
  \left(\frac{a^2b}{p}\right)=\left(\frac{b}{p}\right)$
\item $\left(\frac{1}{p}\right)=1,\ \left(\frac{-1}{p}\right)=
  (-1)^{\frac{p-1}{2}}=\left\{\begin{array}{ll}
  1,  & p=4k+1 \\
  -1, & p=4k-1
  \end{array}\right.$
\item[$\Rightarrow$] $x^2+1\equiv 0\pmod p$ megoldható, ha $p=4k+1$, nem
  megoldható ha $p=4k-1$, a megoldás $\pm\left(\frac{p-1}{2}\right)!$
\end{enumerate}
\end{tet}

\begin{tet}[Gauss-lemma]
$(a,p)=1$, tekintsük $a,2a,\ldots,\frac{p-1}{2}a$ számok legkisebb
abszolútértékű maradékát $\pmod p$ és legyen $m$ a negatívak száma.\\
Ekkor $\left(\frac{a}{p}\right)=(-1)^m$
\end{tet}

\begin{tet}
$p$ páratlan prím
\begin{enumerate}
\item $(a,2p)=1 \Rightarrow \left(\frac{a}{p}\right)=
  (-1)^{\ds\sum_{i=1}^{\frac{p-1}{2}}\left\lfloor\frac{ai}{p}\right\rfloor}$
\item $\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$
\end{enumerate}
\end{tet}

\begin{lem}
$a,b$ páratlanok, $(a,b)=1$
\[ \frac{a-1}{2}\cdot\frac{b-1}{2}=
  \sum_{i=1}^{\frac{b-1}{2}}\left\lfloor\frac{ai}{b}\right\rfloor+
  \sum_{j=1}^{\frac{a-1}{2}}\left\lfloor\frac{bj}{a}\right\rfloor \]
\end{lem}

\begin{tet}[Gauss-féle kvadratikus reciprocitási tétel]
$p,q$ páratlan prím ($p\ne q$) $\Rightarrow \left(\frac{p}{q}\right)\cdot
\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$
\[ \Rightarrow \begin{array}{rcl}
  \left(\frac{p}{q}\right) &=& \left(\frac{q}{p}\right) \\
  \left(\frac{p}{q}\right) &=& -\left(\frac{q}{p}\right)
   \end{array} \Leftrightarrow
   \begin{array}{l}
  p\ \text{vagy}\ q\quad 4k+1\ \text{alakú} \\
  p\ \text{és}\ q\quad 4k+3\ \text{alakúak}
   \end{array} \]
\end{tet}

\begin{dfn}
$m>1$ páratlan, $m=\kan{p}{k}{r}$, $(a,m)=1$ ekkor 
$\left(\frac{a}{m}\right)$-t \emph{Jacobi-jelnek (Jacobi-szimbólumnak)}
nevezzük és a következőképp definiáljuk:
\[ \left(\frac{a}{m}\right)=
  \left(\frac{a}{p_1}\right)^{k_1}\cdot\ldots\cdot
  \left(\frac{a}{p_r}\right)^{k_r} \]
Megjegyzések:
\begin{itemize}
\item $m\pr \Rightarrow$ a Jacobi-jel azonos a Legendre-jellel
\item $\left(\frac{a}{m}\right)=1$ nem jelenti, hogy $x^2\equiv a\pmod m$
  megoldható, csak ha $\forall p\mid m$-re $\left(\frac{a}{p}\right)=1$
\end{itemize}
\end{dfn}

\begin{tet}[A Jacobi-jel tulajdonságai]
$n,m>1$, $(a,m)=(b,m)=1$
\begin{enumerate}
\item $\left(\frac{a}{m}\right)\cdot\left(\frac{b}{m}\right)=
  \left(\frac{ab}{m}\right)$
\item $\left(\frac{a}{m}\right)\cdot\left(\frac{a}{n}\right)=
  \left(\frac{a}{mn}\right)$
\item $\left(\frac{2}{m}\right)=(-1)^{\frac{m^2-1}{8}}$
\item $a\equiv b\pmod m \Rightarrow 
  \left(\frac{a}{m}\right)=\left(\frac{b}{m}\right)$
\item $\left(\frac{-1}{m}\right)=(-1)^{\frac{m-1}{2}}$
\item $m,n$ páratlanok, $(m,n)=1 \Rightarrow
  \left(\frac{m}{n}\right)\cdot\left(\frac{n}{m}\right)=
  (-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}$
\end{enumerate}
\end{tet}

\begin{all}[Moduláris négyzetgyökvonás]
$n=pq,\quad p,q$ páratlan prímek\\
$x^2\equiv a\pmod n$ megoldható $\Rightarrow 4$ különböző megoldás van
\end{all}

\section{Számelméleti függvények}

\subsection{Függvénydefiníciók, multiplikativitás, additivitás}
\begin{dfn}
$f$ függvény \emph{számelméleti függvény}, ha $\Z^+\subseteq{\cal D}_f$
\end{dfn}

\begin{dfn}
$f$ számelméleti függvény
\begin{itemize}
\item \emph{multiplikatív}, ha $f(nm)=f(n)f(m)\ \forall (n,m)=1$
\item \emph{additív}, ha $f(nm)=f(n)+f(m)\ \forall (n,m)=1$
\item \emph{teljesen multiplikatív}, ha $f(nm)=f(n)f(m)\ \forall n,m$
\item \emph{teljesen additív}, ha $f(nm)=f(n)+f(m)\ \forall n,m$
\end{itemize}
\end{dfn}

\begin{all}
\begin{enumerate}
\item $\exists n: f(n)\ne 0$ és $f$ multiplikatív $\Rightarrow f(1)=1$
\item $g$ additív $\Rightarrow g(1)=0$
\end{enumerate}
\end{all}

\begin{tet}
Multiplikatív és additív függvényeket elég csak prímhatványokra, teljesen
multiplikatív és teljesen additív függvényeket pedig csak prímekre ismerni:
\[ \begin{array}{ll}
   f\ \text{mult.} & \text{ha}\ 
     f\left(\ds\prod_{\forall i}p_i^{\alpha_i}\right)=
     \ds\prod_{\forall i}f(p_i^{\alpha_i}) \\
   f_t\ \text{t. mult.} & \text{ha}\ 
     f_t\left(\ds\prod_{\forall i}p_i^{\alpha_i}\right)=
     \ds\prod_{\forall i}f_t(p_i)^{\alpha_i} \\
   g\ \text{add.} & \text{ha}\ 
     g\left(\ds\prod_{\forall i}p_i^{\alpha_i}\right)=
     \ds\sum_{\forall i}g(p_i^{\alpha_i}) \\
   g_t\ \text{t. add.} & \text{ha}\ 
     g_t\left(\ds\prod_{\forall i}p_i^{\alpha_i}\right)=
     \ds\sum_{\forall i}g_t(p_i)^{\alpha_i}
   \end{array} \]
\end{tet}

\begin{tet}
Két multiplikatív függvény szorzata és hányadosa is multiplikatív.
\end{tet}

\begin{dfn}
\begin{itemize}
\item $d(n) := n$ osztóinak száma
\item $\sigma(n) := n$ osztóinak összege
\item $\nu(n) := n$ prímtényezőinek száma
\item $\kappa(n) := n$ különböző prímtényezőinek száma
\item $\varphi(n) := n$-nél kisebb $n$-hez relatív prímek száma
\item $\mu(n) := \left\{\begin{array}{ll}
  1,      & n=1 \\
  (-1)^r, & n=\sor{p}{r}\ p_i\ne p_j,\ \text{ha}\ i\ne j \\
  0,      & \text{egyébként}
       \end{array}\right.$
\end{itemize}
\end{dfn}

\begin{all}
$d, \sigma, \varphi, \mu$ multiplikatív függvények
\end{all}

\begin{tet}
$n=\kan{p}{\alpha}{r}$
\begin{enumerate}
\item $d(n)=\ds\prod_{i=1}^r(\alpha_i+1)$
\item $\sigma(n)=\ds\prod_{i=1}^r\frac{p_i^{\alpha_i+1}-1}{p_i-1}$
\item $\varphi(n)=\ds\prod_{i=1}^r(p_i^{\alpha_i}-p_i^{\alpha_i-1})$
\end{enumerate}
\end{tet}

\subsection{Összegzések}
\begin{tet}
$\ds\sum_{d\mid n}\varphi(d)=n$
\end{tet}

\begin{dfn}
\begin{itemize}
\item $f$ számelméleti függvény \emph{összegzési függvénye} $f^+$, melyre:
  $f^+(n)=\ds\sum_{d\mid n}f(d)$
\item $f$ számelméleti függvény \emph{megfordítási függvénye} $f^-$, melyre:
  $f(n)=\ds\sum_{d\mid n}f^-(d)\quad((f^-)^+=f)$
\end{itemize}
\end{dfn}

\begin{all}
$f^-$ egyértelműen létezik
\end{all}

\begin{all}
$f$ multiplikatív $\Leftrightarrow f^+$ is multiplikatív
\end{all}

\begin{all}
\[ \mu^+(n)=e(n):=\left\{\begin{array}{ll}
  1, & \text{ha}\ n=1 \\
  0, & \text{ha}\ n>1
   \end{array}\right. \]
\end{all}

\begin{tet}[Möbius-féle inverziós/megfordítási formula]
\[ g(n)=\sum_{d\mid n}f(d) \Leftrightarrow 
  f(n)=\sum_{d\mid n}\mu\left(\frac{n}{d}\right)\cdot g(d) \]
\end{tet}

\begin{dfn}
$f$ és $g$ számelméleti függvények \emph{konvolúcióját} a következőképpen
definiáljuk:
\[ (f\star g)(n) := \sum_{d\mid n}f(d)\cdot g\left(\frac{n}{d}\right) \]
Megjegyzés:
\begin{itemize}
\item $f^+=f\star1$
\item $f^-=f\star\mu$
\end{itemize}
\end{dfn}

\begin{tet}
A $\star$ reláció kommutatív, asszociatív, egységelemes: 
$e(n)=\left\{\begin{array}{ll}
  1, & \text{ha}\ n=1 \\
  0, & \text{ha}\ n>1
\end{array}\right.$
\end{tet}

\begin{dfn}[Dirichlet-sor]
$\ds\sum_{n=1}^{\infty}\frac{f(n)}{n^s}$ (azon $s$ helyeken, ahol konvergens)
\end{dfn}

\begin{dfn}[Riemann-féle zeta függvény]
$\zeta(s)=\ds\sum_{n=1}^{\infty}\frac{1}{n^s}$ (abszolót konvergens, $s>1$)
\end{dfn}

\begin{tet}[Euler-féle szorzatalak]
\[ \zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^s}=
  \ds\prod_{p\pr}\left(1-\frac{1}{p^s}\right)^{-1} \]
\end{tet}

\begin{tet}
$f,g,h$ számelméleti függvények és $F,G,H$ Dirichlet-soraik abszolút
konvergensek, ekkor\\
$h=f\star g \Rightarrow H=F\cdot G$
\end{tet}

\begin{tet}[Völgytétel]
\[ \forall K\in\N^+: \exists\infty\ \text{sok}\ n: 
  d(n-1)-d(n)>K, d(n+1)-d(n)>K \]
\end{tet}
 
\begin{tet}[Hegytétel]
\[ \forall K\in\N^+: \exists\infty\ \text{sok}\ n: 
  d(n)-d(n-1)>K, d(n)-d(n+1)>K \]
\end{tet}

\begin{tet}
\[ \left|\frac{\ds\sum_{i=1}^nd(i)}{n}-\ln n\right|<1 \]
\end{tet}

\subsection{Minimális univerzális kitevő (exponens)}
\begin{dfn}
$\lambda>0$ \emph{minimális univerzális kitevő} $\pmod n$, ha $\lambda$ a
legkisebb olyan egész, hogy $a^{\lambda}\equiv 1\pmod n\quad\forall (a,n)=1$
esetén (szokás $\lambda(n)$ függvényként írni)\\
Megjegyzés:
\begin{itemize}
\item ha $\exists$ primitív gyök $\Rightarrow \lambda(n)=\varphi(n)$
\item ha $\ord_na=k \Rightarrow k\mid\lambda(n)$
\end{itemize}
\end{dfn}

\begin{lem}
$\ord_na=k, \ord_nb=l \Rightarrow \exists g: \ord_ng=\left[k,l\right]$
\end{lem}

\begin{lem}
$M$ a maximális rend $\Rightarrow M=\lambda(n)$, $\exists \lambda(n)$ rendű
elem.
\end{lem}

\begin{tet}
$p\pr \Rightarrow \exists$ primitív gyök $\pmod p$
\end{tet}

\end{document}
