%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%    LEKTION 1   %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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-05}


\begin{document}
\maketitle
Vi b\"orjar med lite terminologi om heltal.
\begin{definition}
L{\aa}t $a,b$ vara tv{\aa} heltal. Man s\"ager att {\it b delar a} eller att $b$ \"ar en {\it delare} till $a$ om det finns ett heltal $n$ s{\aa}dan att 
$$a=nb$$
\end{definition}
Man skriver $b|a$ n\"ar $b$ delar $a$ och $b\not | a$ n\"ar s{\aa} inte \"ar fallet. Exempelvis $4|16$, $3\not |8$. 

\noindent{\it Exempel}:
\begin{itemize}
\item $\pm a|a$ och $\pm 1|a$ f\"or varje $a\in\zed$. Man s\"ager att $b$ \"ar en {\"akta} delare till $a$ om $b|a$ och $b\neq \pm a,\pm 1$.
\item $b|0$ f\"or varje heltal $b$, eftersom $0=0b$; Om  $0|a$ s{\aa} g\"aller $a=0$.
\item visa att om $a|b$ och $b|a$ d{\aa} $a=\pm b$.

Om $a=0$ \"ar ocks{\aa} $b=0$ s{\aa}  vi  kan anta  att $a\neq 0$. Eftersom $a|b$ och $b|a$ s{\aa} \"ar $b=na$ och $a=mb$. Detta ger att $a=mna$ och d\"armed $mn=1$. Eftersom $m,n\in\zed$ s{\aa} har vi att $m=n=1$ eller $m=n=-1$.
\item Visa att $a|b$ och $b|c$ ger $a|c$. 

Eftersom $b=na$ och $c=mb$ har vi att $c=mna$ och $mn\in\zed$. Allts{\aa} \"ar $a$ en delare till $c$.
\end{itemize}

\noindent{\"Ovning.} \begin{enumerate}
\item Visa att om $c|a$ och $c|b$ d{\aa}  g\"aller $c|xa+yb$ f\"or alla  heltal $x$ och $y$.
\item Visa att om $b|a$ och $a>0$ d{\aa} \"ar $b\leq a$.
\end{enumerate}
\begin{definition} Ett heltal $p>1$ kallas att {\it primtal} om det saknar \"akta delare.
\end{definition}

\vspace{.2in}

Man ska t\"anka p{\aa} primtalen som ``byggstenar'' f\"or heltalen, p{\aa} grund av:

\vspace{.2in}

\noindent {\it Aritmetikens fundamentalsats}(AFS). Varje heltal $n>1$ kan skrivas som en produkt av primtal:
$$n=p_1p_1...p_k$$
Den kallas en {\it primfaktorisering}.

\vspace{.1in}

\noindent{\sl BEVIS}. Om $n$ \"ar ett primtal d{\aa} \"ar primfaktorisering  $n=n$.
Antar att $n$ inte \"ar ett primtal och l{\aa}t $b$ vara en \"akta delare till $n$. Det betyder att $n=bm$ d\"ar $m\in\zed$. Om $b$ eller $m$ , s\"ag $b$, \"ar ett primtal, s\"att $b=p_1$ och forts\"att p{\aa} samma s\"att med $m$. Efter ett \"andligt antal steg f{\aa}r man en primfaktorisering av $n$.

\vspace{.1in}

\noindent{\it Exempel} Talet 1610 primfaktoriseras som 
$$1610=2\cdot 5\cdot 7 \cdot 13$$

\vspace{.1in}

\noindent {\it NOTERA} att primfaktoriseringen \"ar inte entydig. Den blir s{\aa} om man bortser fr{\aa}n ordningen mellan faktorer!

Nu kan vi visa en mycket viktig sats:

\vspace{.1in}

\noindent {\it EUKLIDES SATS}. Det finns o\"anligt m{\aa}nga primtal.

\vspace{.1in}

\noindent{\sl BEVIS} Antag motsatsen, dvs antag att det finns $k$ stycker primtal: $p_1, p_2,...,p_k$. Bilda talet:
$$ n=p_1p_2...p_k +1$$
Enligt (AFS) \"ar $n$ en produkt att primtal $q_1,...,q_j$ s{\aa}  vihar  att:
$$n=q_1q_2...q_j= p_1p_2...p_k +1$$
Eftersom $q_1|n$ och $q_1,p_1,...,p_k$ \"ar alla primtal   s{\aa} m\aa sta  $q_1|1$. Detta inneb\"ar en mots\"agelse eftersom $q_1>1$.
\vspace{.1in}

 En mycket viktig egenskap hos de positiva tal \"ar den s{\aa} kallade {\it v\"alordningsprincipen} som s\"ager att:

{\it Varje icke-tom delm\"angd av $\zed^+$ har ett minsta element.}

 Det betyder att det finns ett element som \"ar mindre \"an alla andra element i m\"angden. Vi ska visa det lite senare!

Vi beh\"over v\"alordningsprincipen f\"or att visa den s{\aa} kallade {\it divisionsalgoritmen}:

\vspace{.1in}

\noindent {\it EUKLIDESALGORITEN}. L\aa t $a,b$ vara heltal och $b>0$. D{\aa} finns entyga heltal $q,r$ s\aa dan att:
$$ a=bq+r\hspace{1in}0\leq r < b$$
\vspace{.1in}

\noindent{\sl BEVIS}. Satsen \"ar trivial om $a=0$, s{\aa} antag att $a>0$.
Betrakta m\"angden:
$$S=\{a-bt\text{ d\"ar }t\in\zed, a-tb\geq 0\}$$
$S$ \"ar en icke-tom ($a\in S$) delm\"angd av $\zed^+$ och enligt v\"alordningsprincipen har $S$ ett minsta element $r=a-bq$. D{\aa} \"ar $ a=bq+r$ och $0\leq r<b$. Nu ska vi visa att $q,r$ \"ar entydiga. Antag att det finns $Q,R$ {s\aa}dan att $a=bQ+R$, med $0\leq R< b$. D{\aa} \"ar $$a=bq+r= bQ+R\hspace{.2in}\text{ och d\"armed}$$
$$(q-Q)b=R-r$$
Eftersom $R-r<b$ s{\aa} m{\aa}ste $q-Q=0$ och d\"armed $R-r=0$.

\noindent{\it Exempel.} Om $125$ divideras med $12$ har vi att:
$$125=12\cdot 10 + 5$$
\section*{talbasen}
Om man skriver ett tal som 12345 s{\aa} \"ar det f\"orst\aa tt att talet \"ar givet i {\it talbasen} {\bf 10}, dvs 
$$12345=1\cdot 10^4+ 2\cdot 10^3+ 3\cdot 10^2+ 4\cdot 10^1+ 5\cdot 10^0$$

Inom datoromr\aa det anv\"ander man ofta det {\it bin\"ara talsystemet}, d\"ar ett tal skrivas som en sekvens av ``0'' och ``1'', dvs
$$77=1\cdot 2^6+0\cdot 2^5+0\cdot 2^4+1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=10011010$$
Man kan konvertera ett tal fr\aa n  basen $10$ till  basen $2$ med hj\"alp av Euklidens algoritmen:

\[ \begin{array}{lllll}
77&=&2\cdot 38 & + & 1\\
38&=&2\cdot 19 & + & 0\\
19&=&2\cdot 9 & + & 1\\
9&=&2\cdot 4 & + & 1\\
4&=&2\cdot 2 & + & 0\\
2&=&2\cdot 1 & + & 0\\
1&=&2\cdot 0 & + & 1
\end{array}\]
S{\aa} vi har:
$$ 77=2(2\cdot(2\cdot 9 +1))+1=2(2(2(2\cdot 4+1)))+2^2+1=2^6+2^3+2^2+2^0$$


P{\aa} samma s\"att konverterar man ett tal fr\aa n  basen $10$ till en annan bas. Till exempel kan talet $777$   skrivas ``i basen $8$'' som (en sekvens av tal mellan 0 och 7): 
\[ \begin{array}{lllll}
777&=&8\cdot 97 & + & 1\\
97&=&8\cdot 12 & + & 1\\
12&=&8\cdot 1 & + & 4\\
1&=&8\cdot 0& + & 1\\
\end{array}\] 
S{\aa} vi  har $777=8(8(8+4)+1)+1=8^3+4\cdot 8^2+8+8^0=1411$.
\section*{ st\"orsta gemensam delare}
Naturigtvis kan tv{\aa} heltal $a,b$ ha gemensamma delare. Eftersom bara ett \"anligt antal delare \"ar m\"oijlgt s{\aa} det m\aa ste finnas en st\"orsta delare.
\begin{definition}
L\aa t $a,b$ vara heltal, inte b\aa da noll. Det positiva talet $d$ kallas {\it den st\"orsta gemensamma delaren}(sgd) till $a$ och $b$ om:
\begin{enumerate}
\item $d|a$ och $d|b$;
\item om $c|a$ och $c|b$ d{\aa} $c|d$.
\end{enumerate}
\end{definition}
Den $sgd(a,b)$  brukar betecknas ocks{\aa} $(a,b)$.

Man s\"ager att $a,b$ \"ar relativt prima om $sgd(a,b)=1$.

Det kan vara komplicerat att hitta sgd av tv{\aa} st\"ora tal, men det finns ett systematiskt s\"att att hitta sgd tackvare Euklides algoritm.

\vspace{.1in}

\noindent{\it Exampel} Best\"am $sgd(252,111)$.
\[ \begin{array}{lllll}
252&=&111\cdot 2 & + & 30\\
111&=&30\cdot 3 & + & 21\\
30&=&21\cdot 1 & + & 9\\
21&=&9\cdot 2& + & {\bf 3}\\
9&=&3\cdot 3&&
\end{array}\] 
S{\aa}  sgd   \"ar den icke-f\"orsvinnande resten: $sgd(252,111)=3$

Notera att p{\aa} grund av \"ovning (2), om $d|252$ och $d|111$ d{\aa} $d|252-2\cdot 111=30$, d{\aa} $d|111-3\cdot 3=21$, $d|30-21=9$ och $d|3$. Det f\"oljer att $sgd(252,111)=3$.

Notera dessutom att man kan f\"olja algoritm fr\aa n slutet till b\"orjan och f{\aa} $3=21-2(30-21)=3\cdot 21-2\cdot 30=3(111-3\cdot 30)-2\cdot 30=
3\cdot 111-11\cdot(252-2\cdot 111)= 25\cdot 111-11\cdot 252$ s{\aa} att
$$3=25\cdot 111-11\cdot 252$$

Man kan p{\aa} samma s\"att visa att:

\vspace{.1in}

\noindent{\it SATS.} Om $d=(a,b)$ s{\aa} finns tv{\aa} heltal $N$ och $M$ s{\aa} att:
$$d=Na+Mb$$
\section*{diofantiska eknationer}

Alla ni vet att n\"ar man l\"oser en br{\aa}kaddition och vill skriva svaret som ett br\aa k, beh\"over man  r\"akna ut den {\it minsta gemensamma multipel} mellan n\"amnarna. Ofta kallas det {\it lcd} fr{\aa}n det engelska ordet ``list common divisor''. Man Kan ber\"akna $lcm(a,b)$ med hj\"alp av primtal faktoriseringen. Om $a=p_1\cdot...\cdot p_r$ och $b=q_1\cdot ...\cdot q_l$ \"ar
$lcd(a,b)$ ``unionen'' av den. Till exmpel:\\
\noindent $60=2\cdot 2\cdot 3\cdot 5$, $36=2\cdot 2\cdot 3\cdot 3$ s{\aa} \"ar $lcm(60,36)=2\cdot 2\cdot 3\cdot 3\cdot 5=180$
 
\vspace{.1in}

\noindent{\it \"Ovning.} Visa att:
$$lcm(a,b)=\frac{ab}{sgd(a,b)}$$

\vspace{.1in}

\noindent{\it Exempel.} Best\"amm $lcd(4711,777)$.

Med hj\"alp av Euklides algoritm hittar man att $(4711,777)=7$. Eftersom \"ar
$$4711\cdot 777=lcd(4711,777)\cdot sgd(4711,777)$$
har vi att $lcd(4711,777)=522921$.

Vi har sett att man kan skriva $sgd(n,m)$ som en linj\"ara kombination av $n$ och $m$ : $sgd(n,m)=an+bm$, d\"ar $m,n\in\zed$. Till exempel \"ar
$$7=16\cdot 4711-97\cdot 777$$

Finns den ett entydigt s\"att  att g\"ora s{\aa}? Eftersom  $4711\cdot 111=673\cdot 777$  ser man att
$$7=16\cdot 4711-97\cdot 777+k(4711\cdot 111-673\cdot 777)=(16+111k)\cdot 4711-(97+673k)\cdot 777$$
S{\aa} det finns  o\"andligt m{\aa}nga s\"att( ett f\"or varje $k$).

\vspace{.1in}

L\aa t $a,b,c\in\zed$ och $x,y$ vara obekanta heltal. 

Betrackta den {\it diofantiska ekvationen}:
$$ax+by=c$$
Antag att ekvationen \"ar l\"osbar och l{\aa}t $d=sgd(a,b)$. Det f\"oljer att $d|ax+by$ och d\"armed att $d|c$. Antag omv\"ant att $d|c$ s{\aa} att $c=dm$ f\"or n{\aa}got heltal $m$. Eftersom $d=sgd(a,b)$ finns det $M,N\in\zed$ s{\aa}dan att $d=Na+bM$. D{\aa} \"ar $x=M$ och $y=N$  en l\"osning till ekvationen $d=xa+by$ och   $x=mM$, $y=mN$ \"ar en l\"osning till ekvationen $c=md=xa+by$.
Vi har visat att:

\vspace{.1in}

\noindent{\it SATS}. Ekvationen $ax+by=c$ \"ar l\"osbar om och endast om $(a,b)|c$.

\vspace{.1in}

Detta ger en algoritm f\"or att l\"osa ekvationen $ax+by=c$:
\begin{itemize}
\item best\"am $d=(a,b)$
\item om $c\not | (a,b)$ d{\aa} \"ar ekvationen ej-l\"osbar;
\item om $c=md$ l{\aa}t $h=lcm(a,b)$ d\"ar $h=Aa=Bb$. Hitta heltal $N,M$ s\aa dan att $d=Na+Mb$. Den allm\"anna l\"osning \"ar $x=mN+kA,y=mM-kB$.
\end{itemize}

\vspace{.1in}

\noindent{\it Exempel} Vid en idrottst\"avling kostade biljetter 175 SEK f\"or vuxna och 145 f\"or barn. De totala int\"akterna var 10000 kronor. Hur m{\aa}nga barn k\"opte biljett?

Antag att det kom $x$ barn och $y$ vuxna, dvs:
$175y+145x=10000$. H\"ar \"ar $sgd(145,175)=5$ och $5|10000$. Observera att man kan dela hela ekvationen med $5$:
$$ 29x+35y=2000\hspace{.4in}\text{ d{\aa}  \"ar }(29,35)=1$$
P{\aa} grund av Euklides algoritm har vi:
\[ \begin{array}{lllll}
35&=&29\cdot 1& + & 6\\
29&=&4\cdot 6 & +& 5\\
6&=&5\cdot 1 & + & 1\\
\end{array}\] 
och $1=6-5=6-29+4\cdot 6=5\cdot 6-29=5(35-29)-29=5\cdot 35-6\cdot 29$.
Eftersom  $x=-6,y=5$ \"ar en l\"osning till $29x+35y=1$ s{\aa} \"ar  $x=-12000,y=10000$ en l\"osning till $29x+35y=2000$. Eftersom $lcm(29,35)=29\cdot 35$ blir  den alm\"anna l\"osningen:  
$$ x=-12000+35k \hspace{.3in} y=10000-29k$$
 
Klart att vi  ska kr\"ava att $x=-12000+35k\geq 0$ och $y=10000-29k\geq 0$. Det f\"oljer att $343\leq k\leq 344$. Svaret \"ar:
\begin{itemize}
\item $-1200+35\cdot 343=5$ barn eller
\item $-1200+35\cdot 344= 40$ barn.
\end{itemize} 

\end{document}