%% Omia määrityksiä:

\newcommand{\R}{{\mathbb R}}
\def\maple{{\sc Maple}}
\def\Maple{{\sc Maple}}
\def\m{{\sc Maple}}
\def\maplea{{\sc Maple}a}
\def\matl{{\sc Matlab}}
\def\matlab{{\sc Matlab}}
\def\mlb{{\sc Matlab}}
\def\oct{{\sc Octave}}
\def\octave{{\sc Octave}}
\def\scilab{{\sc Scilab}}
\def\emacs{{\sc Emacs}}
\def\notepad{{\sc Notepad}}
\def\wordpad {{\sc Wordpad}}
\def\RSA {{\sc RSA}}
\def\syt {\text{syt}}
\def\esm {\textbf{Esim:}}
\def\Mod{\text{mod}}
 
\renewcommand{\proofname}{Tod}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}

\newtheorem{lause}{Lause}
\newtheorem{seur}[lause]{Seuraus}
\newtheorem{lemma}[lause]{Lemma}
\newtheorem{maarit}{M\"a\"aritelm\"a}


\newtheorem{esim}{Esimerkki} 
\newtheorem{huom}{Huomautus}
\newtheorem{teht}{Teht\"av\"a}

\includegraphics*{nauhakone.eps}
\artikkeli{Lukuteoriaa ja salakirjoitusta, osa 1}

\kirjoittanut{\textbf{\emph{Heikki Apiola}}\\
Dosentti\\
Matematiikan laitos, Teknillinen korkeakoulu}
 
\vspace{0.2cm}
 
\begin{multicols}{2}




\subsection*{Johdanto}

%[R] s. 801: 
Lukuteoriaa on joskus pidetty esteettisesti kauniina, mutta 
käytännössä aika hyödyttömänä matematiikan alana. Kukaan ei asettane
nykyäänkään tuota esteettistä puolta kyseenalaiseksi, mutta miten on
sen käytännön hyödyn laita?

Nykyinen sähköiseen tiedonvälitykseen perustuva
asioiden hoitaminen ei olisi mahdollista ilman tehokkaita salausmenetelmiä. Niiden kehittämisessä puolestaan on ollut ratkaisevan tärkeä 
osa juuri tuolla lukuteorian tarjoamalla ``hyödyttömällä'' 
estetiikalla.
%joiden kehittämiseen puolestaan vaikuttivat aikanaan ennen kaikkea sotilaalliset päämäärät.  (Toinen maailmansota ..., varhaishistoria)

%Entä se lukuteoria? 
Tässä kirjoituksessa esitetään lukuteorian perusasiat,
joita tarvitaan osassa 2 esiteltävän ns. julkisen \RSA-salakirjoitusmenetelmän
johtamiseen, päteväksi osoittamiseen ja ohjelmoimiseen.
%Esitän asiat yksityiskohtia myöten, 

Lukuteoria on sikäli poikkeava matematiikan ala, että siitä voi 
kirjoittaa lukijalle, jolla on minimaaliset perustiedot matematiikassa.
Itse asiassa tarvitaan vain ymmärrys kokonaislukujen 
perusominaisuuksista ja laskutoimituksista niillä. Näillä eväillä 
päästään aika nopeasti kiinnostaviin tuloksiin ja sovelluksiin käsiksi.

Kirjoitus toimii testinä yllä olevalle väitteelle.
Toki on hyödyksi, jos lukijalla on oheislukemistona vaikkapa 
lukion lukuteorian syventävän kurssin 11 oppikirja, kuten 
[Lukio1] tai [Lukio2].

Kirjoitus ei ole lukuteorian alkeiden oppikirjan osa, keskityn
välttämättömän (ja toivottavasti riittävän) osuuden esittelyyn
päämääränä yllä mainitun julkisen salakirjoituksen 
\RSA-salakirjoitusalgoritmina tunnetun menetelmän ymmärtäminen.
Esitän asiat perusteellisesti, niin että yksityiskohtienkin
ymmärtäminen olisi mahdollista. Jotta kirjoitus ei paisuisi liian 
laajaksi, esitän sen kahdessa osassa. Tässä ensimmäisessä keskityn
lukuteorian perusteisiin ja toisessa tuohon salakirjoitussovellukseen.


%Periaatteessa 
%en edellytä esitietoja alalta, määrittelen kaikki tarvittavat käsitteet.  
%Silti lukijan, jolle jaollisuusopin peruskäsitteet, kuten 
%jakoyhtälö, alkuluvut, syt (suurin yhteinen tekijä) ym. ovat aivan uusia,
%kannattaa oheislukemistona pitää lukuteorian syventävän kurssin oppikirjaa 
%harjoitustehtävineen (aktiivisesti) esillä.


%\subsection*{Jaollisuus, tekijät, alkuluvut}
\subsection*{Kokonaisluvut, jaollisuus }

\textbf{Merkintöjä:}
Käytän joukko-opin ja logiikan standardimerkintöjä:
\begin{description}
\item
$ x\in A$ tarkoittaa: $x$ kuuluu joukkoon $A$, eli $x$ on $A$:n alkio.
\item
Kokonaisluvut: $\Z = \lbrace 0,\pm 1, \pm 2, \pm 3 \ldots \rbrace$ \\
\item
Luonnolliset luvut: $\N = \lbrace 0,1,2,3,\ldots \rbrace$ 
\end{description}
%(Ikuinen kiistan aihe: Alkavatko luonnolliset luvut $0$:sta vai $1$:stä ?
%Tässä nyt sovimme ranskalaiseen tyyliin. Tiedossani ei ole, mitä asiasta 
%ajattelee \emph{Angela Merkel} tai \emph{Gordon Brown}.)

Käsittelemme pelkästään kokonaislukuja, usein viittaamme kokonaislukuun lyhyesti sanalla \emph{luku}. %Ryhdymme heti soveltamaan tätä käytäntöä:

\textbf{Pienin ja suurin luku}

Kokonaislukujen osajoukoilla on ominaisuus, jota ei ole rationaali- eikä reaaliluvuilla. Kyseessä on mahdollisuus valita osajoukosta pienin ja suurin luku.

\textbf{Luonnollisten lukujen minimiominaisuus}: 
\emph{Jokaisessa $\N$:n epätyhjässä osajoukossa on \textbf{pienin luku}}.

Tästä seuraa:

\textbf{Kokonaislukujen minimi- ja maksimiominaisuus}:
\emph{Jokaisessa $\Z$:n \textbf{ylhäältä rajoitetussa} epätyhjässä 
osajoukossa on \textbf{suurin} luku ja \textbf{alhaalta rajoitetussa}
on \textbf{pienin} luku}

\subsubsection*{Jakoyhtälö}

Jos vaikkapa luku $a=55$ jaetaan luvulla $b=8$ kokonaislukujakona, saadaan
osamäärä $q=6$ ja jakojäännös $r=7$, sillä $55=6\cdot 8 + 7.$
Osamäärä $q$ löydetään hakemalla suurin luku $q$, jolle $q\cdot 8 \leq 55$, jakojäännös on se, mitä jää yli. Jakojäännös $r$ on jakajaa ($b=8$) pienempi,
muutenhan osamäärä $q=6$ ei olisikaan suurin mahdollinen. 

Yllä oleva esimerkki noudattaa sitä periaatetta, jolla olemme oppineet 
jakolaskun suorittamaan jo peruskoulussa. Sama periaate voidaan kirjoittaa
yleisesti pelkillä kirjainsymboleilla:

\begin{lause}
Olkoot $a$ ja $b$ luonnollisia lukuja, $a>0$. Tällöin on olemassa yksikäsitteiset $q$ ja $r$, $0 \leq r < b$ siten, että $a = q\, b + r$
\end{lause}
\begin{proof}
Toistamme siis vain yllä esimerkissä esitetyn juonen.
Voidaan olettaa, että $a > b$, muutenhan voidaan ottaa $q=0, r=a$.\\
No, ei muuta kuin valitaan maksimiominaisuuden perusteella suurin luku 
$q$ niin, että
$q\,b \leq a$. 
(Epäyhtälön $p\,b \leq a$ toteuttavia lukuja $p$ varmasti on, ainakin $p=0$, ja
$p=1$, joten puheena on epätyhjä joukko. Lisäksi kaikki tällaiset luvut $p$ toteuttavat varmasti epäyhtälön 
$p \leq a$, joten niiden joukko on ylhäältä rajoitettu.)

Merkitään $r$:llä erotusta $r=a - b\,q,$ jolloin $r\geq 0.$ Jos olisi $r\geq b,$ niin voitaisiin kirjoittaa $r=b+c,$ missä $c \geq 0.$ \\
Tällöin olisi
$a=q\,b + b + c = (q+1)\, b + c$, joten $q$ ei olisikaan yllä olevan joukon suurin luku.

Yksikäsitteisyys: Olkoon kaksi esitystä: $a=q_1\,b + r_1,$ ja 
$a=q_2\,b + r_2,$ missä $0 \leq r_i < b,\ \ i=1,2.$
\\
Tällöin $|r_2 - r_1| < b,$ joten $|q_1 - q_2| \, b < b.$\\ 
Koska $b >0,$
sillä voidaan jakaa ja saadaan $|q_1 - q_2|  < 1.$ Kokonaisluvuille 
tämä on mahdollista vain siten, että $q_1 = q_2.$ Siitäpä heti seuraa,
että myös $r_1 = r_2$.
\end{proof}

%\textbf{Merkintä ($a$ mod  $b$)}. Kokonaislukujakolaskun $a/b$ jakojäännöstä $r$ merkitään:
%$r = a \mod b$ (Lausutaan: $a$ modulo $b$). Osamäärälle $q$ on myös erilaisia merkintöjä,
%mutta lukuteoriassa on usein jakojäännös mielenkiintoisempi kuin osamäärä, niin ainakin 
%tässä esitettävässä osuudessa.


\begin{maarit}[Jaollisuus]
Luku $a$ on jaollinen luvulla $b$, jos on olemassa luku $n$ siten, että 
$a=n\, b$. Tällöin sanotaan, että $b$ on $a$:n \textbf{tekijä} ja 
$a$ on $b$:n \textbf{monikerta}. Merkitään: $b\, |\, a,$ joka voidaan 
lukea: "$b$ on tekijänä $a$:ssa"\/ tai "$b$ jakaa $a$:n"  
\end{maarit}

\begin{huom}
Jos $b\,|\,a,$ niin $-b\,|\,a$. Jokaisella luvulla $a$ on triviaalit tekijät 
$\pm 1$ ja $\pm a$. \\
Luku $0$ on jaollinen kaikilla luvuilla $b$, koska $0 = 0\cdot b$, toisaalta
$0$ on tekijänä $0$:ssa, mutta ei missään luvussa $a \ne 0.$ 
\end{huom}



%\begin{huom}
%Jos $b\,|\,a,$ niin $-b\,|\,a$. Jokaisella luvulla $a$ on triviaalit tekijät 
%$\pm 1$ ja $\pm a$. \\
%Luku $0$ on jaollinen kaikilla luvuilla $n$, koska $0 = 0\cdot n$, toisaalta
%$0$ ei ole tekijänä missään luvussa $a \ne 0.$ Nolla on tekijänä $0$:ssa, eli
%$0$ on jaollinen $0:$lla. (Koulussa opetetaan, että nollalla ei saa jakaa,
%mutta jaollisuusselvitys ei edellytäkään jakamista. 
%Jakolaskun $\frac{0}{0}$ tulokseta ei kannata puhua, sillä se 
%on mitä tahansa, koska $0\cdot q = 0,$ olipa $q$ mikä tahansa luku.)
%\end{huom}


\begin{esim} Jaollisuusesimerkkejä \\
1) $7\, |\, 56$, \quad $-3 \, | \, 12 .$ \\
2) Luvun $12$ ei-triviaalit tekijät: $\pm 2,\pm 3, \pm 4, \pm 6$\\
3) Luvulla $6$ jaollisten lukujen joukko:\\ $\lbrace n\cdot 6 | n\in \Z\rbrace=
\lbrace 0, \pm 6, \pm 12, \pm 18 \ldots \rbrace$
\end{esim}

Kootaanpa yhteen yleiset jaollisuuden perusominaisuudet.

\begin{lause}\label{jaollper} Yleiset jaollisuusominaisuudet\\
1) Jos $x \,| \, a$ ja $x \,| \, b$, niin $x \,|\, (a \pm b)$\\
Yleisemmin:\\
1') Jos $x \,| \, a$ ja $x \,| \, b$, niin $x \,|\, (a\,m + b\,n)$ mielivaltaisille (kokonais)luvuille $m,\ \ n$\\
2) Jos $x \,| \, a$ tai $x \,| \, b$, niin $x \,|\, (a\,b)$\\
3) Jos $a\,|\, b,\ \ b\neq 0$, niin $| a | \leq |b|$,\\
\end{lause}
\begin{proof}
Todistetaan malliksi kohta 1). Yleistys 1') on aivan vastaavanlainen. Kohdat
2) ja 3) ovat suorastaan itsestäänselvyyksiä. Mieti kuitenkin.
\\
Kohta 1): 
Oletuksen mukaan on olemassa (kokonais)luvut $s$ ja $t$ siten, että 
$a=s\,x$ ja $b=t\,x.$ Niinpä \\ 
$a+b = s\,x + t\, x = \underbrace{(s + t)}_{\in \Z}x,$ joten $x\,|\,(a+b).$

\end{proof}

Kannattaa huomata, että käänteinen suunta kohdalle 2) ei päde yleisesti.

\esm\/ $12 = 3\cdot 4$. Luku $6$ on tekijänä luvussa $12$, mutta $6$ ei ole tekijänä
kummassakaan tulontekijässä $3$ tai $4$. 

No, kysehän on siitä, että $6:$lla on yhteinen tekijä sekä $3:$n että
 $4:$n kanssa. Tähän tärkeään havaintoon palataan, ja muotoillaan 
lisäehto, jolla käänteinen johtopäätös on voimassa.

Kun puhutaan positiivisten kokonaislukujen $a$ jaollisuudesta, voidaan
rajoittua puhumaan positiivisista tekijöistä $b$, 
sillä jos $b$ on tekijä, niin $-b$ on aina myös tekijä, joten sen 
mainitseminen erikseen on turhaa sanahelinää. 
(Matemaatikon hyveisiin kuuluu sanojen säästäminen.)



\subsection*{Alkuluvut}

\begin{maarit}
Kokonaisluku $a > 1$ on \textbf{alkuluku}, jos se on jaollinen vain $1$:llä 
ja itsellään. Muuten puhutaan \textbf{yhdistetystä luvusta}.
\end{maarit}

Jokainen luku $a$ on jaollinen myös $-1:$llä ja $-a:$lla.
Noudatamme edellä mainittua ``turhan sanahelinän välttämisperiaatetta `` 
ja pitäydymme positiivisissa tekijöissä.


Alkulukujen alkupää näyttää tältä: $2,3,5,7,11,13,17 $.
Yksinkertainen algoritmi alkulukujen laskemiseen on jo antiikin Kreikassa 
tunnettu \emph{Eratostheneen seula}. Lukujoukosta $1,\ldots,n$ seulotaan
pois kaikki yhdistetyt luvut poistamalla ensin $2$:n monikerrat (parilliset luvut), sitten $3$:n monikerrat (3:lla jaolliset luvut), jne.  Kts. [Lukio1]

Symbolilaskentaohjelmissa on valmiita alkulukualgoritmeja ohjelmoituna. 
\maple:lla voitaisiin $100$ ensimmäistä alkulukua laskea näin:
\begin{verbatim}
>     N := [$(2 .. 100)]
[2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14 ... 
  ...   99, 100]
>     map(ithprime, N)
[3, 5, 7, 11, 13, 17, 19,23,29,31,37,41,43 ..
  ...   523, 541]
\end{verbatim}

%\begin{verbatim}
%onalkuluku(n)
%if n<2 then return("Älä kysele tyhmiä!")
%if n=2 tai n=3 then return(1)
%for k:=2 .. nsqrt(n) // nsqrt tarkoittakoon ...
%  if (k | n)        // neliöjuuren kokonaisosaa
%    then return(0)
%  endif
%endfor 
%return(1)
%end

%Alkuluvut(n)
%tulos:=[2]
%for k:=1 .. n
%  if onalkuluku(k) 
%     then tulos:=[tulos,k]
%  endif
%endfor
%return(tulos)
%end
%\end{verbatim}

%Algoritmi on kirjoitettu "pseudokielellä", josta sen voi muokata itse kunkin käytössä olevalle oikealle ohjelmointikielelle.
%Menetelmä on hyvin tehoton ja ylläoleva implementointi vielä korostaa tehottomuutta. Kyseessä on vain pikainen ja mahdollisimman helposti ymmärrettävä toteutus.


\emph{Eratostheneen seula} on helppo ymmärtää ja ohjelmoida, mutta se on
varsin tehoton.
Tehokkaiden alkulukualgoritmien kehittely on tärkeä osa mm. kryptologista 
(salakirjoitusmenetelmiin liittyvää) tutkimusta.

%Sellaiset ovat myös oivallisia "hakkerien"\/ tai "krakkerien"\/ apuvälineitä.


\begin{lause}[Alkulukuhajotelma]\label{alkulukuhajotelma}
Jokainen luonnollinen luku $a > 1$ voidaan esittää alkulukujen tulona.
\end{lause}
\begin{proof}
Jos $a$ on alkuluku, se on (yksiterminen) alkulukutulo. Jos taas $a$ on yhdistetty luku, se on muotoa $a=a_1\,a_2, \ \ a_i>1, i=1,2.$ Jos kumpikin on alkuluku, olemme perillä.
Ellei, niin ainakin toinen on yhdistetty luku. Esitetään kaikki (toinen tai molemmat) tekijät kahden luvun tulona. Näin jatketaan, kunnes päädytään tuloon,
jonka mitään tekijää ei voida jakaa. Tämä tapahtuu viimeistään $\log_2(a)$ askeleen jälkeen, koska yhdistetyn luvun kumpikin tekijä $\geq 2$.
\end{proof}



Tuntuisi uskomattomalta, jos alkuluvut loppuisivat jostain alkaen, ts. niitä
olisi vain äärellinen määrä. \emph{Eukleides} todisti jo 
v. 300 eKr. kirjassaan Elementa (Kirja IX, propositio 20), että niitä 
todella on äärettömän paljon. Tämä $2300$ vuotta vanha todistus on 
edelleenkin voimissaan. Näin se menee:

\begin{lause}[Eukleides]\label{Aarettomastialkulukuja} Alkulukuja on ääretön määrä.
\end{lause}
\begin{proof}
Olkoon $p$ mielivaltainen alkuluku. Osoitetaan, että on olemassa sitä suurempi 
alkuluku. Tällöinhän äärellinen alkulukujen määrä johtaisi heti ristiriitaan.

Olkoot $p_1,p_2,\ldots,p_n=p$ kaikki alkuluvut, jotka ovat $\leq p$.
Olkoon $P=(p_1\cdot p_2\cdot \ldots \cdot p_n)+1.$
Jos $P$ jaetaan millä tahansa luvuista $p_j, j=1,\ldots,n$, niin jakojäännös $=1$ (ajattele $P:n$ kaavaa jakoyhtälönä). Jako ei siis mene tasan, eli mikään 
$p:$tä pienempi alkuluku ei ole tekijänä $P:$ssä. Mutta 
alkulukuhajotelmalauseen \ref{alkulukuhajotelma} mukaan $P:$llä on tekijänä
alkuluku ($P$ itse, jos se sattuu olemaan alkuluku).
Tämä tekijä ei ole mikään $p:$tä pienempi tai sen suuruinen (alku)luku, 
joten sen on oltava $p:$tä suurempi.
\end{proof}

Myöhemmin on esitetty monia muitakin todistuksia, kts. esim.\\
\verb+http://en.wikipedia.org/wiki/Prime_numbers+


%\subsection*{Lukuteorian perusteita}

%\subsubsection*{Jaollisuusoppia, "kelloaritmetiikkaa"}

%\subsection*{Suurin yhteinen tekijä, Eukleideen algoritmi}
\subsection*{Suurin yhteinen tekijä}

Lukujen $a$ ja $b$ \textbf{suurin yhteinen tekijä}, $\syt(a,b)$ on nimensä 
mukaisesti suurin luku $s$, joka on tekijänä sekä $a$:ssa että $b$:ssä.\\
Esimerkiksi $\syt(24,30)=6, \ \ \syt(5,7)=1.$ Systemaattinen tapa $\syt(a,b)$:n
määräämiseksi on muodostaa alkulukuhajotelmat ja poimia kummastakin yhteiset 
alkutekijät. Edellisessä esimerkissä: $24=2\cdot 2\cdot 2\cdot 3$,
$30=2\cdot 3 \cdot 5.$ Yksi kakkonen ja yksi kolmonen voidaan poimia kummastakin, eikä mitään muuta, joten todellakin saadaan $6$.
\\
Tehokkaampi menetelmä on ns. \emph{Eukleideen algoritmi}, joka esitellään kohta. \\
Sitä ennen johdetaan suurimmalle yhteiselle tekijälle kaava, josta saadaan kätevästi koko joukko ominaisuuksia. Sitä voidaan pitää tämän kirjoituksen yhtenä
tärkeimpänä työkaluna.




\begin{lause}[SYTlause]\label{sytlause}
Olkoot $a$ ja $b$ positiivisia kokonaislukuja.
%, joista ainakin toinen $\neq 0.$
%*** (Ehkä oletetaan $a >0, b>0$) *** \\
$$\syt(a,b) = \text{min} \{ s > 0 | s=a\,x + b\,y , \ \ x,y \in \Z \}$$
\end{lause}
\begin{proof}
Oikealla puolella oleva joukko koostuu positiivisista kokonaisluvuista.
Luonnollisten lukujen minimiominaisuuden mukaan tässä joukossa on
pienin luku

$$s_0 = a\,x_0 + b\, y_0,$$

missä $x_0$ ja $y_0$ ovat sellaiset kokonaisluvut, joilla tuo minimi 
saavutetaan. 

Todistuksen juoni on osoittaa, että 
$$\begin{cases}
(1) \ \ \syt(a,b) \leq s_0,  \\
(2) \ \ \syt(a,b) \geq s_0.
\end{cases}$$


Epäyhtälö $(1):$ Koska $\syt(a,b)$ on tekijänä sekä $a$:ssa että $b$:ssä, 
niin se on tekijänä
jokaisessa muotoa $a\,x + b\,y$ olevassa lausekkeessa, siis myös $s_0:$ssa.
Niinpä on oltava $\syt(a,b) \leq s_0$.

Epäyhtälö $(2):$ Jos onnistumme osoittamaan, että $s_0\, |\, a$ ja 
$s_0\, |\, b$,
niin tiedämme, että $s_0$ on $a:$n ja $b:$n yhteinen tekijä ja siten 
pienempi tai yhtäsuuri kuin suurin yhteinen tekijä $\syt(a,b)$.


Aloitetaan $a:$sta. Jakoyhtälön mukaan $a=q\,s_0 + r,$ missä 
$0 \leq r < s_0$, Osoitetaan, että $r=0,$ jolloin väitteemme on $a:$n osalta
todistettu.

Kirjoitetaan $r=a-q\,s_0 = a-q(a\,x_0 + b\,y_0) = a(1-q\,x_0) + b(-q\,y_0).$

Siis $r$ on "muotoa $s_0$". Lisäksi $0 \leq r < s_0.$ Koska $s_0$ on pienin 
positiivinen tuota muotoa oleva luku, on oltava $r=0.$  Siten $a=q\,s_0,$ 
ts. $s_0\, |\, a.$ 

Aivan samoin voimme menetellä $b$:n suhteen, ja päätellä, että  $s_0\, |\, b.$
(Suoritapa tämä lasku ja päättely!)
Siispä $s_0$ on $a:$n ja $b:$n yhteinen tekijä, ja niin ollen
$s_0 \leq \syt(a,b).$ 

Niin olemme todistaneet epäyhtälöt $(1)$ ja $(2),$ joten todellakin 
$\syt(a,b) = s_0$.

\end{proof}

Ennenkuin ryhdymme nautiskelemaan tämän lauseen seurauksista, otamme käyttöön
merkinnän ja nimityksen:\\
\textbf{Keskenään jaottomat luvut:} Luvut $a$ ja $b$ ovat keskenään jaottomat,
jos $\syt(a,b)=1.$ Käytämme myös sanontaa \emph{yhteistekijättömät} ja puhetapaa: " $a:$lla ja $b:$llä ei ole yhteisiä tekijöitä"\/ 
tarkoittaen: ei \emph{yhteisiä epätriviaaleja tekijöitä}. 

%Otan käyttöön omavaltaisesti merkinnän, jota en ole nähnyt kirjallisuudessa käytettävän: 
%$$a \perp b \ \ \text{tarkoittakoon, että}\ \ \syt(a,b)=1.$$
%Tietyissä tilanteissa on hyödyllistä ajatella tätä vektorilaskennan kohtisuoruutta vastaavana ehtona.

Aloitetaan edellä luvatulla käänteisellä puolella tulon jaollisuusominaisuuteen
(Lause ~\ref{jaollper})

%Tästä saamme koko joukon seurauksia. Jotkut tuntuvat miltei 
%itsestäänselvyyksiltä ja voidaankin perustella vaikkapa alkulukuhajotelman
%avulla. Lauseemme antaa helpon ja suoraviivaisen tavan.
\begin{lause}\label{modsupistusok}
Oletetaan, että $\syt(a,n)=1$. 
Jos $n\, |\, a\, b,$ niin $n\, |\, b$ 
\end{lause}
\begin{proof}
Koska $\syt(a,n)=1,$ on $1 = x_1\, a + y_1\,b$ joillakin kokonaisluvuilla $x_1$
ja $y_1$ (SYTlause (Lause ~\ref{sytlause})). Kun tämä kerrotaan puolittain $b:$llä, saadaan

$$b = x_1\,a\,b + y_1\,b\,n.$$

Koska $n\, |\, a\,b,$ on $a\,b = k\,n$ jollain $k\in \Z.$ Kun yllä $b:$n lausekkeessa
sijoitetaan $a\, b:$n paikalle $k\, n,$ saadan:

$$b=x_1\,k\,n + y_1\,b\,n = n\underbrace{(x_1\, k + y_1\, b)}_{\in \Z}.$$

Siispä todellakin $n$ on tekijänä $b:$ ssä.
\end{proof}
Erityisesti saadaan nyt:
\begin{seur}\label{modsupistus2}
Olkoon $p$ alkuluku ja $a$ ja $b$ mielivaltaisia kokonaislukuja.
Jos $p$ on tekijänä tulossa $a\,b$, niin $p$ on tekijänä $a:$ssa tai
$p$ on tekijänä $b:$ssä. Loogisena lauseena ilmaistuna:
$$p\ \ \text{alkuluku}, \ \ p\, | a\,b \implies p\, |\, a \vee p\, |\, b.$$
\end{seur}
\begin{proof}
Oletetaan siis, että $p$ on tekijänä $a\, b:$ssä. Jos $p$ ei ole tekijänä 
$a:$ssa, niin $\syt(p,a)=1,$ koska $p$ on alkuluku. Edellisen mukaan $p:$n 
täytyy siten olla tekijänä $b:$ssä.
\end{proof}

\begin{teht}
Osoita esimerkillä, että edellinen ei päde yleisesti, jos $p$ ei ole alkuluku.
%Vihje: Valitse jokin yhdistetty luku $p$ ja muodosta tekijät $a$ ja 
%$b$ vaikka alkulukuhajotelmina.  
\end{teht}

%\begin{huom}
%Edellä oletus:  \textbf{$p$ on alkuluku} on oleellinen. \\
%\end{huom}




%\begin{huom}
%Yllä oleva voitaisiin päätellä myös alkulukuhajoitelman avulla tähän tapaan:
%\end{huom}
%Olkoot $a$:n ja $b$:n alkulukuhajoitelmat:\\ $a=a_1^{p_1}\, a_2^{p_2} \cdots a_k^{p_k}$ ja
%$b=b_1^{q_1}\, b_2^{q_2} \cdots b_l^{q_l}$, missä siis kukin $a_i$ ja $b_j$ on
%alkuluku. Nyt
%$$c=a\, b = a_1^{p_1}\, a_2^{p_2} \cdots a_k^{p_k}\,b_1^{q_1}\, b_2^{q_2} \cdots b_l^{q_l}. $$
%Olkoon $p$ alkuluku, joka on tekijänä tulossa\\ $c=a\, b.$ 
%Koska $c$:n kaikki alkulukutekijät ovat joukossa $\lbrace a_1,\ldots,a_k,b_1,\ldots b_l \rbrace$, niin $p$:n on oltava jokin näistä luvuista, siis jokin $a_i$
%tai jokin $b_j$ ja niin ollen $a$:n tai $b$:n tekijä.

\subsubsection*{Eukleideen algoritmi}

Kyseessä on menettely, jolla voidaan rekursiivisesti määrittää $\syt(a,b)$ 
annetuille kokonaisluvuille $a$ ja $b$ . 
Se on peräisin samasta Elementa-teoksesta n. 300 v. eKr kuin 
lause \ref{Aarettomastialkulukuja}.



Algoritmi pohjautuu havainnolle:

\begin{lause}\label{Euklalgo}
Olkoot $a$ ja $b$ luonnollisia lukuja, $a > b$. Jos $r$ on jakojäännös 
jakolaskussa $a/b,$ niin $\syt(a,b) = \syt(b,r)$.
\end{lause}
\begin{proof}
Kirjoitetaan jakoyhtälön mukaan $a=q\,b + r.$
Jos $s$ on $a:$n ja $b:$n yhteinen tekijä, niin $s$ on tekijänä 
$r:$ssä, koska $r=a-q\,b$ (Lause \ref{jaollper}, kohta 1). Siispä $s$ on $b$:n ja $r$:n yhteinen 
tekijä. Kääntäen, jos $s$ on $b$:n ja $r$:n yhteinen tekijä, niin se on 
$a$:n  tekijä, koska $a=q\,b + r.$\\
Kaikki yhteiset tekijät ovat samat, joten erityisesti suurin yhteinen tekijä 
on sama.
\end{proof}

\begin{esim}
Määrättävä $\syt(576,168).$ \\
$576=3\cdot 168 + 72.$ \\ 
Lause \ref{Euklalgo}:  $\syt(576,168)=\syt(168,72).$\\
Jakoyhtälö: $168 = 2\cdot 72 + 24.$ \\
Lause \ref{Euklalgo}: $\syt(168,72) = \syt(72,24).$ \\ 
Jakoyhtälö: $72 = 3 \cdot 24 + 0.$\\
Lause \ref{Euklalgo}: $\syt(72,24)= \syt(24,0)=24$. \\ 
Alkuperäisen tehtävän ratkaisu: $\syt(576,168)= 24.$
\end{esim}

% on varmasti kaikkien rekuriivisten algoritmien
%äiti. 
Kirjoitetaan algoritmi rekursiiviseksi (itseään kutsuvaksi) ohjelmaksi symbolilaskentaohjelman 
\maple\/ ohjelmointikielellä. Kyseessä on varmasti kaikkien rekursiivisten algoritmien äiti! \\
(Solmukirjoitus Maplen-käytöstä:\\
\verb_http://solmu.math.helsinki.fi/1999/5/apiola/_, rekursiota käsitellään kirjoituksessa:\\
\verb_ http://solmu.math.helsinki.fi/1998/2/seppanen/._  Eräs kuulemani tietosanakirjamääritelmä: \emph{Rekursio, kts. rekursio})



\begin{verbatim}
   Eukleides := proc (a, b) 
   print(a, b); # seurantaa varten  
   if b = 0 then a else 
     Eukleides(b, a mod b) end if 
     # a mod b on jakojäännös.
   end proc:
\end{verbatim}
Suoritetaan esimerkkiajo vaikkapa määrittämällä $\syt(145,75).$ Oikean sarakkeen $b$ siirtyy
seuraavalla rivillä vasemmalle jakajaksi ja saman rivin oikean puolen luku on vastaava 
jakojäännös.% Toisella rivillä oleva \texttt{print-}käsky on vain ohjelman kulun seuraamiseksi.
\begin{verbatim}
  > Eukleides(145, 75)
              145, 75     
               75, 70   ( 145 = 1x75 + 70 )
                70, 5   (  75 = 1x70 + 5  ) 
                5, 0    (  70 = 14x5 + 0 )
                  5     ( syt(5,0) = 5 )
\end{verbatim}
Siis $\syt(145,75)=5$ .


\subsection*{Aritmetiikkaa jakojäännöksillä}

%Edellä otettiin jakojäännökselle jakolaskussa $a/n$ käyttöön merkintä $r=a \mod  n$.

Meihin on "sisäänrakennettu"\/ laskenta jakojäännöksillä erityisesti tapauksissa $n=12$
ja $24$.
Jokainen tietää, että kellonajat $5$ (i.p.) ja $17$ tarkoittavat samaa, ja jos yöjuna 
lähtee klo $20$ ja on perillä klo $9$, niin matkaan on kulunut aikaa $13$ tuntia.
Matemaattisesti nämä voidaan ilmaista kaavoilla:

$$ 5 \equiv 17 \ \ (\Mod\ \ 12) \ \ \text{ja} \ \ 20 + 13 \equiv 9\ \ (\Mod\ \ 24) $$
%Myös $n=7$

Yleisesti määritellään käsite \emph{kongruenssi modulo n}:\\
\begin{maarit}
Olkoon $n>1$. Luvut $a$ ja $b$ ovat \textbf{kongruentteja modulo n}, jos $n\,|\,(a-b).$
Tällöin merkitään
$$ a \equiv b\ \ \Mod\ \ n.$$
\end{maarit}

% Wharfdale diamond 9.1  195 e/pari, pähkinäpuinen , antennikaapeli
 
Määritelmä tarkoittaa sitä, että $a$ ja $b$ saadaan toisistaan lisäämällä sopiva 
"modulin"\/ $n$ monikerta: $a - b = k\, n$ jollain kokonaisluvulla $k$. Tämä merkitsee,
että jakolaskuissa $a/n$ ja $b/n$ on sama jakojäännös.

\begin{teht} Jos tänään on maanantai, niin mikä viikonpäivä on $100:$n päivän kuluttua? \\
Ratkaisu: Numeroidaan viikonpäivät $0,\ldots,6$ antaen arvo $0$ vaikka sunnuntaille.
Tehtävänä on selvittää jakojäännös jakolaskussa $100/7.$ Jakoyhtälö on\\ 
$100 = 7\cdot 14 + 2.$ Kun siis kierrämme ``viikkokellotaulua'' $14$ kertaa ($=98$ päivää), tulemme samaan, mistä lähdimme, mennään vielä kahdella yli, joten päivä on $1+2=3,$ 
eli keskiviikko.
\end{teht}
Voidaan ajatella, että $1+100$:sta vähennetään sellainen $7:$n monikerta, että päästään
välille $0,\cdots,6$. Sanonta: 
\emph{Redusoidaan luku $101$ modulo 7}. Tämä juhlalliselta kalskahtava sanonta 
tarkoittaa siis arkikielellä vain sitä, että määritämme jakojäännöksen 
jakolaskussa $101/7.$ Kaiken aikaa vaan siis pyörittelemme samaa jakoyhtälöä.

\subsubsection*{Modulaariaritmetiikkaa}

Havainnollisesti ajatellen modulaariaritmetiikka, eli "jakojäännöslaskenta"\/ voidaan
ajatella niin, että lukusuoran sijasta kuljetaan pitkin ympyrän kehää. Kellotaulu 
on tästä havainnollinen esimerkki, siinä jakovälejä on $12$ ja kyseessä siis laskenta
modulo $12.$ 

Voidaan ajatella, että kokonaislukusuora on kierretty rullalle, joka kiertää
samaa kehää äärettömän monta kertaa. Kehä on jaettu $12:$een osaan, yleisesti modulin eli jakajan ilmaisemaan määrään osia. Useimmiten emme ole kiinnostuneita siitä, montako täyttä kierrosta kehän ympäri tehdään, vaan siitä, mille 
kohdalle "onnenpyörää"\/ lopulta pysähdytään. 

Käytännön laskutoimitukset ($+ - \cdot$), kun modulina on $n$, suoritetaan niin, että lasketaan 
luvuilla $0,\ldots,n-1.$ Lopputulos "redusoidaan modulo $n$", ts. lisätään tai vähennetään
$n$:n monikertoja niin, että päästään välille $0,\ldots n-1,$ eli kerran vielä: lasketaan jakojäännös, kun jakajana on $n$. 
%Tämä toimii yhteen-, vähennys- ja kertolaskun suhteen. Jakamisen käsitellään erikseen, sehän ei ole aina edes määritelty kokonaisluvuille (muuten kuin parina (osamäärä, jakojäännös)).

Formaalimpi ja matemaattisesti kauemmas kantava tapa on tarkastella ns. jäännösluokkia 
modulo $n$, jolloin "samaistetaan"\/ kaikki luvut, joilla on sama jakojäännös 
jaettaessa luvulla $n$.
Viittaan koulukirjoihin [Lukio2] Kongruenssi, s. 126, tai [Lukio1] 
Kappale 5 s. 82.
Koska pyrin pitämään koneiston minimaalisena salakirjoitustavoitteitamme 
ajatellen,
vältän ylimääräisiä uusia abstraktioita, niin elegantteja ja 
keskeisiä matemaattisen käsitteenrakennuksen välineitä kuin ovatkin.


\subsubsection*{Kongruensseilla laskeminen}

Kongruenssi näyttää yhtälöltä ja monessa suhteessa käyttäytyy samoin.

\begin{lause}\label{konruenssipluspiste}
$$\text{Jos}\ \ a \equiv b\, (\Mod\ \ n)\ \ \text{ja}\ \ c \equiv d\, (\Mod\ \ n),\ \
\text{niin}$$
$$a\pm c \equiv b\pm d \, (\Mod\ \ n) \ \ \text{ja}\ \ a\,c \equiv b\,d \, (\Mod\ \ n). $$
\end{lause}

\begin{proof}
Tyydytään todistamaan vain summan tapaus. Erotus on aivan samanlainen. Tulo on hiukan 
pitempi, mutta periaate on sama, eikä siinä voi mitenkään johtua harhateille (eihän!).
(Yritä itse, mutta voit myös katsoa [Lukio1] s. 85).

No niin, olkoon siis $n\,|\,(a-b)$ ja $n\,|\,(c-d),$ ts. 

$a-b = j\,n$ ja $c-d=k\,n$ joillakin luvuilla $j,\ \ k$. Nyt 

$(a+c) - (b+d) = j\,n - k\,n = (j-k)\, n,$ joten
todellakin 

$a+c = (b+d) + K\, n,$ missä $K=j-k \in \Z,$ eli väite on tosi.
\end{proof}

Erityisesti valitsemalla $c=d (= m)$  nähdään, että kongruenssiin voidaan lisätä puolittain
luku, se voidaan kertoa puolittain luvulla 
ja korottaa potenssiin:\\


\begin{lause}\label{modyht}
Jos $a \equiv b\,(\Mod\ \ n)$ ja $k\in \Z,\ \  m\in \N$, niin 
%\begin{enumerate}
\begin{itemize}
\item[(1.)]
$  a+k \equiv b +k \,(\Mod\ \ n), $ 
\item[(2.)]
$  a\,k \equiv b\, k \,(\Mod\ \ n),$ 
\item[(3.)]
$  a^m \equiv b^m \,(\Mod\ \ n)$.
%\end{enumerate}
\end{itemize}
\end{lause}

\textbf{Kongruenssiyhtälön supistaminen} 

Kyseessä on oikeastaan vain lauseen \ref{modsupistusok} yhteydessä esitettyjen
asioiden pukeminen modulaariaritmetiikan kielelle. 

\begin{esim}\label{modsupistusei}
$$2\cdot 2 \equiv 2\cdot 5 (\Mod\ \ 6).$$
Voidaanko tekijällä $2$ supistaa? Ts, päteekö\\ 
$2 \equiv 5 (\Mod\ \ 6)$ ?
No eipä tietenkään, sillä $5-2 = 3,$ joka ei taatusti ole $6$:n 
kokonaismonikerta.
\end{esim}


%Esimerkki %~\ref{modsupistusei} 
%osoittaa. Seuraus ~\ref{modsupistusok} antaa
%ehdon, jolla supistaminen on sallittua. Koska asia on jatkon kannalta tärkeä,
%muotoillaan se vielä uudelleen modulaariaritmetiikkaa käyttäen.
Ehto, jolla supistaminen on sallittua, ei yllättäne ketään.

\begin{lause}[Modsupistus]\label{modsupistus}
Jos $\syt(k,n)=1,$ niin 
$a\,k \equiv b\, k \,(\Mod\ \ n) \implies a \equiv b\,(\Mod\ \ n)$.\\
Sanallisesti: Kongruenssiyhtälö voidaan supistaa yhteisellä kertoimella $k$,
mikäli kerroin $k$ ja moduuli $n$ ovat yhteistekijättömät.
\end{lause}
\begin{proof}
Oletetaan siis, että $\syt(k,n)=1$ ja \\ $a\,k \equiv b\, k \,(\Mod\ \ n).$
Tällöin $(a-b)\,k \equiv 0 \,(\Mod\, n),$ joten $n | (a-b)\,k.$
Koska $\syt(k,n)=1$, niin lauseen ~\ref{modsupistusok} mukaan $n | (a-b),$
ts.  $a \equiv b\,(\Mod\, n).$
\end{proof}

\subsubsection*{Kongruenssiyhtälö, käänteisalkio}

Tarkastelemme yksinomaan muotoa $a\,x \equiv b\,(\Mod\ \ n)$ 
olevia yhtälöitä. Yleisesti kokonaislukukertoimisia yhtälöitä 
sanotaan \emph{Diofantoksen yhtälöiksi} ja niihin liittyvä teoria on osa lukuteorian perusoppia. Salakirjoituksen kannalta tarvitaan vain yllä olevaa muotoa, 
vieläpä sillä lisärajoituksella, että $b=1.$ 


\begin{lause}
%(33.26) \\ 
Olkoon $n>1$ ja  $\text{syt}(a,n)=1.$ Tällöin yhtälöllä 
$a\,x \equiv 1 (\Mod\ \ n)$ on yksikäsitteinen ratkaisu $x$.
\end{lause}

\begin{proof}
1. Ratkaisun olemassaolo: Todistus seuraa suoraan Lauseesta \ref{sytlause}
%(s. ~\pageref{sytlause}) 
näin: Koska $\syt(a,n)=1,$ on olemassa kokonaisluvut $x$ ja $y$ siten, että $a\, x + n\, y =1,$ ts.  $a\, x = 1 + n\, y.$  
Mutta tämähän tarkoittaa, että\\ 
$a\,x \equiv 1 (\Mod\ \ n).$


2. Ratkaisun yksikäsitteisyys seuraa suoraan \emph{Modsupistus}-lauseesta
~\ref{modsupistus}. (Mieti kuitenkin!)
%Olkoon $x'$ toinen ratkaisu. Siten 
%$$\begin{cases}
%a\,x \equiv 1 (\mod\ n) \\
%a\,x' \equiv 1 (\mod\ n) 
%\end{cases}
%$$
%Siispä $a(x-x')\equiv 0 (\mod n),$ joten $n$ on tekijänä tulossa $a(x-x')$.
%Koska $n$ ei ole tekijänä $a:$ssa, sen on oltava tekijänä $(x-x'):$ssa.
%(Seuraus ...)
\end{proof}

Yllä olevan yhtälön ratkaisu voidaan ajatella käänteisalkion etsimistehtäväksi
annetulle $a:$lle. Tyydyttävämmin sanottuna kyse on $a:$n määräämän 
"jäänösluokan"\/ modulo $n$ käänteisalkiosta, josta kuitenkin lupasimme olla 
puhumatta 
enempää tällä kertaa.  Ratkaisua $x$ merkitään usein symbolilla 
$x=a^{-1} (\Mod \ \ n).$ Yksikäsitteinen käänteisalkio ($\Mod \ \ n$) on siis 
olemassa jokaiselle $a:$lle, joka on yhteistekijätön modulin $n$ kanssa.

Käänteisalkion määrittämiseen tarvitaan menetelmä lauseen \ref{sytlause} 
kertoimen $x$ (siellä merkittiin $x_0$) laskemiseksi. Se voidaan tehdä ns. 
laajennetulla Eukleideen algoritmilla. 
Palataan tähän kirjoituksen osassa 2.
%joka englanniksi tunnetaan nimellä {\sc Extended Euclid}. 


\subsection*{Fermat'n pieni lause}

Kaikkihan ovat kuulleet legendaarisia tarinoita \emph{Fermat'n} suuresta lauseesta \emph{"Fermat's last theorem"}. Kuinka "olen löytänyt ihmeellisen todistuksen, joka ei mahdu muistikirjani marginaaliin", ja kuinka englantilainen
\emph{Andrew Wiles}, $7$ vuotta yksinäisessä vinttikamarissa työskenneltyään todisti 
tuon vuodesta $1630$ matemaattista maailmaa kiusanneen lauseen. Kuinka siitä 
löytyi puutteita, jotka \emph{Wiles} myöhemmin onnistui paikkaamaan. Ja kuinka tuo todistus ei mahtuisi sataankaan marginaaliin.

No, nyt emme puhu siitä enempää, vaan "pienestä"\/ lauseesta, joka 
on yksi keskeinen osa salakirjoitusmenetelmän oikeellisuuden todistusta.

%Lauseelle on monta erilaista todistusta. Viitteessä 
%\verb_ http://www... _ on ainakin $5$ erilaista todistusta, mielenkiintoisella
%tavalla erilaisia. Esitämme tässä sellaisen, joka nojautuu puhtaasti
%modulaariaritmetiikan perusasioihin ja edellä esitettyyn supistuslemmaan.

\begin{lause}[Fermat'n pieni lause]\label{FermatP}
Jos $p$ on alkuluku ja $a$ ei ole jaollinen $p:$llä, niin
$$a^{p-1} \equiv 1 (\Mod\, p).$$
\end{lause}

\begin{proof}
%Voidaan olettaa, että $0 < a \leq p-1.$
%Oikean puolen epäyhtälö  
%palautuu siihen, että tulo $a\,b (\mod p)$ on ekvivalentti (mod p) tulon
%$a (\mod p)\cdot b (\mod p)$ ($p$:n ei tätä varten tarvitse olla alkuluku).
%Tästähän seuraa (induktiolla), että $a^{n}$ (mod $p$) voidaan muodostaa 
%korottamalla $a (\mod p)$ (joka on $<p$) potensiin $n$ ja redusoimalla tulos 
%modulo p.
Lauseen \ref{modyht} kohdan (3.) perusteella $a$ voidaan redusoida välille
$\left[0,p-1\right].$ Koska $p$ ei ole tekijänä $a:$ssa, ei $a$ ole 
kongruentti $0:$n kanssa modulo $p$. Niinpä riittää osoittaa väite oletuksella
$0 < a \leq p-1.$

Muodostetaan jono 
$$(A) : a, 2\,a, 3\,a,\ldots, (p-1)\,a \ \ (\Mod\ \ p).$$
Nämä ovat siis jakojäännöksiä, kun jakajana on $p$, siis lukuja välillä 
$\left[0,p-1 \right]$. \\
Osoitetaan, että luvut ovat $>0$, ja että tässä on jokainen luku välillä 
$1,\ldots,p-1$ täsmälleen kerran.
Toisin sanoen jono $(A)$ antaa luvut $1,\ldots,p-1$ jossain järjestykseesä.

Jotta juonen seuraaminen olisi miellyttävämpää, jätämme tämän yksityiskohdan 
erikseen osoitettavaksi.

Kun se on tehty, tiedetään siis, että 
$$a\cdot 2\,a\cdot 3\, a \cdot \ldots \cdot (p-1)\, 
a \equiv 1\cdot \ldots \cdot (p-1) = (p-1)!\ \ (\Mod\ \ p).$$
 
Toisin sanoen $a^{p-1} (p-1)! \equiv (p-1)! \ \ (\Mod\ \ p).$

Palamme halusta jakaa yhtälö puolittain $(p-1)!$:lla, mutta onko lupa?
No eipä muuta kuin sydämen kyllyydestä sovellamme lausetta \ref{modsupistus},
jonka oletus on voimassa, sillä mikään 
luvuista $2,\ldots,p-1$ ei voi olla alkuluvun $p$ tekijä.

Lause on todistettu, kunhan selvitämme tuon edellä mainitun puuttuvan 
yksityiskohdan.

Tiedämme jo, että $a\neq 0$.
Voisiko olla $k\,a \equiv 0 \ \ (\Mod \ \ p)$ jollain $k=1,\ldots p-1$? 
No tämähän merkitsisi, että $p$
olisi tekijänä $k\, a:$ssa. 

Seuraus \ref{modsupistus2} vaatisi, että  
$p$ on tekijänä $k:$ssa tai $a:$ssa, mutta kumpikaan ei päde.
Tiedämmehän, että $\syt(p,a)=1$
ja $\syt(p,k)=1,$ kun $k=1,\ldots,p-1,$ koska kerran $p$ on alkuluku. 
Jonon $(A)$ luvut ovat siis joukossa
$\lbrace 1,\ldots,p-1\rbrace.$ 

Lisäksi ne ovat kaikki erillisiä, sillä jos $j$ ja $k$ ovat joukossa
$\lbrace 1,\ldots,p-1\rbrace$
ja
$j\,a \equiv k\, a \ \ (\Mod \ \ p),$ niin modsupistuslauseen 
\ref{modsupistus} mukaan $j=k.$

Siinä kaikki.
\end{proof}

Huomaamme, että oikeastaan ainoa työkalu oli Modsupistuslause 
\ref{modsupistus}. Todistuksen juonen keksiminen on sitten aivan toinen juttu.

\emph{Pierre de Fermat}
esitti väitteen ystävälleen 18.10.1640 päivätyssä kirjeessään. Kuten miehen tapoihin kuului, hän ei tällekään väitteelle esittänyt todistusta. ("Lähettäisin 
myös todistuksen, ellen pelkäisi sen olevan liian pitkän.")
Ensimmäinen tunnettu todistus on \emph{Leibniz'n} julkaisemattomassa käsikirjoituksessa vuodelta 1683 ja ensimmäinen julkaistu on peräisin \emph{Eulerilta}
vuodelta 1736. Nämä ovat keskenään periaatteessa samanlaisia, binomikaavaan
perustuvia, kokonaan toisenlaisia kuin yllä annettu.

Lauseelle on myöhemmin keksitty useita kiintoisia todistuksia. Kts.
\verb+ http://en.wikipedia.org/wiki/+ \\
\verb+Proofs_of_Fermat%27s_little_theorem.+
Uusimpien joukkoon kuuluu hollantilaisen tietojenkäsittelytieteen
gurun ja vuoden 1972 \emph{Turingin palkinnon} saajan 
\emph{Edsger Dijkstra'}n vuonna 1980 keksimä kombinatorinen todistus. Sekin 
on yllä mainitussa viitteessä esitettynä.



%Sen lisäksi kannattaa panna merkille, että todistus on helppo ymmärtää, mutta ... kukapa keksisi tuollaisen? Siinä on vähän niinkuin tulkitsemisen ja 
%säveltämisen välinen ero.
%Tai kenties taidekriitikon ja taiteen tekijän välinen.


\subsection*{Salakirjoitus tulee}

Näillä pohjatiedoilla päästään käsiksi johdannossa mainittuun 
salakirjoitusmenetelmään, joka on aiheena seuraavassa Solmun numerossa ilmestyvässä osassa 2, toistaiseksi vain omien arkistojeni uumenissa piileskelevänä
ja muotoaan hakevana salakirjoituksena.




%Kaksi päälausetta: syt-lause ja modsupistuslause (eri muodoissaan).
%Mitä seuraavassa osassa.
%Salausta, algoritmien tehokkuutta, joitakin lisätyökaluja lukuteoriasta,
%kutan Kiinalainen jäännöslause, ...



\subsubsection*{Viitteet}

%R: Rivest\\
%H: Halmetoja \\
%N: Norssi\\
%K: Kaisa

\begin{tehtratk}

\item[[Algo]] T.H. Cormen, C.E. Leiserson, R.L. Rivest:
\emph{Introduction to Algorithms}, The MIT Press, McGraw-Hill, 1998.

\item[[Lukio1]] Halmetoja, Häkkinen, Merikoski, Pippola, Silfverberg, Tossavainen, Laurinolli, Väänänen:
\emph{Lukuteoria ja logiikka, Matematiikan taito, syventävä kurssi 11}, WSOY\

\item[[Lukio2]] Kangasaho, Mäkinen, Oikkonen, Paasonen, Salmela:
\emph{Logiikka ja lukuteoria}, Pitkä matematiikka, syventävä kurssi, WSOY
%\footnote{}

\item[[NumberTH]] Humphreys, Prest:
\emph{Numbers, groups and codes}, Cambridge U.P. 1989.

%\item[K.] Kaisa Nyberg

\item[[Wiki]] \verb+http://en.wikipedia.org/wiki/+\\
\verb+Fermat's_little_theorem+

\item[] Kirjat [Lukio1] ja [Lukio2] ovat saman syventävän kurssin 11 keskenään vaihtoehtoisia kirjoja. Edellinen käsittelee tätä aihetta hiukan laajemmin

%\emph{kryptologia, kryptografia, encrypt, decrypt, modular arithmetic, Fermat, Lagrange, Euler, RSA, Chinese remainder theorem}.

%\emph{}

\end{tehtratk}

%\end{thebibliography}


%\end{document}


















\end{multicols}
%\end{document}
