

\documentclass[12pt]{amsart} 
\usepackage[dvips]{graphics, color}
\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{lemma}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{exempel}
\newtheorem{exempel}[theorem]{Exempel}
\theoremstyle{corollary}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{proposition}
\newtheorem{proposition}[theorem]{{Proposition}}
\theoremstyle{clam}
\newtheorem{clam}[theorem]{Claim}
\theoremstyle{conjecture}
\newtheorem{con}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{re}[theorem]{{Remark}}
\newtheorem{no}[theorem]{Notation}



\newtheorem{quest}[theorem]{Question}

\newtheorem{problem}[theorem]{Problem}





\newtheorem{worning}[theorem]{{\rm W\sc orning}}

\newtheorem{para}[theorem]{}

\newtheorem{examp}[theorem]{Example}

\newtheorem{exercise}[theorem]{Exercise}

\newcommand\pn[1]{{\mathbb P}^{#1}}
\newcommand\cal[1]{\mathcal {#1}}
\newcommand\cL{\mathcal L}
\newcommand\cZ{\mathcal Z}
\newcommand\cO[1]{\cal{O}_{\cal{{#1}}}}
\newcommand\X[1]{X^{[{#1}]}}
\newcommand\zed{{\mathbb Z}}
\newcommand\nat{{\mathbb N}}
\newcommand\rat{{\mathbb Q}}
\newcommand\real{{\mathbb R}}
%\newcommand\a{{\aa}}
\textwidth16cm
\textheight20cm
\oddsidemargin-0.3cm
\evensidemargin0.4cm
%\pagestyle{plain} 
\newtheorem{Definition}{\sf Definition}

 \title{Lektion 03-08}


\begin{document}
\maketitle
\section*{Modul\"ar aritmetik}

Klockan \"ar nu $9:00$. Hur mycket kommer klockan  om $16$ timmar?
Man  kan ta $9+16=25$ men eftersom  en dygn bara har $24$ timmar  blir det $kl:01$. Vi s\"agar d{\aa} att vi r\"acknar ``modulo 24''. Det betyder att :
\begin{itemize}
\item vi delar tal med $24$
\item vi tar resten. Vi s\"ager att tv{\aa} tal \"ar ``ekvivalenta'' (lika modulo $24$) om de har samma resten. Om $a$ och $b$ \"ar ekvivalenta skriver vi: $a\equiv b $.
\end{itemize}
Vi har att $25=24+1$ och $1=0\cdot 24+1$, dvs $25\equiv 1$.
\begin{definition} Tv{\aa} tal \"ar eqvivalenta {\it modulo n}, $a\equiv_n b$ om
$$a=kn+b\text{ d\"ar }k\in\zed$$
\end{definition}
Vi ska t\"anka p{\aa} $a$ och $b$ som ``samma tal modulo n'' . Till exampel modulo $2$ har vi:
$$... -6\equiv_2 -4 \equiv_2 -2 \equiv_2 0 \equiv_2 2 \equiv_2 4 \equiv_2 6 ...$$
$$... -5\equiv_2 -3 \equiv_2 -1 \equiv_2 1 \equiv_2 3 \equiv_2 5 \equiv_2 7 ...$$
Alla j\"amna heltal \"ar ekvivalenta till $0$ modulo $2$ och alla udda heltal \"ar ekvivalenta till $1$ modulo $2$. S{\aa} vi kan beteckna alla j\"amna tal med $[0]$ och alla udda heltal med $[1]$ och bilda en ny m\"angd (m\"angden av heltal modulo $2$):
$$\zed_2=\{[0],[1]\}$$

\vspace{.1in}
\noindent{\it Exempel}. R\"akna $26+32$ modulo $2$.

\vspace{.1in}

Eftersom $26+32=58$ och $58\equiv_2 [0]$ s\"ager man att $26+32=0$ modulo $2$.

\vspace{.1in}


P{\aa} samma s\"att kan man bilda m\"angen av heltal modulo n:
$$\zed_n=\{[0],[1],...,[n-1]\}$$
d\"ar $[k]$ representerar alla heltal p{\aa} formen $tn+k$ d\"ar $t\in\zed$, dvs
$[k]=\{tn+k\text{ d\"ar }t\in\zed \}$. Vi s\"ager att $k$ \"ar ekvilansklassen av $k$ modulo $n$ och $\zed_n$ \"ar m\"angden av ekvilensklasser modulo $n$.

En multipel av $n$ blir alltid $[0]$ modulo $n$.
\vspace{.1in}

\noindent{\it Notera att:} om $a\equiv_n c$ och $b\equiv_n d$ d{\aa} 
$a=kn+c$ och $b=hn+d$ d\"ar $k,h\in\zed$. Det f\"oljer att
$a+b=(k+h)n+(d+c)$ och $ab=(khn+kd+ch)n+dc$. Detta visar att
\begin{itemize}
\item $a+b\equiv_n c+d$, dvs att $[a]+[c]=[a+c]$.
\item $ac\equiv_n cd$, dvs att $[a]\cdot[c]=[a\cdot c]$
\end{itemize}

\vspace{.1in}

\noindent{\it Exempel}.

 \begin{itemize}
\item Ber\"akna $27\cdot 35$ modulo 4.

$27\cdot 35=(6\cdot 4+3)\cdot(4\cdot 8+3)\equiv_4 3\cdot 3=4\cdot 2+1\equiv_4 1$
\item Ber\"akna $65432$ modulo $9$.

$65432=6\cdot 10^4+5\cdot 10^3+4\cdot 10^2+3\cdot 10+2\equiv_9 6\cdot 1^4+5\cdot 1^3+4\cdot 1^2+3\cdot 1+2=20\equiv_9 2$

\end{itemize}

Man kan sammafattar resultatet av addition och multliplication modulo n i en tabel. Till exempel, modulo 6:

\[\begin{tabular}{c|lcccccr}
+&0&1&2&3&4&5&\\ \hline
0&0&2&2&3&4&5\\ 
1&1&2&3&4&5&0\\
2&2&3&4&5&0&1\\
3&3&4&5&0&1&2\\
4&4&5&0&1&2&3\\
5&5&0&1&2&3&4
\end{tabular}\]

\vspace{.1in}

\[\begin{tabular}{c|lcccccr}
$\cdot$ &0&1&2&3&4&5\\ \hline
0&0&0&0&0&0&0\\ 
1&0&1&2&3&4&5\\
2&0&2&4&0&2&4\\
3&0&3&0&3&0&3\\
4&0&4&2&0&4&2\\
5&0&5&4&3&2&1
\end{tabular}\]

\vspace{.1in}

\noindent{\it Notera} kancelleringslagen g\"aller inte. Till example i $\zed_6$ har vi
$$2\cdot 2=2\cdot 5\text{ men } 2\neq 5$$
 Kancelleringslagen g\"aller om elemnt \"ar INVERTERBARA.

\begin{definition}
Ett element $a\in\zed_n$ \"ar inverterbara om det finns $b\in\zed_n$ s\aa dan att:
$$a\cdot b=b\cdot a=1$$
Elementet $b$ kallas {\it inversen} av $a$.
\end{definition}

\vspace{.1in}

\noindent{\it SATS}. Ett element $0\neq a\in\zed_n$ \"ar inverterbart om och endast om $sgd(a,n)=1$.

\vspace{.1in}

\noindent{\it BEVIS}. Antag f\"orst att $sgd(a,n)=1$. Det Finns  heltal $x,y$ s\aa dan att $1=ax+yn$ och d\"armed \"ar $1\equiv_n ax$. Det betyder att:
$$[1]=[ax]=[a]\cdot[x].$$ Antag nu att $a$ \"ar invertebar, dvs det finns $b$ s\aa dan att $[ab]=[1]$. Det f\"oljer att 
$$ab=kn+1,\text{ och d\"armed }1=ab-kn$$
Det betyder att $a$ och $n$ \"ar relativt prima.

\vspace{.1in} 

\noindent{\it Exempel}. Best\"am inversen till $41$ i $\zed_{323}$.

Inversen existerar eftersom $sgd(41,323)=1$. Vi ber\"akna den med hj\"alp av Euklides algoritm:

\[ \begin{array}{lllll}
323&=&8\cdot 41& - & 5\\
41&=&8\cdot 5 & + & 1\\
\end{array}\]

D\"armed  g\"aller $1=-63\cdot 41+8\cdot 323\equiv_{323} -63\cdot 41$. Inversen \"ar allts{\aa} $[-63]=[260]$.

\vspace{.1in}

Man kan l\"osa ekvationer modulo $n$. Vi  ska l\"osa
$$6x\equiv_{17} 8$$
Vi vill hitta (alla) $x\in\zed_{17}$ s{\aa}dan att $6x\equiv_{17} 8$. 

Eftersom $6x\equiv_{17} 8$ om och endast om $6x=17y+8$ ska vi l\"osa den diofantiska ekvationen $$6x-17y=8.$$ Heltalen $6$ och $17$ \"ar relatvt prima och Euklides algoritm ger:

\[ \begin{array}{lllll}
17&=&2\cdot 6& + & 5\\
6&=&5\cdot 1 & + & 1
\end{array}\]
D{\aa} blir $1=6-5=5-16+2\cdot 6=3\cdot 6-17$. Det f\"oljer att $x=24+17k$ och $y=8+6k$ \"ar den allm\"anna l\"osning. Nu ska vi ber\"akna den modulo $17$.
\begin{itemize}
\item $x=24+17k\equiv_{17} 7$;
\item $y=8+6k$;
\end{itemize}
Svaret \"ar $x=7$ (vi menar att $x=[7]\in\zed_{17}$).



\vspace{.1in}

\noindent{\it Exempel} L\"os ekvationen $6x\equiv_{16} 8$.

Vi ska l\"osa ekvationen $6x-16y=8$. Vi ser direkt att $gcd(6, 16)=2$ och Euklides algoritm ger $2=3\cdot 6-16$ (man kan ber\"akna det direkt!). Vidare vet vi att $lcd(6,16)=16\cdot 3$. Den allm\"anna l\"osning blir:
\begin{itemize}
\item $x=12+8k\equiv_{16}8+8k$; vi har d{\aa} tv{\aa} m\"ojliga fall, n\"amlingen $x=4$ ($k=-1$) eller $x=12$ ($k=0$).
\item $y=4+3k$; 
\end{itemize}
Svaret \"ar $x=4$ och $x=12$ (vi menar $x=[4],[12]\in\zed_{16}$).

\vspace{.3in}

\end{document}



