\documentclass[a4paper]{article}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
\sloppy
\pagestyle{empty}

\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\addtolength\textwidth{4.5cm}
\addtolength\hoffset{-2.5cm}
\addtolength\textheight{5cm}
\setlength\topmargin{-1cm}

\usepackage{amssymb}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe II.}
\\\vspace*{1mm}
10. gyakorlat, 2007. április 18.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{8mm}
\textbf{\LARGE Számelmélet III. – Csoportelmélet}
\end{center}

\vspace*{10mm}

\begin{enumerate}
\setcounter{enumi}{102}

\item Teljes maradékrendszer-e modulo 77 az 1, 11, 21, \dots 761
számhalmaz?

\item Redukált maradékrendszer-e modulo 32 az 5, 15, 25, \dots, 155
számhalmaz?

\item Legyen $n$ osztható $k$-val. Bizonyítsuk be, hogy $\varphi(n)$ is
osztható $\varphi(k)$-val.

%\item Biz. be, hogy $2^{1998}-1$ osztható $(2^{37}-1)$-gyel.

\item Mivel kongruens mod 77 az $1998^{1979}$ szám?

\item Mi $7^{6^{5^{4^{3^2}}}}$ utolsó számjegye a 10-es számrendszerben?

\item Kiszámítandó $(((43^{43})^{43})^{43})^{43}$ modulo 49.

\item Biz.\ be, hogy a $10^n+3$ alakú számok között végtelen sok
osztható 13-mal.

\item Legyen a $p$ prím esetén $a_1, a_2, \dots, a_{p-1}$ RMR (mod $p$).
Biz: $a_1^{p-2}, a_2^{p-2}, \dots, a_{p-1}^{p-2}$ szintén RMR (mod $p$).


\item Adjuk meg az összes 1, 2, 3, illetve 4 elemű nem izomorf csoport
művelettábáját.

\item Értelmezzük az egész számok halmazán az $a \star b=a+b+1$
képlettel megadott műveletet. Mutasd meg, hogy $(\mathbb{Z}, \star)$
csoport. Milyen korábbról ismert csoporttal izomorf $(\mathbb{Z}, \star)$?

\item Határozzuk meg az alábbi alakzatok szimmetriacsoportját. \\
\begin{tabular}{llllllll}
(a)&szabályos háromszög;&$\qquad$&(c)&téglalap;&$\qquad$&(e)&kocka;\\
(b)&paralelogramma;&$\qquad$&(d)&deltoid;&$\qquad$&(f)&tetraéder.
\end{tabular}

\item A $G$ csoport $e$ egységére és $x,y$ elemeire $x^2=e$ és
$xyx^{-1}=y^3$. Bizonyítsuk be, hogy $y^8=e$.

\item Az alábbi következtetések közül melyek teljesülnek minden csoportban? \\
\begin{tabular}{llllllll}
(a)& $ax=ay \Rightarrow x=y$; &$\qquad$&
(d)& $abx=aby \Rightarrow x=y$; &$\qquad$&
(g)& $ax=1 \Rightarrow x=a^{-1}$; \\
(b)& $xa=ya \Rightarrow x=y$; &$\qquad$&
(e)& $axb=ayb \Rightarrow x=y$; &$\qquad$&
(h)& $abx=1 \Rightarrow x=a^{-1}b^{-1}$; \\
(c)& $xa=ay \Rightarrow x=y$; &$\qquad$&
(f)& $bxa=ayb \Rightarrow x=y$; &$\qquad$&
(i)& $abx=1 \Rightarrow x=b^{-1}a^{-1}$. \\
\end{tabular}

\item Legyen $a_1, \ldots a_{\varphi(m)}$ az $m$-nél kisebb, $m$-hez relatív
prím pozitív egészek halmaza. Hasonlóan legyen $b_1, \ldots b_{\varphi(n)}$
az $n$-nél kisebb, $n$-hez relatív prím pozitívak halmaza.
\begin{enumerate}
\item Mutassuk meg, hogy minden $1\leq i\leq \varphi(m)$ és $1\leq j\leq
\varphi(n)$ esetén pontosan egy olyan $mn$-nél kisebb $x$ szám van, amelyre
$x\equiv a_i (m)$ és $x\equiv b_j (n)$.
\item Mutassuk meg, hogy az így kapott $x$ relatív prím $mn$-hez.
\item Bizonyítsuk be, hogy ha $m$ és $n$ relatív prímek, akkor
$\varphi(mn)=\varphi(m)\varphi(n)$.
\end{enumerate}

\end{enumerate}

\end{document}
