Salausmenetelmät / Osa 1

Veikko Keränen, Jouko Teeriaho (Lapin AMK 2015)

LUKUTEORIAA JA ALGORITMEJA

Sisällysluettelo

Johdanto

1.  Jaollisuus

1.1  Tekijöihin jako

1.2  Jakoalgoritmi

1.3  Alkuluvut

1.4  Suurin yhteinen tekijä ja pienin yhteinen jaettava.  Aritmetiikan peruslause.

Etätehtävät kappaleeseen 1

2.  Eukleideen algoritmi

2.1  Suurimman yhteisen tekijän tehokas laskutapa

2.2  Lineaarikombinaatio  syt(a,b)=u a+v b

2.3  Eukleideen algoritmin kompleksisuus

Etätehtävät kappaleeseen 2

3.  Kongruenssit

3.1  Jakojäännös ja kongruenssi

3.2  Jäännösluokka

3.3  Täydellinen jäännössysteemi

3.4  Kongruenssien laskusääntöjä

Etätehtävät kappaleeseen 3

4.  Eulerin ja Fermat'n lauseet

4.1  Alkuluokka ja Eulerin φ-funktio

4.2  Supistettu jäännössysteemi

4.3  Eulerin ja Fermat'n lauseet

4.4  Eulerin funktio ja kertolaskun säilyminen

4.5  Suurien potenssien nopea laskeminen: Eulerin lause ja peräkkäiset neliöönkorotukset

Etätehtävät kappaleeseen 4

5.  Lineaarisen kongruenssiyhtälön ratkaiseminen

5.1  Yksi lineaarinen kongruenssiyhtälö

5.2  Käänteisalkio modulo  m

5.3  Kongruenssiyhtälön ratkaiseminen tietokoneella

Osan 1 etätehtävät – kooste kaikista kappaleista

Kirjallisuutta

Liitteet

Liite 1.  Laajennettu Eukleideen algoritmi – suoraviivainen tapa
		Johdanto
		Matemaattinen induktiotodistus
		Matriisien kertolaskun käyttömahdollisuus
		Käsinlaskuesimerkkejä
		Kaikki välivaiheet esittävä ohjelma Mathematicalla

Liite 2.  Ryhmien ja kuntien perusteet
		Ryhmät
		Ryhmien perusominaisuudet
		Aliryhmät
		Sykliset ryhmät ja ryhmän generaattori
		Syklisten ryhmien ominaisuuksia
		Sivuluokat ja Lagrangen teoreema
		Renkaat ja kunnat

Johdanto

Tässä opintojakson ensimmäisessä osassa käsitellään salausmenetelmien kannalta keskeisiä lukuteorian perustuloksia ja algoritmeja. Tavoitteena on ollut aineiston saattaminen sellaiseen muotoon, että sitä voitaisiin käyttää muuallakin matematiikan ja tekniikan opetuksessa sekä itseopiskelussa. Materiaali sopii käytettäväksi esimerkiksi ammattikorkeakoulujen diskreetin matematiikan opintojaksoilla ja yliopistojen peruskursseilla. Lisäksi aiheesta kiinnostuneet lukioiden oppilaat voivat osallistua näille opintojaksoille.

Laajuudeltaan salausmenetelmien kurssi – Osa 1 ja Osa 2 yhteensä – on 5 opintopistettä. Osa 1 ja sen liitteet sisältävät lukuteorian ja algebrallisten rakenteiden alkeita, algoritmeja ja ohjelmointia. Osassa 2 keskitytään eri salakirjoitusjärjestelmiin ja sovelletaan Osan 1 matemaattisia rakenteita monipuolisesti. Molemmissa osissa esimerkkien laskelmat on tehty Mathematica-ohjelmaa käyttäen.    

Niissä opiskelutilanteissa, joissa Mathematica-ohjelma on käytettävissä, algoritmeja voidaan kokeilla muutetuilla lähtöarvoilla. Algoritmien toteutuksiin liittyvät rakenteet ja yksityiskohdat saattavat kiinnostaa myös muiden ohjelmointiympäristöjen käyttäjiä. Internetistä löytyy lisäksi useita sopivia laskentaympäristöjä. Erityisesti Osassa 2 käytetään Wolfram|Alpha-laskentaympäristöä. Myös Osan 1 kohdalla laskentaympäristöjen käyttö on suotavaa, mutta ei kuitenkaan välttämätöntä ajatuksen ymmärtämisen kannalta. 

Laskuharjoitukset ovat keskeinen osa opintojakson käsitteiden ja rakenteiden oppimisessa. Kaikista apuvälineistä huolimatta Osan 1 laskuharjoitukset on syytä tehdä myös kynällä ja paperilla. 

Osassa 1 on esitetty myös lauseiden todistukset. Tämä on toki luontevaa matemaattisten rakenteiden ymmärtämisen kannalta ja auttaa niitä jotka haluavat perehtyä aihepiiriin tarkemmin. Kaikkien todistusten yksityiskohtien hallintaa ei kuitenkaan vaadita ammattikorkeakoulujen insinööriopinnoissa.

1.  Jaollisuus

1.1  Tekijöihin jako

Olkoon  ℕ  luonnollisten lukujen joukko,  ℤ  kokonaislukujen joukko,  ℚ  rationaalilukujen joukko  ja  ℝ  reaalilukujen joukko.  Siis  ℕ = {0, 1, 2, 3, ... },  ℤ = {0, ±1, ±2, ±3, ... },  ℚ = {(m/n)|  m,n ∈ ℤ,  n≠ 0}  sekä esimerkiksi luvut  π  ja (Sqrt[2])  ovat joukon  ℝ  alkioita. Luvun (tai yleisesti alkion)  a  kuulumista joukkoon  A  merkitään kirjoittamalla  a ∈ A.

Esimerkki 1.1   11 ∈ ℕ,   -11 ∈ ℤ,   (11/13) ∈ ℚ  ja    (Sqrt[11]) ∈ ℝ.

Sanomme, että kokonaisluku  d  on kokonaisluvun  n  tekijä (tai jakaja tai että  d  jakaa luvun n),  jos  n=k d  jollekin k∈ℤ.   Tällöin käytetään merkintää  d|n.  Jos lukua  k ∈ ℤ  ei ole olemassa,  d  ei ole luvun  n  tekijä (ts. d  ei jaa lukua  n).  Tällöin merkitään  d∤n.

Esimerkki 1.2   Luku  d = 3  jakaa luvun  n = 6,  ts.  3|6,  koska  6 = 2·3.  Tässä siis  n = k d  arvolla  k = 2.  Toisaalta  3  ei jaa lukua  7,  ts.  3∤ 7,  koska lukua  7  ei voida kirjoittaa muotoon  7 = k·3  millekään kokonaisluvulle  k.

Esimerkki 1.3   Luvun  6  kaikki tekijät ovat  ±1, ±2, ±3  ja  ±6.

Huomautus 1   Koska  0 = 0·a,  niin  a | 0  kaikilla  a∈ℤ  (mutta  0 ∤ a  jos  a  ≠ 0).  
Huomautus 2   Yllä olevan määritelmän mukaan  0  on luvun  0  tekijä, ts.  0 ∤ 0.  Vaikka toisinaan vapaamieliesti sanommekin tekijää jakajaksi, ei pidä kirjoittaa lauseketta muotoon 0/0,  koska tämä ilmaisu ei edusta mitään määriteltyä lukua.

Jokaisella luvulla  a∈ℤ  on ns. triviaalit tekijät  ±1  ja  ±a.

Kokeillaksemme, jakaako kokonaisluku  d  luvun  n,  voimme Mathematica-ohjelmassa käyttää funktiota IntegerQ seuraavaan tapaan:

n=1218;d=3;  IntegerQ[n/d]

n=1218;d=9;  IntegerQ[n/d]

Mathematica-funktio Divisors antaa kaikkien luvun n  positiivisten jakajien (ts. tekijöiden) muodostaman listan. Esimerkiksi:

n=35; Divisors[n]

n=12345; Divisors[n]

Harjoituksia

1  	Onko kokonaisluku  19  seuraavien kokonaislukujen tekijä?
	a)  57		b)  –95		c)  228		d)  10001

2  	Etsi seuraavien kokonaislukujen kaikki tekijät.
	a)  57		b)  71		c)  100		d)  512

1.2  Jakoalgoritmi

Seuraavan lauseessa esiintyvää yhtälöä  a = q b + r,  0≤ r < |b |,  nimitetään usein jakoyhtälöksi.  Korostamme jatkossa lukujen laskemisen prosessia ja käytämme näin ollen tästä lauseesta nimeä jakoalgoritmi.

Lause 1.1	Jakoalgoritmi

Jos  a, b ∈ ℤ,  b≠0,  niin on olemassa sellaiset yksikäsitteiset luvut  q, r ∈ ℤ,  että

	a = q b + r,  0≤ r < |b |.  

Luku  r  on ns. jakojäännös modulo  b.

Jakoyhtälöä voidaan  tilanteessa  a > b > 0  havainollistaa seuraavasti:

|---------------------------------------------------------a-----------------------------------------------------------|
|----------b----------|----------b----------|----------b----------|----------b----------|----------b----------|---r---|

Tässä tapauksessa  q = 5  ja  r > 0,  joten jako ei mene tasan.

Esimerkki 1.4   a)  Kun  a = 111  ja  b = 7,  voidaan kirjoittaa  111 = 15·7 + 6,  missä siis kerroin  q = 15  ja jakojäännös  r = 6.   Mathematicalla voitaisiin laskea seuraavasti:

Quotient[111,7]

Mod[111,7]

b)  Kun  a = –111  ja  b = 7,  on voimassa   –111 = –16·7 + 1.  Tässä  kerroin  q = –16  ja jakojäännös  r = 1.

Quotient[-111,7]

Mod[-111,7]

Esimerkki 1.5   Eri lukujärjestelmiä
Kokonaislukuja voidaan muuttaa toisiin lukujärjestelmiin soveltamalla jakoalgoritmia toistuvasti. Yleensä olemme tottuneet käyttämään 10-järjestelmää, jossa esimerkiksi luku  2358 = 2000 + 300 + 50 + 8,  toisin sanoen

	2358 = 2·(10^3) + 3·(10^2) + 5·(10^1) + 8·(10^0). 
	
Voimme kuitenkin esittää lukuja muissakin kantajärjestelmissä kuin 10-järjestelmässä. Muutetaan luku 2358 vaikkapa 16-järjestelmään jakamalla toistuvasti luvulla 16:

	2358 = 147·16 + 6,    147 = 9·16 + 3, 
joten  
	2358 = 147·16 + 6 = (9·16 + 3)·16 + 6 = 9·(16^2) + 3·(16^1) + 6·(16^0)

Siis  2358 = (Subscript[936, 16]),  missä olemme merkinneet kantaluvun näkyviin alaindeksin avulla. 10-järjestelmän luvuissa ei alaindeksiä yleensä yksinkertaisuuden vuoksi käytetä (luvut 2358 ja (Subscript[2358, 10]) tarkoittavat samaa lukua). 

Vastaavasti voisimme muuttaa luvun  2358  binäärijärjestelmään eli 2-kantaiseen järjestelmään jakamalla toistuvasti luvulla 2.  Jätämme muunnoksen tekemisen harjoitustehtäväksi. Tulokseksi saadaan, että  2358 = (Subscript[100100110110, 2]).  

Totea myös, että  2358 = (Subscript[6606, 7])  (7-järjestelmän esitys).

Lauseen 1.1 (jakoalgoritmi) todistus: 
1)  Oletetaan, että  a, b ∈ ℤ,  b≠0.  	Todistetaan ensiksi kokonaislukujen  q  ja  r  olemassaolo  esitysmuodossa  a = q b + r,  0≤ r < |b |. 

Olkoon  b > 0.  Merkitään

	S = {n | n = a – kb, k ∈ ℤ,  n ≥ 0} .
	
Joukko  S  on joukon  ℕ  osajoukko.  Koska aina voidaan valita  k ∈ ℤ  niin, että  kb ≤ a,  ts. a – kb ≥ 0,  nähdään että  S  ei ole tyhjä joukko.  Täten hyvinjärjestämisen aksiomin (Well–Ordering Axiom) nojalla joukossa  S  on pienin alkio  r.  Siis  r = a – qb  eräälle  q∈ ℤ.  Koska  r ∈ S,  on  r ≥ 0.  Toisaalta  r < b,  sillä jos olisi  r ≥ b,  niin   r – b ≥ 0  ja  r – b = (a – qb) – b =  a – (q + 1) b,  joten  r – b ∈ S  ja  r – b  < r.  Tämä on mahdotonta, koska  r  on joukon  S  pienin alkio.  Siis  r < b.  Näin ollen tapauksessa  b > 0  luvut  q  ja  r  toteuttavat Lauseen 1.1 esityksen  a = q b + r,  0≤ r < |b |  olemassaoloa koskevat ehdot.

Olkoon  b < 0.  Tällöin  –b > 0  ja edellä todistetun mukaan on olemassa  q, r ∈ ℤ,  joille 
	
	a = q (– b) + r,  0 ≤ r < –b = |b|,  ts.
	a = –q b + r
	
Täten myös tapauksessa  b > 0  luvut  –q  ja  r  toteuttavat Lauseen 1.1 olemassaoloa koskevat ehdot.

2)  Todistetaan, että luvut  q  ja  r  ovat yksikäsitteiset.  Olkoon joillakin luvuilla  a  ja  b  kaksi esitystä  

	a = q b + r,  0 ≤ r < |b|,  	ja 	 a = (Subscript[q, 1]) b + (Subscript[r, 1]),  0 ≤ (Subscript[r, 1]) < |b|. 
	
Tällöin  q b + r  =  (Subscript[q, 1]) b + (Subscript[r, 1]),  ts.  

(1)	(q – (Subscript[q, 1])) b = (Subscript[r, 1]) – r.

Tapaus 1.  q = (Subscript[q, 1]).  Tällöin kohdan (1) nojalla  r = (Subscript[r, 1]).

Tapaus 2.  q ≠ (Subscript[q, 1]).  Tällöin  | q – (Subscript[q, 1])| ≥ 1  ja kohdan (1) nojalla saadaan  | (Subscript[r, 1]) – r | = | (q – (Subscript[q, 1])) b | = | q – (Subscript[q, 1]) | | b | ≥ | b |.  Tämä on mahdotonta, koska  0 ≤ r, (Subscript[r, 1]) < |b|  (ja täten | (Subscript[r, 1]) – r | < | b |).

Näin ollen q = (Subscript[q, 1])  ja  r = (Subscript[r, 1]).

□

Harjoituksia

3	Suorita jakolasku  543 : 21  ja kirjoita tulos jakoyhtälönä muodossa
	jaettava =  vaillinainen osamäärä  kertaa  jakaja  plus  jakojäännös,
	ts. muodossa 	a = q b + r,  0≤ r < |b |,  missä  a = 543,  b = 21,
	q = vaillinainen osamäärä  ja  r = jakojäännös.

4 	Muunna 10–järjestelmän luku  511  
	a)  binääriluvuksi  
	b)  8–kantaiseen järjestelmään 
	c)  esitä luku  (Subscript[1234, 7])  10–järjestelmän lukuna

5  	Muuta luku 10–järjestelmän luku  2358  
	a)  binääriluvuksi
	b)  7–kantaiseen järjestelmään

1.3  Alkuluvut

Kokonaisluku  p, p>1,  on alkuluku (prime), jos  1  ja  p  ovat sen ainoat positiiviset tekijät, ts. jos luvulla  p  on vain triviaalit tekijät.  Kokonaisluku p>1  on yhdistetty luku, jos se ei ole alkuluku.  Asettamalla (Subscript[p, 1])=2, (Subscript[p, 2])=3, (Subscript[p, 3])=5, … saadaan luonnollinen alkulukujen numerointi.

Tässä yhteydessä esittelemme hyödylliset Mathematica-funktiot  Prime  ja  PrimeQ:

Prime[1]

k=1000; Prime[k]

Luku 7919 on siis 1000. alkuluku.

Merkitään alkululuvut väliltä 1 - 50:

If[PrimeQ[#],Framed[#],#]&/@Range[50]

Kysytään onko luku  1234567  alkuluku vai ei:

n=1234567; PrimeQ[n]

Vastauksena saatiin että luku  1234567  ei ole alkuluku, vaan yhdistetty luku.

Huomaa kuitenkin, että Mathematica Help (Wolfram Language & System | Documentation Center) esittää seuraavan kommentin:

• PrimeQ first tests for divisibility using small primes, then uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test. 
• As of 1997, this procedure is known to be correct only for n<(10^16), and it is conceivable that for larger n it could claim a composite number to be prime.

Tästä huolimatta ei ilmeisesti tunneta yhtään esimerkkiä tapauksesta, jossa PrimeQ olisi väittänyt yhdistettyä lukua alkuluvuksi. Testin ilmoittaman tuloksen tiedetään kyllä olevan aina oikein silloin, kun vastauksena saadaan  False.  Tällöin luku on varmasti yhdistetty luku, vaikka sen tekijöihinjakoa ei saataisikaan selville. Todellakin, tekijöihin jakaminen voi olla käytännössä mahdotonta hyvin suurten kokonaislukujen tapauksessa. Tilanne voi muuttua jos kvanttitietokoneen kehityksessä tapahtuu merkittävää edistymistä. Tosin D-Wave-yhtiö väittää kesällä 2015 ylittäneensä jo 1000 kubitin rajan. Katso http://www.dwavesys.com/ (“D-Wave commercializes 1152 qubit chip but there are 2048 physical qubits so some chips will have more than 1152 qubits active.”).

Merkintä: 	 (∏_(i=1)^k)(Subscript[a, i]) = (Subscript[a, 1])(Subscript[a, 2])⋯ (Subscript[a, k])  (tulo)

Esimerkki 1.1
Tarkastellaan muutamia yo. tulomuodon käyttöön liittyviä perusesimerkkejä.

	(∏_(i=1)^3) i = 1·2·3,    (((∏_(i=1)^4) i)^( 2)) = (1^2)·(2^2)·(3^2)·(4^2),
	
	(((∏_(i=1)^k) (1/i))^( )) = (1/1)·(1/2)·(1/3)⋯ (1/k),
	
	(((∏_(i=1)^r) (1-(1/(Subscript[p, i]))))^( )) =  (1-(1/(Subscript[p, 1]))) (1-(1/(Subscript[p, 2])))⋯ (1-(1/(Subscript[p, r])))

Lause 1.2		Eukleides	(Euclid)

Alkulukuja on ääretön määrä.

Todistus: Tehdään vastaoletus, että alkulukujen määrä on äärellinen. Olkoot (Subscript[p, 1]),(Subscript[p, 2]),…,(Subscript[p, k])  nämä kaikki alkuluvut. On kuitenkin olemassa lukuja, jotka eivät ole jaollisia millään alkuluvulla (Subscript[p, 1]),(Subscript[p, 2]),…,(Subscript[p, k]).  Esimerkiksi  m = ((∏_(i=1)^k)(Subscript[p, i]))+1 = (Subscript[p, 1])·(Subscript[p, 2])⋯ (Subscript[p, k]) + 1  on sellainen luku (sillä jakojäännös alkuluvulla jaettaessa on aina = 1).  Olkoon nyt  n  pienin näistä kokonaisluvuista, joita ei voida jakaa millään luvuista  (Subscript[p, 1]),(Subscript[p, 2]),…,(Subscript[p, k])  (näimme juuri että näitä lukuja on olemassa, esimerkkinä m, ja pienin niistä voidaan valita hyvinjärjestämisen aksiomin nojalla).  Tämä  n  ei voi olla alkuluku, koska muutoin se olisi listassa (Subscript[p, 1]),(Subscript[p, 2]),…,(Subscript[p, k]).  Siis luvulla n  on ei-triviaali tekijä  d.  Mutta tällöin  d  (< n)  on jaollinen jollakin luvuista  (Subscript[p, 1]),(Subscript[p, 2]),…,(Subscript[p, k])  ja samoin  n.  Vastaoletus johtaa siis ristiriitaan, joten Lauseen 1.2 alkuperäinen väite on tosi.

□

Kahden peräkkäisen alkuluvun välillä voi olla mielivaltaisen pitkä aukko yhdistettyjä lukuja.  Esimerkiksi, n-1 peräkkäistä lukua  n!+2,n!+3,…,n!+n  ovat jaollisia luvuilla 2,3,…,n,  vastaavasti.  Siten yksikään niistä ei ole alkuluku.

Määritelmä 1.1
π(n)  on niiden alkulukujen lukumäärä, jotka ovat  ≤  n.

Mathematicassa tämä funktio on  PrimePi.

n=10000; PrimePi[n]

Mathematica Help kertoo tästä muun muassa seuraavaa:

• Prime and PrimePi use sparse caching and sieving. For large n, the Lagarias-Miller-Odlyzko algorithm for PrimePi is used, based on asymptotic estimates of the density of primes, and is inverted to give Prime.

Seuraava Lause 1.3, jota emme todista, kertoo alkulukujen esiintymisen taajuudesta joukossa  ℕ. (Ks. esim. [HarW45] Hardy, G.H. and E.M. Wright, An Introduction to the Theory of Numbers, Clarendon Press, Oxford, 1945, p. 91; tai Bach E. and J. Shallit, Algorithmic Number Theory, Volume 1: Efficient Algorithms, Foundations of Computing Series, MIT Press, Cambridge, Massachusetts, 1996, p. 203–.)

Lause 1.3	Alkulukulause 		(The Prime Number Theorem)

	(lim_(n→∞)) ((π(n))/(n / ln n))=1.

Lasketaan kokeeksi lausekkeen  ((π(n))/(n / ln n))  numeerinen likiarvo, kun  n = 1 000 000:

n=(10^6);(( PrimePi[n])/(n/Log[n])) //N

Harjoituksia

6	Osoita, että  113  on alkuluku.

7	Mitä tarkoittavat seuraavat tulomuodot?
	
	a)  (((∏_(i=1)^4) i)^( 3))	b)  (((∏_(i=1)^n) i)^( ))	c)  (((∏_(i=1)^k) (1/(i^2)))^( ))	d)  (((∏_(i=2)^n) (1-(1/i)))^( ))

8	Todista hieman eri tavalla (tai kertaa ajatuksella) Lause 1.2 (Eukleides): Alkulukuja on ääretön määrä.

1.4  Suurin yhteinen tekijä ja pienin yhteinen jaettava

Seuraavaksi esitetään keskeiset määritelmät: suurin yhteinen tekijä (greatest common divisor, GCD) ja pienin yhteinen  jaettava  (least common multiple, LCM).

Määritelmä 1.2
Kahden kokonaisluvun  a  ja   b  (joista ainakin toinen ≠ 0)  suurin yhteinen tekijä (syt) on positiivinen kokonaisluku  d,  jolle on voimassa

(1.1) 	d  jakaa molemmat luvut  a  ja  b

ja

(1.2)	jos  f  jakaa molemmat luvut  a  ja  b,  niin  f  jakaa myös luvun  d.

Lukujen  a  ja  b  suurimmasta yhteisestä tekijästä käytetään merkintää  syt(a,b).

Määritelmä 1.3
Kahden kokonaisluvun a ja b  pienin yhteinen  jaettava on  positiivinen kokonaisluku  m,  jolle on voimassa

(1.3) 	a  ja  b  jakavat luvun  m

ja

(1.4)	jos  a  ja  b  jakavat luvun  n,  niin  n  =  k m,  k ∈ ℤ.

Lukujen  a  ja  b  pienimmästä yhteisestä jaettavasta käytetään merkintää  pyj(a ,b).

Vaihtoehtoiset määritelmät suurimmalle yhteiselle tekijälle  syt(a, b)  ja pienimmälle yhteiselle jaettavalle  pyj(a, b)   voidaan esittää muodossa:

syt(a,b)  on suurin positiivinen kokonaisluku, joka jakaa molemmat luvut  a  ja  b;
pyj(a,b)  on pienin positiivinen kokonaisluku, jonka molemmat luvut  a  ja  b  jakavat.

Osoitetaan seuraavaksi, että yllä esitetty suurin yhteinen tekijä on hyvin määritelty. Osoitetaan ensin luvun  syt(a, b)  olemassaolo.  Tarkastellaan lukujen  a  ja  b  lineaarikombinaatioista  x a + y b > 0  muodostuvaa joukkoa

U = {x a+y b | x∈ℤ, y∈ℤ, x a+y b>0}.

Olkoon  m  joukon  U  pienin alkio (tämä on olemassa hyvinjärjestämisen aksiomin nojalla).  Osoitetaan, että  m  toteuttaa ehdot (1.1) ja (1.2), joten  m  itse asiassa on  juuri etsitty luku  syt(a, b).  Selvästikin, jos kokonaisluku  f  jakaa molemmat luvut  a  ja  b,  niin  f   jakaa myös luvun  m = xa + yb.  Näin ollen  m  toteuttaa ehdon (2).  Lauseen 1 (jakoalgoritmi) nojalla voidaan luku  a  kirjoittaa muotoon  a=q m+r,  0≤r<m.  Jos r≠0,  niin  r∈U  (sillä m ∈ U,  m = xa+yb, ja siis r = a-q m = a-q(xa +yb) = (1-qx)a +(-qy)b ).  Koska 0≤r<m,  tämä on ristiriita sen kanssa, että  m  on joukon  U   pienin alkio.  Siis  r=0,  joten  m | a.  Vastaavasti  m | b.  Siis  m   toteuttaa myös ehdon (1.1).  

Syt(a,b):n yksikäsitteisyys seuraa ehdoista (1.1) and  (1.2).  Todellakin, jos  d ja d '  molemmat toteuttavat ehdot (1.1) ja (1.2), niin  d|d'  ja  d'|d.  Koska molemmat luvut  d ja d'  ovat positiivisia kokonaislukuja, saadaan yhtäsuuruus  d=d'.

Pyj(a,b):n  olemassaolo nähdään seuraavasti:  Ne positiiviset kokonaisluvut, jotka molemmat luvut  a  ja  b  jakavat, muodostavat ei-tyhjän joukon  V.  Hyvinjärjestämisen aksiomin nojalla joukossa  V  on pienin alkio, joka on juuri etsitty  pyj(a,b).

Pyj(a,b):n  yksikäsitteisyys voidaan perustella jäljempänä todistettavan aritmetiikan peruslauseen (Lause 1.7) avulla.  Tämän lauseen nojalla  a  ja  b  voidaan esittää tekijöiden järjestystä lukuunottamatta yksikäsitteisellä tavalla alkulukujen  (Subscript[p, i])  tulona muodossa   a= (∏_i) ((Subscript[p, i])^(Subscript[e, i])), (Subscript[e, i]) ∈ ℕ,  ja  b= (∏_i) ((((Subscript[p, i])))^(Subscript[f, i])), (Subscript[f, i]) ∈ ℕ.  Edelleen voidaan osoittaa, että

syt(a,b)=(∏_i)((Subscript[p, i])^(min((Subscript[e, i]),(Subscript[f, i]))))

pyj(a,b)=(∏_i)((Subscript[p, i])^(max((Subscript[e, i]),(Subscript[f, i]))))

syt(a,b) · pyj(a,b)=a b.

Tarkastellaan näitä tulomuotoisia esityksiä vain lyhyesti seuraavan esimerkin avulla.

Esimerkki 1.2

Olkoon  a = (2^5)·(3^2)·(7^2)  ja  b = (2^4)·(3^3)·(11^3).   Tällöin
 
	syt(a, b) =  (2^(min(5, 4)))·(3^(min(2, 3)))·(7^(min(2, 0)))·(11^(min(0, 3))) = (2^4)·(3^2)·(7^0)·(11^0) 
	pyj(a, b) =  (2^(max(5, 4)))·(3^(max(2, 3)))·(7^(max(2, 0)))·(11^(max(0, 3))) = (2^5)·(3^3)·(7^2)·(11^3) 
	syt(a,b) · pyj(a,b) = ((2^4)·(3^2)·(7^0)·(11^0))·((2^5)·(3^3)·(7^2)·(11^3)) = (2^(4+5))·(3^(2+3))·(7^(0+2))·(11^(0+3)) = ab.

Arvot  syt(a,b)  (GCD)  ja  pyj(a,b)  (LCM)  voidaan laskea Mathematicalla seuraavan esimerkin mukaisesti:

a=56;b=35;GCD[a,b]

a=56; b=35;LCM[a,b]

Jos kahden kokonaisluvun suurin yhteinen tekijä on = 1, sanotaan, että ne ovat suhteellisia alkulukuja (coprime). Yllä esitetyn joukkoa  U  koskevan tarkastelun tärkeänä seurauksena saadaan seuraava lause.

Lause 1.4
Olkoot  a  ja  b nollasta eroavia kokonaislukuja. Tällöin on olemassa kokonaisluvut  u  ja  v,  joille 

		syt(a,b)=u a+v b.

Toisin sanoen  syt(a,b)  voidaan esittää lukujen  a  ja  b  lineaarikombinaationa.  Erityisesti, jos  a  ja  b  ovat suhteellisia alkulukuja, on olemassa kokonaisluvut  u  ja  v,  joille

		u a+v b=1.

Seuraava lemma on hyvin luonteva.

Lemma 1.5
Olkoon  d  tulon  a b  tekijä ja olkoon  syt(d, a) = 1. Tällöin  d | b.

Todistus: Koska syt(d,a)=1, Lauseen 1.4 nojalla on voimassa x d+y a=1 joillekin kokonaisluvuille x  ja  y.  Kertomalla tämä yhtälö puolittain luvulla  b,  saadaan   x d b+y a b=b.  Koska  d | a b,  on  a b = c d,  jollekin  c ∈ ℤ.  Siis  x d b+y c d=b,   joten  d | (x d b+y c d),  ts.  d | b.

□

Seuraus 1.6
Olkoon p alkuluku, joka jakaa tulon  (∏_(i=1)^k)(Subscript[a, i]) = (Subscript[a, 1])(Subscript[a, 2])⋯ (Subscript[a, k]),  missä  (Subscript[a, i]) ∈ ℤ , 1≤i≤k. 
Tällöin p  jakaa ainakin yhden tekijöistä  (Subscript[a, i]), 1≤i≤k.

Todistus: Käytä Lemmaa 1.5 ja induktiota luvun  k  suhteen.

□

Harjoituksia

9	Laske Esimerkin 1.2 tavalla  syt(a, b)  ja  pyj(a, b),  kun
	
	a = (3^2)·(5^3)·(7^4)  ja  b = (2^4)·(3^3)·(7^2).   
 
	Totea näille luvuille, että  syt(a,b) · pyj(a,b) = ab.

1.5  Aritmetiikan peruslause

Tässä todistetaan

Lause 1.7	Aritmetiikan peruslause 	(Fundamental Theorem of Arithmetic)

Jokainen kokonaisluku  a  ≥ 2  voidaan esittää tekijöiden järjestystä lukuunottamatta yksikäsitteisellä tavalla alkulukujen  (Subscript[p, i])  tulona

		a = (∏_i)(Subscript[p, i]^(Subscript[e, i])) = ((Subscript[p, 1])^(Subscript[e, 1]))((Subscript[p, 2])^(Subscript[e, 2]))⋯ ((Subscript[p, r])^(Subscript[e, r])),    (Subscript[e, i])∈ℕ.

Todistus: 
1)  Voidaan esittää. Tehdään vastaoletus: On olemassa kokonaislukuja ≥ 2,  joille ei ole esitystä alkulukujen tulona. Hyvinjärjestämisen aksiomin nojalla tällainen pienin kokonaisluku n ≥ 2,  jolle ei ole esitystä alkulukujen tulona, on olemassa.  Koska  n  ei voi olla alkuluku (muuten se olisi sellainen esitys alkulukujen tulona, jossa on yksi tekijä), niin  n  on yhdistetty luku ja siis esitettävissä muodossa  n = (Subscript[n, 1])(Subscript[n, 2]),  missä  2 ≤ (Subscript[n, 1]),(Subscript[n, 2]) < n.  Luvun  n  valinnasta johtuen luvuilla (Subscript[n, 1]) ja  (Subscript[n, 2])  on aito esitys alkulukujen tulona.  Esimerkiksi  (Subscript[n, 1]) = (Subscript[p, 1])(Subscript[p, 2])⋯ (Subscript[p, r])  ja   (Subscript[n, 2]) = (Subscript[q, 1])(Subscript[q, 2])⋯ (Subscript[q, s])  ((Subscript[p, i]):t ja (Subscript[q, i]):t alkulukuja). Tällöin kuitenkin  n = (Subscript[n, 1])(Subscript[n, 2]) = (Subscript[p, 1])(Subscript[p, 2])⋯ (Subscript[p, r]) (Subscript[q, 1])(Subscript[q, 2])⋯ (Subscript[q, s]) on alkulukujen tulo. Vastaoletus johtaa näin ollen ristiriitaan.

2)  Yksikäsitteisyys.  Todistetaan tämä matemaattisella induktiolla.
(i)  Luvulla  2  on yksikäsitteinen esitys alkulukujen tulona (luku 2 itse).
(ii) Induktioaskel. Tehdään induktio-oletus: luvuilla  3, 4, 5, ... , n – 1  on yksikäsitteinen esitys alkulukujen tulona.  Oletetaan nyt, että  

	n = ((Subscript[p, 1])^(Subscript[e, 1]))((Subscript[p, 2])^(Subscript[e, 2]))⋯ ((Subscript[p, r])^(Subscript[e, r])) = ((Subscript[q, 1])^(Subscript[f, 1]))((Subscript[q, 2])^(Subscript[f, 2]))⋯ ((Subscript[q, s])^(Subscript[f, s])),
	
missä jokainen  (Subscript[p, i]),  1 ≤ i ≤ r,  ja  jokainen  (Subscript[q, j]),  1 ≤ j ≤ s,  on alkuluku, ja edelleen (Subscript[p, 1])<(Subscript[p, 2])<⋯ <(Subscript[p, r])  ja  (Subscript[q, 1])<(Subscript[q, 2])<⋯ <(Subscript[q, s]),  ja  (Subscript[e, i]) > 0  kaikilla  1≤ i ≤ r,  (Subscript[f, j]) > 0  kaikilla  1≤ j ≤ s.  Koska  (Subscript[p, 1])| n,  niin  (Subscript[p, 1])| ((Subscript[q, 1])^(Subscript[f, 1]))((Subscript[q, 2])^(Subscript[f, 2]))⋯ ((Subscript[q, s])^(Subscript[f, s])).  Seurauslauseen 1.6 nojalla  (Subscript[p, 1])| (Subscript[q, j])  jollekin  1≤ j ≤ s.  Koska  (Subscript[p, 1])  ja  (Subscript[q, j])  ovat alkulukuja, on  (Subscript[p, 1]) = (Subscript[q, j]).  Itse asiassa  j = 1,  muutoin ehto  (Subscript[q, 1])| n  antaisi  (Subscript[q, 1]) =  (Subscript[p, α])  jollekin 1 < α ≤ r  ja  (Subscript[p, 1]) < (Subscript[p, α]) = (Subscript[q, 1]) < (Subscript[q, j]) = (Subscript[p, 1]),  mikä on ristiriita. Siis  (Subscript[p, 1]) = (Subscript[q, 1]),  joten  (Subscript[n, 1]) = (n/(Subscript[p, 1])) = ((Subscript[p, 1])^((Subscript[e, 1])-1))((Subscript[p, 2])^(Subscript[e, 2]))⋯ ((Subscript[p, r])^(Subscript[e, r])) = ((Subscript[q, 1])^((Subscript[f, 1])-1))((Subscript[q, 2])^(Subscript[f, 2]))⋯ ((Subscript[q, s])^(Subscript[f, s])) < n.  Koska  (Subscript[n, 1]) < n,  niin induktio-oletuksen nojalla  r = s,  (Subscript[p, i]) = (Subscript[q, i])  aina kun   1 ≤ i ≤ r ;  (Subscript[e, 1])– 1 =  (Subscript[f, 1]) – 1,  joten  (Subscript[e, 1]) = (Subscript[f, 1]),  ja  (Subscript[e, i]) = (Subscript[f, i])  aina kun  2 ≤ i ≤ r.  Näin ollen luvun  n  esitys alkulukujen tulona on induktioperiaatteen nojalla yksikäsitteinen.

□

Mathematica-ilmaisu (expression) FactorInteger[n] antaa luvun n tekijät. Funktion arvona saadaan parien muodostama lista. Jokainen pari sisältää luvun  n  alkulukutekijän ja sen eksponentin. Alla esitetään esimerkkejä tekijöihin jaosta Mathematicaa käyttäen:

FactorInteger[24]

Siis  24 = (2^3)·(3^1)= (2^3)·3.

Etsitään myös luvun  10  kertoman, ts. luvun  10! = 10·9·8⋯ 2·1  kaikki alkulukutekijät.

10!

FactorInteger[10!]

Olkoon

a=204;b=303;

FactorInteger[a]

FactorInteger[b]

Luvun  syt(a,b)  (GCD)  jako tekijöihin:

FactorInteger[GCD[a,b]]

Luvun  pyj(a,b)  (LCM)  jako tekijöihin:

FactorInteger[LCM[a,b]]

Kokeillaan vielä, että tulos  syt(a,b) · pyj(a,b)=a b  on voimassa:

GCD[a,b]* LCM[a,b]==a*b

Tekijöihinjako saadaan vielä mukavampaan esitysmuotoon käyttämällä seuraavaa funktiota  f.  Muodostetaan ensin lista alkulukujen potensseista, joiden laskeminen estetään muuttamalla luvut merkkijonoiksi:

f[{p_,e_}]:=((ToString[p])^(ToString[e]));

f /@ FactorInteger[204]

f /@ FactorInteger[303]

Kehitellään muotoilua vielä niin, että saadaan luvun  30!  esitys alkulukujen tulomuodossa:

n=30!;
Times @@(f /@ FactorInteger[n])

Ohjelmoinnista kiinnostunut lukija voisi vielä järjestää tekijät kantaluvun mukaiseen suuruusjärjestykseen. Monipuolista muotoilua varten kannattaa katsoa Mathematica Helpistä löytyvää komentoa  MakeBoxes.

Tässä meille kuitenkin riittää ratkaisuksi Infix-komento, joka ei enää muuta lukujen (eikä merkkijonojen) suuruusjärjestystä FactorInteger-komennon antamasta listasta:

n=30!;
Infix[(f /@ FactorInteger[n]),"×"]

n=50!;
Infix[(f /@ FactorInteger[n]),"×"]

Harjoituksia

10	Kertaa Lauseen 1.7 (Aritmetiikan peruslause) alkuosan todistus:
	Jokainen kokonaisluku  a ≥ 2  voidaan esittää tekijöiden järjestystä 
	lukuunottamatta alkulukujen  (Subscript[p, i])  tulona muodossa  a = (∏_i)(Subscript[p, i]^(Subscript[e, i])),  (Subscript[e, i])∈ℕ.
	Yksikäsitteisyyden todistusta ei tässä siis nyt vaadita.

Etätehtävät kappaleeseen 1

1.  Jaollisuus

1.1  Tekijöihin jako

1  	Onko kokonaisluku  19  seuraavien kokonaislukujen tekijä?
	a)  57		b)  –95		c)  209		d)  10001

2  	Etsi seuraavien kokonaislukujen kaikki tekijät.
	a)  57		b)  71		c)  100		d)  1024

1.2  Jakoalgoritmi

3	Suorita jakolasku  543 : 21  ja kirjoita tulos jakoyhtälönä muodossa
	jaettava =  vaillinainen osamäärä  kertaa  jakaja  plus  jakojäännös,
	ts. muodossa 	a = q b + r,  0≤ r < |b |,  missä  a = 543,  b = 21,
	q = vaillinainen osamäärä  ja  r = jakojäännös.

4 	Muunna 10–järjestelmän luku  511  
	a)  binääriluvuksi  
	b)  8–kantaiseen järjestelmään 
	c)  esitä luku  (Subscript[1234, 7])  10–järjestelmän lukuna

5  	Muuta luku 10–järjestelmän luku  2358  
	a)  binääriluvuksi
	b)  7–kantaiseen järjestelmään

1.3  Alkuluvut

6	Osoita, että  113  on alkuluku.

7	Mitä tarkoittavat seuraavat tulomuodot?
	
	a)  (((∏_(i=1)^4) i)^( 3))	b)  (((∏_(i=1)^n) i)^( ))	c)  (((∏_(i=1)^k) (1/(i^2)))^( ))	d)  (((∏_(i=2)^n) (1-(1/i)))^( ))

8	Todista hieman eri tavalla (tai kertaa ajatuksella) Lause 1.2 (Eukleides): Alkulukuja on ääretön määrä.

1.4–5  Suurin yhteinen tekijä ja pienin yhteinen jaettava. Aritmetiikan peruslause.

9	Laske Esimerkin 1.2 tavalla  syt(a, b)  ja  pyj(a, b),  kun
	
	a = (3^2)·(5^3)·(7^4)  ja  b = (2^4)·(3^3)·(7^2).   
 
	Totea näille luvuille, että  syt(a,b) · pyj(a,b) = ab.

10	Kertaa Lauseen 1.7 (Aritmetiikan peruslause) alkuosan todistus:
	Jokainen kokonaisluku  a ≥ 2  voidaan esittää tekijöiden järjestystä 
	lukuunottamatta alkulukujen  (Subscript[p, i])  tulona muodossa  a = (∏_i)(Subscript[p, i]^(Subscript[e, i])),  (Subscript[e, i])∈ℕ.
	Yksikäsitteisyyden todistusta ei tässä siis nyt vaadita.

2.  Eukleideen algoritmi

2.1  Suurimman yhteisen tekijän tehokas laskutapa

Tässä luvussa tarkastellaan annettujen lukujen suurimman yhteisen tekijän etsimistä tehokkaalla tavalla.  Erinomaisen käyttökelpoinen menetelmä on Eukleideen algoritmi, joka on ikivanha, mutta ei vähääkään vanhanaikainen laskutapa. Nykyisen tietotekniikan aikakautena sen merkitys sovelluksissa on vain entisestään kasvanut.

Olkoot  a  ja  b  positiivisia kokonaislukuja ja  a≥b.  Kirjoitetaan luku  a  jakoalgoritmin mukaiseen muotoon   a=q b+r,  0≤r<b,  (ks. Lause 1.1).  Jokainen lukujen  a  ja  b  yhteinen tekijä, sanokaamme  t,  on luvun  b  ja jakojäännöksen  r = a-q b  yhteinen tekijä – ja myös päinvastoin.  Todellakin,  jos  a = t a'  ja   b = t b',  missä  t, a', b' ∈ (SubPlus[ℤ]),  niin 

(2.1)	 r = a-q b = (t a') – q (t b') = t (a' – q b'),

ts.  t  on luvun  r  tekijä – ja oletuksen mukaan myös luvun  b   tekijä. 

Toisaalta, jos  b = t b'  ja  r = t r',  missä  t, b', r' ∈ (SubPlus[ℤ]),  niin  

(2.2)	a = q b + r = q (t b') + (t r') = t (q b' + r'),  

ts.  t  on luvun  a  tekijä – ja oletuksen mukaan myös luvun  b   tekijä. 

Merkitään  d = syt(a,b).  Edellä nähdyn nojalla  d | b  ja  d | r,  joten  d | syt(b,r).  Vastaavasti, kuten kohdassa (2.2) nähtiin, syt(b,r) | syt(a,b),  joten   

	d = syt(a,b) = syt(b,r),   kun  a=q b+r,  0≤r<b.

Jos  r=0  (ja siis a=q b),  saadaan tulos  syt(a,b)=b.  Olkoon  r ≠ 0.  Jatketaan nyt samalla tavalla lukujen  b  ja  r  kanssa. Kirjoitetaan siis  a = (Subscript[q, 1])b+(Subscript[r, 1]), b=(Subscript[q, 2]) (Subscript[r, 1])+(Subscript[r, 2]),  missä  0≤(Subscript[r, 2])<(Subscript[r, 1]).  Vastaavasti kuten edellä nähdään, että  syt(a,b)=syt(b,(Subscript[r, 1]))=syt((Subscript[r, 1]),(Subscript[r, 2])).  Jatketaan menettelyä kunnes toinen argumentti  (Subscript[r, n-1])  on ensimmäisen argumentin  (Subscript[r, n-2])  tekijä (näin käy lopulta, koska  (Subscript[r, 1]) > (Subscript[r, 2]) > (Subscript[r, 3]) > ⋯ > (Subscript[r, n-2]) > (Subscript[r, n-1]) > (Subscript[r, n ]) = 0).  Luku  (Subscript[r, n-1])  on täsmälleen etsitty lukujen  a  ja  b  suurin yhteinen tekijä, ts.  (Subscript[r, n-1]) = syt(a, b). Tämä algoritmi on nimeltään Eukleideen algoritmi  (Euclid's Algorithm)  ja se on erittäin nopea tapa laskea  syt(a, b).  Huomattavaa on, että  syt(a,b)  löytyy ilman lukujen  a  ja  b  tekijöihinjakoa (jota suurten lukujen kyseessä ollen voi käytännössä olla mahdotonta löytää, ks. RSA-haasteluvut vuoteen 2007 saakka – käytä netissä hakusanaa: The RSA Challenge Numbers).

Algoritmi 2.1	 	Yksinkertainen Eukleideen algoritmi  

	syöte		a, b  positiivisia kokonaislukuja,  a ≥ b
	while   b>0  do  	begin
				 aseta  r = jakojäännös, kun a on jaettu luvulla b
				 (siis  r  saadaan jakoyhtälöstä  a=q b+r, 0≤r<b)
				 aseta  a=b
				 aseta  b=r
			           end
	tulosta   a

Käyttämällä Mathematica-funktioita While, Floor ja Print, yllä esitetty algoritmi voidaan ohjelmoida seuraavasti. Viimeinen nollasta eroava jakojäännös on sama kuin Algoritmin 2.1 lopussa tulostama luku  a,  joka puolestaan on syötteenä annettujen lukujen suurin yhteinen tekijä:

a=2345;b=987;
While[b≠0, r=a-Floor[a/b]*b;{a,b}={b,r};Print[{a,b}]]

Tämä algoritmi voitaisiin implementoida myös näin:

Clear[f];
f[{a_,b_}]:={b,r=a-Floor[a/b]*b};

NestWhileList[f,{2345,987},Last[#]≠0&]

Tarkastellaan vielä kahta yksityiskohtaista esimerkkiä.

Esimerkki 2.1
Laske lukujen  129  ja  15  suurin yhteinen tekijä.  

Ratkaisu.
Käytetään jakoyhtälöä  a=q b+r, 0≤r<b,  toistuvasti. Lisäksi  syt(a,b)=syt(b,r)=syt(r,r') = ... .

Siispä Eukleideen algoritmin toiminta näyttää seuraavalta:

({{129, "=", 8, "*", 15, "+", 9          syt(129,15) = syt(15,9)}, {15, "=", 1, "*", 9, "+", 6          syt(15,9) = syt(9,6)}, {9, "=", 1, "*", 6, "+", 3          syt(9,6) = syt(6,3)}, {6, "=", 2, "*", 3, "+", 0          syt(6,3) = syt(3,0) = 3}, {"", "", "", "", "", "", ""}})

Viimeinen nollasta eroava jakojäännös = 3 = syt(129, 15).

Esimerkki 2.2
Laske lukujen  2345  ja  123  suurin yhteinen tekijä.  

Ratkaisu.
Tässä saadaan tulokseksi  syt = 1.  Tämä tulos löydetään Eukleideen algoritmilla seuraavasti:

({{2345, "=", 19, "*", 123, "+", 8}, {123, "=", 15, "*", 8, "+", 3}, {8, "=", 2, "*", 3, "+", 2}, {3, "=", 1, "*", 2, "+", 1}, {2, "=", 2, "*", 1, "+", 0}, {"", "", "", "", "", "", ""}})

Viimeinen nollasta eroava jakojäännös = 1 = syt(2345, 123).

Harjoituksia

11 (a)	Määritä  d = syt(1233, 63).  Välivaiheet tulee merkitä selkeästi näkyviin

Tätä harjoitusta jatketaan vielä seuraavassa kohdassa 2.2 (esitä d  muodossa  d = s 1233 + t 63,  missä  s, t ∈ ℤ).

12 (a)  	Määritä  syt(2333, 187).  

Tätä harjoitusta jatketaan vielä seuraavassa kohdassa 2.2 (esitä d  muodossa  d = s 2333 + t 187,  missä  s, t ∈ ℤ).

2.2  Lineaarikombinaatio  syt(a,b)=u a+v b

Salakirjoituksissa lasketaan usein hyvin suurten lukujen, sanokaamme  a,  jakojäännöksillä - modulo jokin luku  b.  Tällaisten suurten lukujen  a  käänteisluvuilla (modulo  b)  on ensiarvoisen keskeinen merkitys, kuten tullaan näkemään.  Lauseen 1.4 mukaan on olemassa kertoimet  u ja v ∈ ℤ  joiden avulla  syt(a, b) voidaan esittää muodossa   syt(a,b)=u a+v b.  Siinä tapauksessa, että  syt(a, b) = 1,  kuten oli edellä Esimerkissä 2.2, tälle lineaarikombinaatiolle pätee  u a + v b = 1.  Tällöin saadaan  u a = (–v) b + 1,  ts.  u a ≡ 1 (modulo b)  ja siis  u = (a^(-1)) (modulo b).  Näin ollen lineaarikombinaatiota 1 = syt(a,b)=u a+v b  voidaan suoraan käyttää hyväksi käänteisalkioiden  (a^(-1)) (modulo b)  laskemisessa. Edellä esiintynyt merkintä  x≡y (mod m)  tarkoittaa, että  m  jakaa kokonaislukujen  x  ja  y  erotuksen  x-y,  ts.  x - y = q m,  eräälle  q ∈ ℤ.  Tällöin sanotaan, että  x  ja  y  ovat keskenään kongruentteja modulo  m.  Kongruensseja käsitellään laajemmin Kappaleessa 3.

Kun Lauseen 1.4 mukaiset kertoimet  u ja v  halutaan löytää, ts. esittää  syt(a, b)  muodossa    syt(a,b)=u a+v b,  voidaan Algoritmia 2.1  muuntaa alla esitetyllä tavalla. Huomaa, että jättämällä pois symboleja  (Subscript[u, i])  ja  (Subscript[v, i])  sisältävät rivit, tämä (laajennettu) algoritmi palautuu yksinkertaiseen Eukleideen algoritmiin, jossa 

 syt(a,b)=syt((Subscript[r, -1]),(Subscript[r, 0]))=syt((Subscript[r, 0]),(Subscript[r, 1]))=syt((Subscript[r, 1]),(Subscript[r, 2]))=…=syt((Subscript[r, n-1]),(Subscript[r, n]))=syt((Subscript[r, n-1]),0)=(Subscript[r, n-1]).

Algoritmin 2.2 oikeellisuuden todistus löytyy Liitteestä 1, jossa esitetään yksityiskohtaiseisesti tähän suoraviivaiseen tapaan johtavat tarkastelut. Liitteessä 1 nähdään lisäksi, että jakoalgoritmin tuottama jakojäännös  (Subscript[r, i])  voidaan esittää jokaisella askeleella muodossa  (Subscript[u, i]) a + (Subscript[v, i]) b.  Viimeisen jakojäännöksen  (Subscript[r, n])  ollessa nolla, on viimeinen nollasta eroava jakojäännös  (Subscript[r, n-1])  juuri etsitty lineaarikombinaatio  d = syt(a,b)=(Subscript[r, n-1])=u a+v b.  Algoritmi todistetaan matemaattisella induktiolla ja siitä esitetään käsinlaskuesimerkkejä. Liitteestä 1 löytyvät myös perustelut matriisien kertolaskun käytölle lineaarikombinaation laskemisessa. Lisäksi liitteestä 1 löytyy kaikki välivaiheet esittävä Mathematica-ohjelma, jota Mathematica-ympäristön käyttäjät voivat kokeilla. Tuon ohjelman voi myös muuttaa jossakin toisessa ohjelmointiympäristössä toimivaksi koodiksi.

Algoritmi 2.2		Laajennettu Eukleideen algoritmi 

	syöte		a≥b>0
	alkuarvot	(Subscript[r, -1])=a; (Subscript[r, 0])=b;
			  (Subscript[u, -1])=1; (Subscript[u, 0])=0; (Subscript[v, -1]) =0; (Subscript[v, 0]) =1;n=0;
	while  (Subscript[r, n])>0  do  begin
					  aseta  	n=n+1;
				   tulosta	(Subscript[r, n-2])=(Subscript[q, n])(Subscript[r, n-1])+(Subscript[r, n]),  (Subscript[r, n-1]) > (Subscript[r, n]) ≥ 0;
				   aseta 	(Subscript[u, n])=(Subscript[u, n-2])-(Subscript[q, n]) (Subscript[u, n-1]);
				   aseta 	(Subscript[v, n])=(Subscript[v, n-2])-(Subscript[q, n]) (Subscript[v, n-1]);
				end
	aseta	 u=(Subscript[u, n-1]); v= (Subscript[v, n-1]);

(2.2) 	syt(a,b)=(Subscript[r, n-1])=u a+v b

Todistus: 
Katso Liite 1 (Laajennettu Eukleideen algoritmi – suoraviivainen tapa).

□

Vaikka lukijaa kannustetaankin perehtymään Liitteeseen 1, emme vaadi tällä salakirjoitusten peruskurssilla siinä esitettyjä perusteluja hallittavaksi loppukokeessa. Esitämme nyt kuitenkin yhden esimerkin tuossa liitteessä kirjoitetun laajennettuEukleides-ohjelman toiminnasta (vrt. Esimerkki 2.1 yllä):

laajennettuEukleides[129, 15]

Lasketaan tämä lineaarikombinaatio nyt käsin toisella, aluksi ehkä helpommalla, tavalla. Ainakin tämä alhaalta ylöspäin etenevä laskutapa tulee hallita. Siis jompikumpi tapa kuuluu kurssin keskeisiin vaatimuksiin. Tavan - suoraviivainen ylhäältä alas (yllä), tai alhaalta ylös (alla) - voi valita itse sen mukaan kumpi tuntuu luontevalta.

Esimerkki 2.3
Laske lukujen  129  ja  15  suurin yhteinen tekijä ja esitä se muodossa  u*129 + v*15.
Esimerkissä 2.1 laskimme jo, että viimeinen nollasta eroava jakojäännös = 3 = syt(129, 15).  Toistamme tässä vielä nämä laskut:

({{(rivi 1)           129, "=", 8, "*", 15, "+", 9}, {(rivi 2)           15, "=", 1, "*", 9, "+", 6 }, {(rivi 3)           9, "=", 1, "*", 6, "+", 3}, {(rivi 4)           6, "=", 2, "*", 3, "+", 0}, {"", "", "", "", "", "", ""}})

Lähdemme nyt liikkeelle riviltä 3, jossa on viimeinen nollasta eroava jakojäännös (syt = 3).  Saadaan:

	3 = 9 - 1*6	(rivi 3)

Nyt riviltä 2 saadaan ratkaistuksi edeltävä jakojäännös  6 = 15 - 1*9.   Sijoittamalla tämä laskematon lauseke  (15 - 1*9)  luvun  6  paikalle yllä, saadaan:

	3 	=  9 - 1*6 			(rivi 3)
		=  9 - 1*(15 - 1*9) 		(rivi 2)
		=  -1*15 + 2*9		(sievennys)
	
Riviltä 1 saadaan jakojäännös   9 = 129 - 8*15.  Sijoittamalla lauseke (129 - 8*15)  luvun  9  paikalle edellä saatuun viimeiseen muotoon, saadaan:

	3	=  9 - 1*6 			(rivi 3)
		=  9 - 1*(15 - 1*9) 		(rivi 2)
		=  -1*15 + 2*9 		(sievennys)
		=  -1*15 + 2*(129 - 8*15)	(rivi 1)
		=  2*129 + (-17)*15		(sievennys)
	   
Siis kysytty lineaarikombinaatio on   3 = syt(129, 15) = u a + v b = 2*129 + (-17)*15.

Huomattakoon vielä, että yllä sievennys tarkoitti sitä, että kootaan yhteen (so. esitetään yhden kertoimen avulla) jatkossa ylemmiltä riveiltä löytyvät jakojäännökset  (3, 6, 9)  tai luvut  b  ja  a  (15, 129).  Esitettyjä kertolaskuja ei tule laskea loppuun, koska silloin menetettäisiin lausekkeiden rakenne. Laskemisen kannalta näitä lukuja käsitellään siis symboleina tai merkkijonoina. Samaa ajattelutapaa kannattaa käytää myös, jos kirjoittaa tämän algoritmin ohjelman muotoon symbolisen laskennan ohjelmointiympäristössä.

Esimerkki 2.4
Laske lukujen  2345  ja  123  suurin yhteinen tekijä ja esitä se muodossa  u*2345 + v*123.
Esimerkissä 2.2 laskimme jo, että viimeinen nollasta eroava jakojäännös = 1 = syt(2345, 123).  Toistamme vielä nämä laskut:

({{(rivi 1)            2345, "=", 19, "*", 123, "+", 8}, {(rivi 2)            123, "=", 15, "*", 8, "+", 3}, {(rivi 3)            8, "=", 2, "*", 3, "+", 2}, {(rivi 4)            3, "=", 1, "*", 2, "+", 1}, {(rivi 5)            2, "=", 2, "*", 1, "+", 0}, {"", "", "", "", "", "", ""}})

Laskemme nyt kysytyn lineaarikombinaation seuraavasti:

	1	=  3 - 1*2 				(rivi 4)
		=  3 - 1*(8 - 2*3) 			(rivi 3)
		=  -1*8 + 3*3 				(sievennys)
		=  -1*8 + 3*(123 - 15*8)		(rivi 2)
		=  3*123 - 46*8			(sievennys)
		=  3*123 - 46*(2345 - 19*123)	(rivi 1)
		=  -46*2345 + (3 + (-46)(-19))*123 	(sievennys)
		=  -46*2345 + 877*123 		(sievennys)
	   
Siis kysytty lineaarikombinaatio on   1 = syt(2345, 123) = u a + v b = (-46)*2345 + 877*123.

Mathematicassa tämä laajennettu Eukleideen algoritmi on standardi funktio ExtendedGCD.  Lukujen suuruusjärjestyksestä käyttäjän ei tarvitse huolehtia:

a=963; b=4320; ExtendedGCD[a,b]

Todellakin  9 = syt(963, 4320) = –157*963 + 35*4320.

Harjoituksia

11	Määritä  syt(1233, 63)  (ks. T11(a)) ja esitä se muodossa  s 1233 + t 63,  missä  s, t ∈ ℤ.
	Välivaiheet tulee merkitä selkeästi näkyviin. Huom.  syt(1233, 63)  laskettiin aiemmin tehtävässä 11(a).

12  	Määritä  syt(2333, 187)  ja esitä se muodossa  s 2333 + t 187,  missä  s, t ∈ ℤ. 
 	Huom.  syt(2333, 187)  laskettiin aiemmin tehtävässä 12(a).

12'  	Lisäharjoitus. Valitse itse luvut  a  ja  b.  Laske valitsemillasi luvuilla d = syt(a, b)  
	ja esitä  d  muodossa  d = s a + t b,  missä  s, t ∈ ℤ.

2.3  Eukleideen algoritmin kompleksisuus

Päätetään tämä kappale  Eukleideen algoritmin  kompleksisuuden tarkasteluun. Olkoon  a >b ≥ 1.  Verrataan algoritmin toiminnan nopeutta luvun  b  arvoon.  Algoritmin toiminta on hitaimmillaan silloin, kun jakojäännös  (Subscript[r, k])  pienenee kussakin askeleessa  (Subscript[r, k-2])=(Subscript[q, k])(Subscript[r, k-1])+(Subscript[r, k])  mahdollisimman vähän.  Tällaiseen tilanteeseen joudutaan, jos  (Subscript[r, k-2])=(Subscript[r, k-1])+(Subscript[r, k])  aina kun  2≤k≤n-1,  ts. jos jokaisella askeleella (ensimmäistä askelta  a = (Subscript[q, 1])b  + (Subscript[r, 1])  lukuunottamatta) osamäärä  (Subscript[q, k])  saa arvon  1 – edellyttäen, että se on ylipäätään mahdollista.  Tällöin on myös voimassa  (Subscript[r, n-2])=2(Subscript[r, n-1]),  kun  (Subscript[r, n])=0.  Toisin sanoen, sellainen luvun  a  pienin arvo  (a >b ≥ 1),   jolle syt(a,b):n laskeminen vie  n-2  askelta  (so. riviä) saadaan, kun  a=(Subscript[F, n])  ja  b=(Subscript[F, n-1]),  missä jono  (Subscript[((Subscript[F, i])), i≥0])  on kuuluisa Fibonacci-lukujono,  joka määritellään asettamalla  (Subscript[F, 0])=0, (Subscript[F, 1])=1  ja  (Subscript[F, i+2])=(Subscript[F, i+1])+(Subscript[F, i])   aina kun  i≥0.  Jonon alku on siis:  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... .

Alla Mathematican toiminta kohdistuu toistuvasti listoihin, jotka koostuvat kahdesta peräkkäisestä Fibonacci-luvusta (tässä käytetään  Nest-funktiota). Näin saadaan menetelmä Fibonacci-lukujen laskemiseksi. Tässä  esimerkissä lasketaan  (Subscript[F, 99])  ja  (Subscript[F, 100]),  jotka ovat jo hyvin suuria lukuja:

f[{u_,v_}]:={v,u+v}
n=99;Nest[f,{0,1},n]

Voidaan käyttää myös Mathematican sisäänrakennettua funktiota: Fibonacci.

Fibonacci[100]

Tarkastellaan vielä yllä esitettyä analyysiä kirjoittamalla Mathematicalla funktio sytIteroinnit.  Siinä käytetään jakojäännöksen laskemiseen valmista funktiota  Mod:

sytIteroinnit[n_Integer?Positive, m_Integer?Positive] := Module[ { a=n, b=m, r, t=0},							While[ b > 0,r = Mod[a,b];{a,b,t}={b,r,t+1}]; t]

n=100;
sytIteroinnit[Fibonacci[n],Fibonacci[n-1]]

Siis tosiaankin syt(a,b):n laskeminen vie tapauksessa  n = 100  juuri nuo aiemmin mainitut n-2  askelta, kun  a=(Subscript[F, n])  ja  b=(Subscript[F, n-1]).

Kokeillaan vielä tapausta  n = 10.  Tässäkin tapauksessa Eukleideen algoritmin toiminta päättyy  8  askeleessa, ts. tarvitaan 8 riviä.  Tässä Fibonacci-luvut ovat seuraavat:

{Fibonacci[10],Fibonacci[9]}

Eukleideen algoritmi päättyy rivillä numero  8:

({{(rivi 1)           55, "=", 1, "*", 34, "+", 21}, {(rivi 2)           34, "=", 1, "*", 21, "+", 13}, {(rivi 3)           21, "=", 1, "*", 13, "+", 8}, {(rivi 4)           13, "=", 1, "*", 8, "+", 5}, {(rivi 5)           8, "=", 1, "*", 5, "+", 3}, {(rivi 6)           5, "=", 1, "*", 3, "+", 2}, {(rivi 7)           3, "=", 1, "*", 2, "+", 1}, {(rivi 8)           2, "=", 2, "*", 1, "+", 0}, {"", "", "", "", "", "", ""}})

Asettamalla (Subscript[F, n])=c (f^n) Fibonacci-lukujen määrittelyrelaatiossa (Subscript[F, i+2])=(Subscript[F, i+1])+(Subscript[F, i]), saadaaan (f^2)=f+1, jonka nollakohdat ovat: ((1±(Sqrt[5]))/2). Esitetään ilman todistusta seuraava yläraja Eukleideen algoritmin kompleksisuudelle. Se voidaan todistaa induktiolla luvun  a  suhteen (erottelemalla tapaukset  b≤(a/f)  ja  (a/f)<b <a).

Lause 2.3  Eukleideen algoritmin  kompleksisuus 
Olkoot  a  ja  b  positiivisia kokonaislukuja,  a >b ≥ 1  ja olkoon  f=((1 + (Sqrt[5]))/2).  Tällöin  Eukleideen algoritmin tarvitsema iteraatioiden lukumäärä  syt(a, b):n  laskemiseksi on korkeintaan  1 + (Subscript[log, f])b.

Testataan tätä vielä yhdellä suhteellisen suurella luvun  b  arvolla:

a=Fibonacci[1000]; b=Fibonacci[999];
sytIteroinnit[a,b]
Ceiling[Log[(1+Sqrt[5])/2 ,b]]

Ja vielä yhdellä suhteellisen pienellä luvun  b  arvolla:

a=Fibonacci[1000]; b= 100;
sytIteroinnit[a,b]
Ceiling[Log[(1+Sqrt[5])/2 ,b]]

Alkuperäisessä Mathematica Notebookissa on mukana automaattisesti alustettavia laskentakoodeja, joista alla on esimerkkinä funktio Eukleides. Tässä etsitään Fibonacci-lukujen suurinta yhteistä tekijää:

Eukleides[ a = Fibonacci[30], b = Fibonacci[29] ]

Käytännössä Eukleideen algoritmi toimii yleensä paljon nopeammin, kuin mitä Lauseen 2.3 yläraja antaisi aiheen odottaa.

Etätehtävät kappaleeseen 2

2.  Eukleideen algoritmi

2.1–2	Suurimman yhteisen tekijän tehokas laskutapa 
	ja lineaarikombinaatio  syt(a,b)=u a+v b

11	Määritä  syt(1233, 63)  ja esitä se muodossa  s 1233 + t 63,  missä  s, t ∈ ℤ.
	Välivaiheet tulee merkitä selkeästi näkyviin

12  	Määritä  syt(2333, 187)  ja esitä se muodossa  s 2333 + t 187,  missä  s, t ∈ ℤ.

12'  	Lisäharjoitus. Valitse itse luvut  a  ja  b.  Laske valitsemillasi luvuilla d = syt(a, b)  
	ja esitä  d  muodossa  d = s a + t b,  missä  s, t ∈ ℤ.

Automaattisesti alustettavat laskentakoodit (Eukleides ja laajennettuEukleides)

Clear[f];
f[{a_,b_}]:=If[a≥b,{a,"=",Floor[a/b],"*",b,"+",a-Floor[a/b]*b},
f[{b,a}]];
f[{a_,_,_,_,b_,_,r_}]:=Module[{myPr=""},If[r==0,Print["\nTässä syt = ",b,".","\n\nTulos nähdään Eukleideen algoritmilla seuraavasti:\n"];myPr,{b,"=",Floor[b/r],"*",r,"+",b-Floor[b/r]*r}]];

Clear[Eukleides];
Eukleides[a_,b_]:=(
Print[(steps=Rest[NestWhileList[f,{a,b},(#=!= "")&]])//TableForm];Print["Viimeinen nollasta eroava jakojäännös = ",
Last[steps[[Length[steps]-2]]]," = syt(",a,", ", b,")."]
)

Clear[jako];
jako[{a_,b_}]:=If[a≥b,
Print[(Subscript[r, -1]),"=",a,"=", (Subscript[q, 1]),"*",(Subscript[r, 0]),"+",(Subscript[r, 1]),"=",Floor[a/b],"*",b,"+",a-Floor[a/b]*b,";  ",(Subscript[r, 1]),"=",a-Floor[a/b]*b,"=",(Subscript[u, 1]),"a +",(Subscript[v, 1]),"b"," = ","(",1-0,")*",a," + (",0-Floor[a/b],")*",b];
{1,a, Floor[a/b], b, a-Floor[a/b]*b,{0,1},1-0,a,0-Floor[a/b],b} (* = {indeksi=n=1,(Subscript[r, -1]),(Subscript[q, 1]),(Subscript[r, 0]),(Subscript[r, 1]),{(Subscript[u, 0]),(Subscript[v, 0])},(Subscript[u, 1])=(Subscript[u, -1])-(Subscript[q, 1])*(Subscript[u, 0]),a,(Subscript[v, 1])=(Subscript[v, -1])-(Subscript[q, 1])*(Subscript[v, 0]),b} *),
jako[{b,a}]];
jako[{n_,r1_,q3_,r2_,r3_,{u2_,v2_},u3_,a_,v3_,b_}]:=Module[{i,q4,r4,u4,v4,nextStep},If[r3==0,"",
(q4=Floor[r2/r3];r4=r2-q4*r3;u4=u2-q4*u3;v4=v2-q4*v3;nextStep={i=n+1,r2,q4,r3,r4,{u3,v3},u4,a,v4,b};Print[(Subscript[r, i-2]),"=",r2,"=", (Subscript[q, i]),"*",(Subscript[r, i-1]),"+",(Subscript[r, i]),"=",q4,"*",r3,"+",r4,";  ",(Subscript[r, i]),"=",r4,"=",(Subscript[u, i]),"a +",(Subscript[v, i]),"b"," = ","(",u4,")*",a," + (",v4,")*",b];
nextStep)]];

Clear[laajennettuEukleides];
laajennettuEukleides[a_,b_]:=(Print["Laajennettu Eukleideen algoritmi toimii seuraavasti:"];
Print["a = ",Max[a,b],", b = ",Min[a,b]];
lastRelevantStep=NestWhile[jako,{a,b},(#=!= "")&,1,Infinity,-2];Print["Viimeinen nollasta eroava jakojäännös = ",lastRelevantStep[[5]]," = syt(",a,", ", b,")."];
Print["Lineaarikombinaatio:  ",lastRelevantStep[[5]]," = u a + v b = ","(",lastRelevantStep[[7]],")*",Max[a,b]," + (",lastRelevantStep[[9]],")*",Min[a,b],"."];);

Kokeillaan syt(a,b) :n laskemista ensin Eukleideen perusalgoritmilla ilman lineaarikombinaatiota. Tällöin laskelmien rakenne on yksinkertainen.

Eukleides[34527,18273645]

laajennettuEukleides[34527,18273645]

Tarkistuslaskelmia luvuilla  a  ja  b  sekä tuloksena saaduilla luvuilla  u  ja  v:

lastRelevantStep  
(* siis {i,(Subscript[r, i-2]),(Subscript[q, i]),(Subscript[r, i-1]),(Subscript[r, i]),{(Subscript[u, i-1]),(Subscript[v, i-1])},(Subscript[u, i]),a,(Subscript[v, i]),b}, kun i = n-1 *)

Print["Lineaarikombinaatio  u a + v b = ","(",lastRelevantStep[[-4]],")*",lastRelevantStep[[-3]]," + (",lastRelevantStep[[-2]],")*",lastRelevantStep[[-1]],"  tuottaa sievennettynä luvun:"];

lastRelevantStep[[-4]]*lastRelevantStep[[-3]]+lastRelevantStep[[-2]]*lastRelevantStep[[-1]]

Tämäkin on oikein.

3.  Kongruenssit

3.1  Jakojäännös ja kongruenssi

Tässä kappaleessa esitellään kokonaislukujen modulaarinen aritmetiikka (ns. kellotauluaritmetiikka), jossa luvut tyypillisesti korvataan niillä jakojäännöksillä, jotka saadaan kun luku jaetaan tietyllä vakiolla (ns. moduluksella). Nämä rakenteet ovat keskeisiä salausmenetelmille ja käytössä tästä eteenpäin koko opintojakson ajan (myös Osassa 2).

Määritelmä 3.1
Kaksi lukua  a ja b  ovat keskenään kongruentteja (tai  a  on kongruentti luvun  b  kanssa)  modulo  m,  jos  m  jakaa niiden erotuksen  a-b,  ts.  a - b = q m,  eräälle  q ∈ ℤ.  Tätä merkitään kirjoittamalla

					a≡b (mod m).
				
Luku  m  on nimeltään modulus.

Jakoalgoritmin (Lause 1.1) mukaan luvut  a  ja  b  voidaan esittää yksikäsitteisesti muodossa  (Subscript[ a =(Subscript[q, 1]) m+r, 1])  ja  (Subscript[ b =(Subscript[q, 2]) m+r, 2]),  0≤ (Subscript[r, 1]),(Subscript[r, 2])<m.   Tässä  a-(Subscript[r, 1])=(Subscript[q, 1]) m  ja   b- (Subscript[r, 2]) =(Subscript[q, 2]) m,  joten Määritelmän 3.1 nojalla luku  a  on kongruentti jakojäännöksen  (Subscript[r, 1])  kanssa ja luku  b  jakojäännöksen  (Subscript[r, 2])  kanssa.  Toisin sanoen on voimassa  

	a≡(Subscript[r, 1]) (mod m)   ja   b≡(Subscript[r, 2]) (mod m),
	
missä  (Subscript[r, 1])  ja  (Subscript[r, 2])  ovat ko. jakojäännökset modulo  m.

Lisäksi  

(3.1)	a≡b (mod m)  jos ja vain jos jakojäännökset  (Subscript[r, 1])  ja  (Subscript[r, 2])  ovat samat.  

Perustellaan (3.1) käyttäen edellä esitettyjä merkintöjä seuraavasti:

	           a≡b (mod m) 
	⇔       a - b = q m 
	 ⇔	((Subscript[ (Subscript[q, 1]) m+r, 1]))  –  ((Subscript[ (Subscript[q, 2]) m+r, 2])) = q m
	⇔	(Subscript[r, 1]) – (Subscript[r, 2]) = (q – (Subscript[q, 1])+ (Subscript[q, 2])) m	(tässä kerroin  (q – (Subscript[q, 1])+ (Subscript[q, 2])) ∈ ℤ)
	⇔      (Subscript[r, 1]) – (Subscript[r, 2]) = 0 		       (koska  0≤ (Subscript[r, 1,])(Subscript[r, 2])<m)
	⇔      (Subscript[r, 1]) = (Subscript[r, 2])
	
Näin ollen  a≡b (mod m)  täsmälleen silloin, kun luvuilla  a  ja  b  on sama jakojäännös modulo  m.

Mathematica-funktio  Mod[a,m]  antaa jakoalgoritmin (Subscript[ a =(Subscript[q, 1]) m+r, 1])  mukaisen jakojäännöksen  (Subscript[r, 1])  modulo  m.

Esimerkki 3.1

a=36; m=17; Mod[a,m]

a=17015; m=17; Mod[a,m]

Todellakin  36 = 2*17 + 2  ja  17015 = 1000*17 + 15.

□

Seuraavassa esimerkissä testataan ovatko kaksi suurehkoa lukua  a  ja  b  keskenään kongruentteja modulo m ( = 17):

Esimerkki 3.2

m=17; a=3456789; b=34567894; 
Mod[a-b,m]==0  (* vp == op palauttaa arvon True jos vp ja op ovat samat *)

Vastauksena saatiin siis, että nämä luvut  a = 3456789  ja  b = 34567894  todella ovat kongruentteja keskenään modulo  m = 17,  ts.  a≡b (mod m).  Näin on koska jakojäännös on = 0,  kun  a - b  jaetaan luvulla  m = 17  (ks. Määritelmä 3.1).  Osoittautuu, että tässä tapauksessa  a - b = -1830065*17.

Tarkistetaan vielä toisella tavalla, että lukujen  a  ja  b  jakojäännökset ovat samat, kun ne jaetaan luvulla  m = 17:

Mod[a,17]
Mod[b,17]

Molemmat jakojäännökset ovat siis = 9.  Vielä voidaan laskemalla todeta, että  a  =  203340*17 + 9  ja  b = 2033405*17 + 9.

□

Yleisesti jakojäännökset  (mod  m)  ovat  0, 1, 2, ...,  m - 1.  Jokainen kokonaisluku on siis kongruentti (mod m) täsmälleen yhden luvun   0, 1, 2, ...,  m - 1  kanssa.  Kuten aiemmin kohdassa (3.1) todettiin,  a≡b (mod m)  täsmälleen silloin, kun luvuilla  a  ja  b  on sama jakojäännös  r  (mod  m).

Harjoituksia

13	Mitkä seuraavista kongruensseista ovat tosia?

	a)	19 ≡ 1 (mod 9)
	b)	19 ≡ –8 (mod 9)
	c)	18 ≡ 0 (mod 9) 
	d)	29 ≡–2 (mod 9)

14	Osoita, että  a≡b (mod m)  täsmälleen silloin, kun kokonaisluvuilla  
	a  ja  b  on sama jakojäännös modulo  m.

3.2  Jäännösluokka

Kokonaislukujen joukon  ℤ  alkiot jakautuvat erillisiin luokkiin siten, että samaan luokkaan kuuluvat luvut ovat kongruentteja keskenään (mod m) - toisin sanoen niillä on sama jakojäännös (mod m).

Määritelmä 3.2  (Jäännösluokka)
Luvun  a  määräämä jäännösluokka (mod m), merkitään  [a],  on joukko

	[a] 	= { x∈ℤ |  x≡a (mod m) }
		= { x∈ℤ |  x-a  = q m, q∈ℤ }
		= { x∈ℤ |  x=a  + q m, q∈ℤ }.

Esimerkki 3.3
Jäännösluokat (mod 2) ovat 

	[0]	= { x∈ℤ |  x≡0 (mod 2) }
		= { x∈ℤ |   x-0  = q 2,  q∈ℤ }
		= { x∈ℤ |   x= 2 q, q∈ℤ }
		= parilliset kokonaisluvut
	
	[1]	= { x∈ℤ |  x≡1(mod 2) }
		= { x∈ℤ |   x-1  = q 2,  q∈ℤ }
		= { x∈ℤ |   x= 2 q +1, q∈ℤ }
		= parittomat kokonaisluvut

Jäännösluokkia (mod m) on  m  kappaletta ja ne ovat esimerkiksi  [0], [1], ..., [m-1].  Huomaa, että  [m] = [0], [m+1] = [1],  jne.  Lisäksi on voimassa:  

	[a] = [b]   ⟺   a≡b (mod m).

Esimerkki 3.4
Tarkastellaan kokonaislukujen jakautumista jäännösluokkiin modulo 5.  Tässä tarvitsee kiinnittää huomio ainoastaan jakojäännökseen. Viidellä jaolliset luvut  ..., -10, -5, 0, 5, 10, ...  muodostavat jäännösluokan  [0],  koska niiden jakojäännös on nolla. Niiden lukujen esiintymistä lukusuoralla, joiden jakojäännös on  2,  ts. jotka muodostavat jäännösluokan  [2],  on hahmoteltu alla: 

	({{...,, -9,, -8,, -7,, -6,, -5,, -4,, -3,, -2,, -1,, 0,, 1,, 2,, 3,, 4,, 5,, 6,, 7,, 8,,  9,, 10,, 11,, 12,, 13,, ...}, {..., ., [2], ., ., ., ., [2], ., ., ., ., [2], ., ., ., ., [2], ., ., ., ., [2], ., ...}})

Kaikkiaan on viisi erilaista jäännösluokkaa. Ne ovat seuraavat:

	[0] 	= { ..., -10, -5, 0, 5, 10, ... }
	[1] 	= { ..., -9, -4, 1, 6, 11, ... }
	[2] 	= { ..., -8, -3, 2, 7, 12, ... }
	[3] 	= { ..., -7, -2, 3, 8, 13, ... }
	[4] 	= { ..., -6, -1, 4, 9, 14, ... }

Määritelmä 3.3
Jäännösluokkien (mod m) muodostamasta joukkosta käytetään merkintää  (Subscript[ℤ, m]).

Esimerkki 3.5

	(Subscript[ℤ, 2])	=  {[0], [1]}			jakojäännökset (mod 2) ovat 0 ja 1
		(Subscript[ℤ, 3])	=  {[0], [1], [2]}		jakojäännökset (mod 3) ovat 0, 1 ja 2
		(Subscript[ℤ, 4])	=  {[0], [1], [2], [3]}		jakojäännökset (mod 4) ovat 0, 1, 2 ja 3

Harjoituksia

15	Tarkastellaan kokonaislukujen jakautumista jäännösluokkiin modulo 4, ts.
	tarkastellaan joukkoa  (Subscript[ℤ, 4]) =  {[0], [1], [2], [3]}.  Esitä Esimerkin 3.4 tavalla, 
	mitkä luvut kuuluvat seuraaviin jäännösluokkiin.
	 
	a)  [0] 		b)  [1]		c)  [2] 		d)  [3].

3.3  Täydellinen jäännössysteemi

Määritelmä 3.4
Kokonaislukujen joukko  {(Subscript[a, 1]),(Subscript[a, 2]),…,(Subscript[a, m])} (m kpl)  on täydellinen jäännössysteemi (complete residue system) modulo  m,  jos jokainen kokonaisluku on kongruentti täsmälleen yhden alkion  (Subscript[a, i]),  1≤i≤m,  kanssa modulo  m.  Ts. joukko  {(Subscript[a, 1]),(Subscript[a, 2]),…,(Subscript[a, m])} on saatu ottamalla yksi luku kustakin  (Subscript[ℤ, m]):n alkiosta.

Yleisimmin käytettyjä täydellisiä jäännössysteemejä modulo  m  ovat joukot  {0,1,… ,m-1}  ja  {1,2,…,m}  (yhtä hyvin voitaisiin valita esim. {m,m+1,… ,2m-1}).

Selvästi  m  kokonaislukua  (Subscript[a, i]),  1≤i≤m,  muodostavat täydellisen jäännössysteemin modulo  m  jos ja vain jos jokaista paria  (i, j),  1≤i, j≤m,  kohti pätee

(3.2)		(Subscript[a, i])≡(Subscript[a, j]) (mod m)     ⟹     i=j.

Kongruenssirelaatio  ≡  (modulo m)  määrittelee ekvivalenssirelaation (refleksiivinen, symmetrinen  ja transitiivinen relaatio) kokonaislukujen joukossa  ℤ.  Täydellinen jäännössysteemi on ekvivalenssiluokkien (m kpl) edustajien muodostama joukko.

Lemma 3.1
Olkoon   k a≡k b (mod m)  ja  syt(k,m)=d.  Tällöin

		 a≡b  (mod m/d).

Todistus:  Kirjoitetaan k=k'd  ja  m=m' d, missä  d = syt(k, m)  ja siis  syt(k',m')=1. Oletuksesta   k a≡k b (mod m)  seuraa Määritelmän 3.1 nojalla, että  k a-k b=x m,  ts.  (k'd) a-(k'd) b=x (m'd), jollekin  x∈ℤ.  Ottamalla  d ≠ 0  puolittain tekijäksi, saadaan  k'(a-b)=x m'.  Koska  syt(m',k')=1, seuraa Lemmasta 1.5, että  m'|(a-b),   ts.  a≡b (mod m').

□

Lemma 3.2
Olkoon  {(Subscript[a, 1]),(Subscript[a, 2]),…,(Subscript[a, m])}  täydellinen jäännössysteemi modulo  m  ja olkoon  syt(k,m)=1.
Tällöin  {k (Subscript[a, 1]),k (Subscript[a, 2]),…,k (Subscript[a, m])}  on myös täydellinen jäännössysteemi modulo  m.

Todistus:  Käytetään kriteeriä (3.2).  Lemman 3.1  nojalla ehdosta  k (Subscript[a, i])≡k (Subscript[a, j]) (mod m)  seuraa, että  (Subscript[a, i])≡(Subscript[a, j]) (mod m),  josta edelleen seuraa, että   i=j.

□

Harjoituksia

16	Kertaa Lemman 3.1 todistus:  Olkoon   k a≡k b (mod m)  ja  syt(k,m)=d.  
	Tällöin	 a≡b  (mod m/d).

17	Kertaa Lemman 3.2 todistus: Olkoon  {(Subscript[a, 1]),(Subscript[a, 2]),…,(Subscript[a, m])}  täydellinen jäännössysteemi 
	modulo  m  ja olkoon  syt(k,m)=1.  Tällöin  {k (Subscript[a, 1]),k (Subscript[a, 2]),…,k (Subscript[a, m])}  on myös 
	täydellinen jäännössysteemi modulo  m.

3.4  Kongruenssien laskusääntöjä

Seuraavassa lauseessa saadaan kongruensseille mukavia laskusääntöjä. Erityisesti kohtaa 4) tarvitaan hyvin usein tässä opintojaksossa.

Lause 3.3
Olkoon  m  annettu positiivinen kokonaisluku. Kongruenssi (mod m) toteuttaa seuraavat ehdot:
1)	a ≡ a (mod m)   							(refleksiivisyys)
2)	Jos  a ≡ b (mod m),  niin  b ≡ a (mod m) 				(symmetrisyys)
3)	Jos  a ≡ b (mod m)  ja  b ≡ c (mod m),  niin  a ≡ c (mod m)		(transitiivisuus)

4)	Jos  a ≡ b (mod m),  c ≡ d (mod m),  r ∈ ℤ  ja  n ∈ (SuperPlus[ℤ]),  niin seuraavat kongruenssit ovat voimassa:

	(i)	(a ± c) ≡ (b ± d)  (mod m)
	(ii)	r a ≡ r b (mod m)
	(iii)	a c ≡ b d (mod m)
	(iv)	(a^n) ≡ (b^n) (mod m)

5)	Jos 	k a ≡ k b (mod m)  ja  syt(k, m) = 1,  niin  a ≡ b (mod m).

Todistus:
1)  Koska  a – a = 0 = 0 · m,  niin määritelmän nojalla  a ≡ a (mod m).

2)  Jos  a ≡ b (mod m),  niin  m | a – b,  ts.  a – b = k·m  (k ∈ ℤ).  Siis  b – a = (–k)·m,  
      ts.  m | b – a,  ts.  b ≡ a (mod m). 

3)  Jos  a ≡ b (mod m)  ja  b ≡ c (mod m),  niin eräille  k, l  ∈ ℤ  pätee
	
	a – b = k·m    ja   b – c = l·m.   
 
     Nyt  a – c = (a – b) + (b – c) = ( k + l )·m,  joten  a ≡ c (mod m).

4)  Olkoon  a ≡ b (mod m),  c ≡ d (mod m),  r ∈ ℤ  ja  n ∈ (SuperPlus[ℤ]).  Tällöin eräille  k, l  ∈ ℤ  pätee

	a – b = k·m   ja   c – d = l·m.

     (i) 	Meillä on  (a ± c) – (b ± d) = (a – b) ± (c – d) = k ·m ± l·m = ( k ± l )·m,  ja siis
     	(a ± c) ≡ (b ± d)  (mod m).
     	
     (ii)  Tässä  r a – r b = r·(a – b) = r·(k ·m) = (r·k)·m,  ja siis r a ≡ r b (mod m).
     
     (iii)	Edelleen  a = b + k·m   ja   c = d + l·m.
	 Näin ollen  ac = (b + k·m)(d + l·m) = bd + (bl + kd + klm)·m,  joten
	ac – bd = (bl + kd + klm)·m,  ja siis  a c ≡ b d (mod m).
	 		
     (iv)	Kun  n = 1,  on oletuksen  a ≡ b (mod m)  nojalla  (a^n) = (a^1)= a ≡ b = (b^1) = (b^n) (mod m).
     	Tehdään induktio-oletus, että  (a^k) ≡ (b^k) (mod m),  ts. oletetaan, että väite on tosi, 
     	kun  n = k.  Valitaan nyt kohdassa (iii)  c = (a^k)  ja  d = (b^k).  Tällöin kohdan (iii) ja 
     	induktio-oletuksen nojalla saadaan:  (a^(k+1))= a((a^k)) = ac ≡ bd = b((b^k)) = (b^(k+1)) (mod m).
     	Näin ollen väite on induktioperiaatteen nojalla tosi aina kun  n ∈ (SuperPlus[ℤ]).

5)  Tulos seuraa suoraan Lemmasta 3.1, koska tässä tapauksessa on  d = syt(k,m) = 1.

□

Kun  [a]  ja  [b]  ∈ (Subscript[ℤ, m]),  voidaan määritellä 

	 	[a] + [b]  =  [a+b]
(3.3)	 
	  	[a]·[b]  =  [a·b]

Osoitetaan, että nämä yhteen- ja kertolaskuoperaatiot ovat hyvin määriteltyjä, toisin sanoen laskutoimitukset kohdassa (3.3) ovat riippumattomia jäännösluokkien edustajista.

Todistus:  Edustakoot  (Subscript[a, 1])  ja  a  keskenään samaa jäännösluokkaa, samoin  (Subscript[b, 1])  ja  b.   Tällöin siis  [(Subscript[a, 1])] = [a]  ja  [(Subscript[b, 1])] = [b],  ts.  (Subscript[a, 1]) ≡ a (mod m)  ja  (Subscript[b, 1]) ≡ b (mod m).  Lauseen 3.3 (kohta 4) nojalla 

	 (Subscript[a, 1])+(Subscript[b, 1]) ≡ a+b (mod m)
	 (Subscript[a, 1])·(Subscript[b, 1]) ≡ a·b (mod m).

Näin ollen  
	
	[(Subscript[a, 1])+(Subscript[b, 1])] = [a+b]
	[(Subscript[a, 1])·(Subscript[b, 1])] = [a·b] 
	
ja siis

	[(Subscript[a, 1])] + [(Subscript[b, 1])] (Overscript[=, (Määr. 3.1)]) [(Subscript[a, 1])+(Subscript[b, 1])] = [a+b] (Overscript[=, (Määr. 3.1)]) [a] + [b]

	[(Subscript[a, 1])]·[(Subscript[b, 1])] (Overscript[=, (Määr. 3.1)]) [(Subscript[a, 1])·(Subscript[b, 1])] = [a·b] (Overscript[=, (Määr. 3.1)]) [a]·[b] .

Täten laskutoimitukset kohdassa (3.3) ovat riippumattomia jäännösluokkien edustajista ja määritely kohdassa (3.3) on ristiriidattomasti tehty.

□

Esimerkki 3.6
Esitetään jäännösluokkien avulla joukkojen  (Subscript[ℤ, 2])  ja  (Subscript[ℤ, 5])  yhteen- ja kertolaskutaulut:


 (Subscript[ℤ, 2]):		({{+, |, [0], [1]}, {-, |, -, -}, {[0], |, [0], [1]}, {[1], |, [1], [0]}})					({{·, |, [0], [1]}, {-, |, -, -}, {[0], |, [0], [0]}, {[1], |, [0], [1]}})	
 

 
 (Subscript[ℤ, 5]):		({{+, |, [0], [1], [2], [3], [4]}, {-, |, -, -, -, -, -}, {[0], |, [0], [1], [2], [3], [4]}, {[1], |, [1], [2], [3], [4], [0]}, {[2], |, [2], [3], [4], [0], [1]}, {[3], |, [3], [4], [0], [1], [2]}, {[4], |, [4], [0], [1], [2], [3]}})			({{·, |, [0], [1], [2], [3], [4]}, {-, |, -, -, -, -, -}, {[0], |, [0], [0], [0], [0], [0]}, {[1], |, [0], [1], [2], [3], [4]}, {[2], |, [0], [2], [4], [1], [3]}, {[3], |, [0], [3], [1], [4], [2]}, {[4], |, [0], [4], [3], [2], [1]}})

Esimerkki 3.7
Ratkaise joukossa  (Subscript[ℤ, 5]) = {[0], [1], [2], [3], [4]}  yhtälö  [3] x + [2] = [4].

Ratkaisu:    	[3] x + [2] = [4]  			|  + [3]

	⟺	[3] x + [2] + [3] = [4] + [3]  		|  Tässä  [2] + [3]  = [5] = [0]   ja  [4] + [3] = [7] = [2].

	⟺	[3] x + [0] = [2]  	

	⟺	[3] x = [2]  	
	
Edellisen Esimerkin 3.6 kertotaulun neljännen rivin mukaisesti on jäännösluokalla [3]  kerrottaessa voimassa: 
	
		({{·, |, [0], [1], [2], [3], [4]}, {-, |, -, -, -, -, -}, {[3], |, [0], [3], [1], [4], [2]}})
	
Näin ollen  [3] ·[4] = [2],  toisin sanoen  [3] x = [2]  täsmälleen silloin kun  x = [4].

Huomautus
Olkoon  m  anettu positiivinen kokonaisluku. Kirjallisuudessa luvun  a ∈ ℤ  edustamasta jäänösluokasta  [a] ∈ (Subscript[ℤ, m])  käytetään myös merkintää (Subscript[[a], m]).  Usein käytetään myös lyhyempiä alle- tai päälleviivausmerkintöjä  a  tai  (Overscript[a, -])  (modulo m).  Kun jäännösluokilla lasketaan jatkuvasti, eikä sekaannuksen vaaraa ole, voidaan pelkällä luvulla merkitä sen edustamaa jäännösluokkaa.  Siis esimerkiksi näin:  

(3.4)		4 + 4 = 3   (mod 5).

Tämän salakirjoituskurssin Osassa 2 onkin usein käytännöllistä laskea kuten kohdassa (3.4).

Tässä osassa kuitenkin merkitsemme mieluummin näin:

		4 + 4 = 8 ≡ 3   (mod 5)
		
tai näin:

		[4] + [4] = [8] = [3]   (mod 5).

Esimerkki 3.8
Etsi jakojäännös, kun 		

a)	(2^2002)	jaetaan luvulla  5
b)	(3^3003)	jaetaan luvulla  6
c)	(5^4004)    jaetaan luvulla  11 
d)	44( (2^200) + (3^3333))    jaetaan luvulla  7

Ratkaisu:	Käytetään Lauseen 3.3 kohtaa 4).

a)   	Lasketaan aluksi kantaluvun  2  perättäisiä potensseja.
	Tässä esimerkissä tulos saadaan hyvinkin helposti.

	(2^2) = 4 ≡ –1 (mod 5)
	(2^2002) = ((((2^2)))^1001) ≡ (((–1))^1001) =  –1 ≡ 4 (mod 5)
	
	Jakojäännos on siis 4.
	
	Saman tuloksen voisi myös laskea esimerkiksi seuraavasti, 
	jos ei halua käyttää negatiivisia lukuja laskuissa.
	Sillä käyttääkö negatiivisia vai positiivisia lukuja, 
	ei sinäänsä ole merkitystä, kunhan vain luvut ovat kongruentteja keskenään.
	
	(2^2) = 4 (mod 5)   
	(2^3) = 2·(2^2) = 2·4 = 8 ≡ 3 (mod 5)  
	Huomaa, että yllä moduluksen 5  lisääminen tai vähentäminen ei vaikuta kongruenssiin. Miksi?

	(2^4) = 2·(2^3) ≡ 2·3 = 6 ≡ 1 (mod 5)
	Nyt saadaan
	(2^2002) = (2^(2+4·500)) = (((2^2)·((2^4)))^500) ≡ (((–1))^2)·(1^500) =  –1 ≡ 4 (mod 5)	
	
	Jakojäännös on siis 4  kuten aluksi jo totesimmekin.

b)   	(3^2) = 9 ≡ 3 (mod 6)
	(3^3) = 3·(3^2) ≡ 3·3 ≡ 3 (mod 6)
	Koska  (3^n) = 3·(3^(n-1)),  näemme induktiivisesti, että  (3^n) ≡ 3 (mod 6).
	Siis  (3^3003) ≡ 3 (mod 6).
	
	Jakojäännös on 3.

c)	Lasketaan aluksi kantaluvun  5  perättäisiä potensseja.

	(5^2) = 25 ≡ 3 (mod 11)
	(5^3) = 5·(5^2) ≡ 5·3 = 15 ≡ 4 (mod 11)
	(5^4) = 5·(5^3) ≡ 5·4 = 20 ≡ 9 ≡ –2 (mod 11)
	(5^5) = 5·(5^4) ≡ 5·(–2) = –10 ≡ 1 (mod 11)
	Nyt saadaan
	(5^4004) = (5^(4+5·800)) = (5^4)·(5^(5·800)) = (5^4)·((((5^5)))^800) ≡ 9·(1^800) = 9 (mod 11) 
	
	Jakojäännös on 9.

d) 	Tässä siis  44( (2^200) + (3^3333))    jaetaan luvulla  7.

	44 = 6·7 + 2 ≡ 2 (mod 7)
	
	(2^3) ≡ 1 (mod 7)
	(2^200) = (2^(2+3·66)) = (2^2)·(2^(3·66)) = (2^2)·((((2^3)))^66) ≡ (2^2)·(((1))^66) = 4·1 = 4 (mod 7)
	
	(3^3)= 27 ≡ 6 ≡ –1 (mod 7)
	(3^3333) = ((((3^3)))^1111)≡ (((–1))^1111) ≡ –1 (mod 7) 
	
	Siis  44( (2^200) + (3^3333)) ≡ 2(4 –1) = 2·3 = 6 (mod 7) .
	
	Jakojäännös on 6.

Harjoituksia

18	Kertaa Lauseen 3.3 kohdan 4 (iii) todistus: Olkoon  m  annettu positiivinen kokonaisluku, 
	a ≡ b (mod m)  ja  c ≡ d (mod m).  Tällöin  a c ≡ b d (mod m).

19	Esitä joukkojen  (Subscript[ℤ, 8])  ja  (Subscript[ℤ, 9])  yhteen- ja kertolaskutaulut.

20	Ratkaise joukossa  (Subscript[ℤ, 7]) = {[0], [1], [2], [3], [4], [5], [6]}  yhtälö  [2] x + [3] = [4].

21	Etsi jakojäännös, kun

	a)	(10^515)	jaetaan luvulla  7	(5)
	b)	(8^391)	jaetaan luvulla  5	(2)
	c)	(7^348)	jaetaan luvulla  11	(9)
	d)	(3^323)   	jaetaan luvulla  7	(5)
	e)	127·((10^515)+(3^323))    jaetaan luvulla  7   (3)

	Laske sopivasti jakojäännöksillä ja merkitse kaikki välivaiheet näkyviin.
	Oikea vastaus on merkitty valmiiksi sulkeiden sisään.

22	Etsi jakojäännös, kun

	a)	(2^203)	jaetaan luvulla  5	(3)
	b)	(3^4567)	jaetaan luvulla  6	(3)
	c)	55·( (2^203) + (3^4567))    jaetaan luvulla  7   (0)

	Laske sopivasti jakojäännöksillä ja merkitse välivaiheet näkyviin.
	Oikea vastaus on tässäkin merkitty valmiiksi sulkeiden sisään.

23	Oletetaan tunnetuksi tulos  P(b) ≡ P(c) (mod m),  kun  
	P(x) = (Subscript[a, 0])(x^n) + (Subscript[a, 1])(x^(n-1)) + ⋯ + (Subscript[a, n-1])x + (Subscript[a, n]);  (Subscript[a, i]) ∈ ℤ;  ja  b ≡ c (mod m).  
	Olkoon lisäksi  q  n-numeroinen kokonaisluku ja sen peräkkäiset numerot  
	(Subscript[a, 1]), (Subscript[a, 2]), ... , (Subscript[a, n]);  (Subscript[a, i]) ∈ {0, 1, ... , 9}.  Osoita, että  9 | q  jos ja vain jos  
	9 | ((Subscript[a, 1]) + (Subscript[a, 2]) + ⋯ + (Subscript[a, n])).  Onko luku  987654321  jaollinen 9:llä?

Etätehtävät kappaleeseen 3

3.  Kongruenssit

3.1  Jakojäännös ja kongruenssi

13	Mitkä seuraavista kongruensseista ovat tosia?

	a)	19 ≡ 1 (mod 9)
	b)	19 ≡ –8 (mod 9)
	c)	18 ≡ 0 (mod 9) 
	d)	29 ≡–2 (mod 9)

14	Osoita, että  a≡b (mod m)  täsmälleen silloin, kun kokonaisluvuilla  
	a  ja  b  on sama jakojäännös modulo  m.

3.2  Jäännösluokka

15	Tarkastellaan kokonaislukujen jakautumista jäännösluokkiin modulo 4, ts.
	tarkastellaan joukkoa  (Subscript[ℤ, 4]) =  {[0], [1], [2], [3]}.  Esitä Esimerkin 3.4 tavalla, 
	mitkä luvut kuuluvat seuraaviin jäännösluokkiin. 
	a)  [0] 		b)  [1]		c)  [2] 		d)  [3].

3.3  Täydellinen jäännössysteemi

16	Kertaa Lemman 3.1 todistus:  Olkoon   k a≡k b (mod m)  ja  syt(k,m)=d.  
	Tällöin	 a≡b  (mod m/d).

17	Kertaa Lemman 3.2 todistus: Olkoon  {(Subscript[a, 1]),(Subscript[a, 2]),…,(Subscript[a, m])}  täydellinen jäännössysteemi 
	modulo  m  ja olkoon  syt(k,m)=1.  Tällöin  {k (Subscript[a, 1]),k (Subscript[a, 2]),…,k (Subscript[a, m])}  on myös 
	täydellinen jäännössysteemi modulo  m.

3.4  Kongruenssien laskusääntöjä

18	Kertaa Lauseen 3.3 kohdan 4 (iii) todistus: Olkoon  m  annettu positiivinen kokonaisluku, 
	a ≡ b (mod m)  ja  c ≡ d (mod m).  Tällöin  a c ≡ b d (mod m).

19	Esitä joukkojen  (Subscript[ℤ, 8])  ja  (Subscript[ℤ, 9])  yhteen- ja kertolaskutaulut.

20	Ratkaise joukossa  (Subscript[ℤ, 7]) = {[0], [1], [2], [3], [4], [5], [6]}  yhtälö  [2] x + [3] = [4].

21	Etsi jakojäännös, kun

	a)	(10^515)	jaetaan luvulla  7	(5)
	b)	(8^391)	jaetaan luvulla  5	(2)
	c)	(7^348)	jaetaan luvulla  11	(9)
	d)	(3^323)   	jaetaan luvulla  7	(5)
	e)	127·((10^515)+(3^323))    jaetaan luvulla  7	  (3)

	Laske sopivasti jakojäännöksillä ja merkitse kaikki välivaiheet näkyviin.
	Oikea vastaus on merkitty valmiiksi sulkeiden sisään.

22	Etsi jakojäännös, kun

	a)	(2^203)	jaetaan luvulla  5	(3)
	b)	(3^4567)	jaetaan luvulla  6	(3)
	c)	55·( (2^203) + (3^4567))    jaetaan luvulla  7	  (0)

	Laske sopivasti jakojäännöksillä ja merkitse välivaiheet näkyviin.
	Oikea vastaus on tässäkin merkitty valmiiksi sulkeiden sisään.

23	Oletetaan tunnetuksi tulos  P(b) ≡ P(c) (mod m),  kun  
	P(x) = (Subscript[a, 0])(x^n) + (Subscript[a, 1])(x^(n-1)) + ⋯ + (Subscript[a, n-1])x + (Subscript[a, n]);  (Subscript[a, i]) ∈ ℤ;  ja  b ≡ c (mod m).  
	Olkoon lisäksi  q  n-numeroinen kokonaisluku ja sen peräkkäiset numerot  
	(Subscript[a, 1]), (Subscript[a, 2]), ... , (Subscript[a, n]);  (Subscript[a, i]) ∈ {0, 1, ... , 9}.  Osoita, että  9 | q  jos ja vain jos  
	9 | ((Subscript[a, 1]) + (Subscript[a, 2]) + ⋯ + (Subscript[a, n])).  Onko luku  987654321  jaollinen 9:llä?

4.  Eulerin ja Fermat'n lauseet

4.1  Alkuluokka ja Eulerin φ-funktio

Yleensä olemme kiinnostuneita vain niistä jäännösluokista modulo  m,  joiden alkiot ovat suhteellisia alkulukuja luvun  m  kanssa.  Näiden luokkien lukumäärä esitetään Eulerin  φ-funktion arvona.

Määritelmä 4.1
Jäännösluokka  [a]  (mod m)  on alkuluokka  (mod m),  jos  syt(a, m) = 1.    
Kaikkien alkuluokkien (mod m)  joukolle käytetään merkintää  (Subscript[ℤ, m]^( * )).
Siis  
		(Subscript[ℤ, m]^( * )) = {[a]∈ (Subscript[ℤ, m]) | syt(a, m) = 1}.

Määritelmä 4.2
Eulerin φ-funktio  (Euler's Totient Function)  antaa arvonaan kokonaisluvun

	φ(m)=card( {  0≤i<m | syt(i,m)=1 } ).

Siis  φ(m)  ilmaisee, montako luvuista  0, 1, ..., m-1  on suhteellisia alkulukuja luvun  m  suhteen, ts.  φ(m)  on joukon  (Subscript[ℤ, m]^( * ))  alkioiden lukumäärä. Itse asiassa, aina kun  m ≥ 2,  luvun  0  voi jättää pois (syt(0, m) = m) ja tarkastella vain lukuja  1, ...,  m-1.

Huomaa, että  φ(1) = card( { 0 ≤ i < 1 | syt(i, 1) = 1 } )  = 1,  koska syt(0,1) = 1.  Vastaavasti  φ(0) = card( {} ) = 0.

Mathematicalla  φ(m)  voidaan laskea EulerPhi[m] -funktion avulla. Esimerkiksi

m=15; EulerPhi[m]

Vastaavat suhteelliset alkuluvut luvun  m = 15  kanssa ovat: 1, 2, 4, 7, 8, 11, 13 ja 14.  Myöhemmin näemme, kuinka funktio  φ(m)  voidaan efektiivisesti laskea.

Lause 4.1
Kaikille positiivisille kokonaisluvuille  m   on voimassa:

				(∑_(d|m))φ(d)=m.

Merkintä  (∑_(d|m)) φ(d)  tarkoittaa yllä sitä, että muodostetaan jokaiselle luvun  m  jakajalle, ts.  m:n tekijälle,  arvo  φ(d)  ja lasketaan kaikkien näin saatujen  arvojen  φ(d)  summa.

Tarkastellaan vielä esimerkin avulla, mitkä kokonaisluvuista välillä  [1, m]  ovat niitä, jotka tuottavat Lauseen 4.1 summaan ko. termin  φ(d),  missä d|m.  Olkoon  m=15.  Tällöin jakajat ovat  1, 3, 5 ja 15.  Ne kahdeksan lukua (huom. φ(15)=8),  joiden suurin yhteinen tekijä luvun 15 kanssa on 1,  ovat  1, 2, 4, 7, 8, 11, 13 ja 14.  Neljällä  (=φ(5))  luvulla  (3, 6, 9, 12)  on syt=3 (luvun 15 kanssa), kahdella (=φ(3)) luvulla (5, 10) on  syt=5  ja yhdellä  (=φ(1))  luvulla (0)  on syt=15.

Siis tässä      	(∑_(d|m))φ(d)	=  φ(15) + φ(5) + φ(3) + φ(1) 
				=  φ(1) + φ(3) + φ(5) + φ(15) 
				=  1 + 2 + 4 + 8 
				=  15.

Lauseen 4.1 Todistus (1. tapa – lyhyt, mutta kunnon keskittymistä vaativa tarkastelu):

On siis osoitettava, että  (∑_(d|m))φ(d)=m  aina kun  m ∈ (SubPlus[ℤ]). 

Oletetaan, että  d | m.  Kirjoittamalla r=i d  näemme, että niiden kokonaislukujen  r,  0≤r<m,  missä  syt(r,m) =d,  lukumäärä on sama kuin lukujen  i,  missä  0≤i<(m/d)  ja  syt(i,(m/d))=1,  lukumäärä.  Tämä luku on Määritelmän 4.2 mukaan  φ((m/d)).

Toisaalta,  d = syt(r,m) | m  kaikilla kokonaisluvuilla r,  0≤r<m.  Siis  (∑_(d|m))φ((m/d))=m.  Tämä on ekvivalenttia sen kanssa, mikä oli todistettavana.

□

Todistus (2. tapa – pitempi, mutta tarkka ja ehkä valaiseva perustelu):
Olkoon   S = { (d, f) |   d|m,  1 ≤ f ≤ d,  syt(f, d) = 1 }.  Esimerkiksi tapauksessa  m = 12  joukkoa  S  esittää seuraava taulukko, jossa viimeiset numerot rivissä  d  tarkoittavat niiden lukujen  f   lukumäärää väliltä  1 ≤ f ≤ d,  joille syt(f, d) = 1,  ts.  kyseessä  ovat arvot  φ(d). 

({{(Subscript[,         (d^(  ((\)^(  f))))]),  |, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, |, φ(d)}, {   ---, |, -, -, -, -, -, -, -, -, -, -, -, -, |, ----    }, {1, |, 12,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , |, 1}, {2, |, 6,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , |, 1}, {3, |, 4, 8,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , |, 2}, {4, |, 3,  , 9,  ,  ,  ,  ,  ,  ,  ,  ,  , |, 2}, {6, |, 2,  ,  ,  , 10,  ,  ,  ,  ,  ,  ,  , |, 2}, {12, |, 1,  ,  ,  , 5,  , 7,  ,  ,  , 11,  , |, 4}, {   ---, -, -, -, -, -, -, -, -, -, -, -, -, -, -, ----    }, { ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , |, 12}})
 
Tapauksessa  m = 15  joukkoa  S  esittää taulukko:
 
 ({{(Subscript[,         (d^(  ((\)^(  f))))]),  |, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, |, φ(d)}, {   ---, |, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, |, ----    }, {1, |, 15,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , |, 1}, {3, |, 5, 10,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , |, 2}, {5, |, 3, 6, 9, 12,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , |, 4}, {15, |, 1, 2, " ", 4, " ", " ", 7, 8, " ", " ", 11, " ", 13, 14,  , |, 8}, {   ---, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, -, ----    }, { ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , |, 15}})
 
Joukon   S  määrittelyn nojalla  |S| = (∑_(d|m))φ(d).  Lauseen 4.1 todistamiseksi tulee osoittaa, että  |S| = m.  (Huom. |S| ≡ card(S))

Konstruoidaan bijektio  β: S -> (Subscript[ℕ, m]),  missä  (Subscript[ℕ, m]) = {1, 2, ..., m}.  Olkoon pari  (d, f) ∈ S  annettu. Määritellään

	β(d, f)  =  f·m / d.
	
Yllä olevassa taulukossa rivin  d  ja sarakkeen  f  risteyksessä oleva luku on nimenomaan tämä  β(d, f).  Koska  d|m,  niin arvot  β(d, f)  ovat kokonaislukuja. Lisäksi  β(d, f) ∈ (Subscript[ℕ, m]),  koska  1 ≤ f ≤ d.

Osoitetaan, että  β: S -> (Subscript[ℕ, m])  on injektio.  Olkoon  β(d, f) = β( d', f' ).  Tällöin  f·m / d  =  f'·m / d',  josta saadaan   f·d' = f'·d.  Koska  f  ja  d  ovat suhteellisia alkulukuja, samoin kuin  f'  ja  d',  nähdään, että  d = d'  ja f = f'.  Siten  β  on injektio.

Osoitetaan, että  β: S -> (Subscript[ℕ, m])  on surjektio. Olkoon  x ∈ (Subscript[ℕ, m])  annettu.  Olkoon  (Subscript[g, x]) = syt(x, m)  ja olkoon

	(Subscript[d, x]) = m/(Subscript[g, x]), 	(Subscript[f, x]) = x/(Subscript[g, x]).

Selvästi  (Subscript[d, x])  ja  (Subscript[f, x])  ovat suhteellisia alkulukuja, muutoin on olemassa kokonaisluku  k ≥ 2,  jolle  k|(Subscript[d, x])  ja  k|(Subscript[f, x]),  ts.  (m/(k·(Subscript[g, x])))  ja  (x/(k·(Subscript[g, x])))  ∈ (SubPlus[ℕ]),  ts.  (k·(Subscript[g, x])) | m  ja  (k·(Subscript[g, x])) |  x,  mikä on ristiriita sen kanssa, että  k(Subscript[g, x]) > (Subscript[g, x]) = syt(x, m).

Siis  	β((Subscript[d, x]), (Subscript[f, x]))  =  (((Subscript[f, x])·m)/(Subscript[d, x]))  =  (((Subscript[f, x])·m)/((m/(Subscript[g, x])))) =  (Subscript[f, x])·(Subscript[g, x])  =  x.

Näin ollen  β  on surjektio.

Kaiken kaikkiaan   β: S -> (Subscript[ℕ, m])  on bijektio, joten  |S| = m.  Näin ollen Lause 4.1 on tosi.  □

Harjoituksia

24	Määritä alkuluokat modulo  m,  ts. joukon  (Subscript[ℤ, m]^( * ))  alkiot sekä  φ(m)  tapauksissa  
	m = 7  ja  m = 12.  Laske myös  φ(46), φ(55), φ(81)  ja  φ(144).

Lauseen 4.1 todistuksen (2. tapa) taulukkoihin liittyviä laskelmia Mathematicalla (tämän loppuosan voi halutessaan myös ohittaa)

Clear[myBeta,myBetaWithGCDTest];
myBeta[f_,d_,m_]:= f*m/d;
myBetaWithGCDTest[f_,d_,m_]:=If[GCD[f,d]==1∧ f≤d,myBeta[f,d,m]," "]

m = 15;
d =1;
Print["d = ",d];
Table[{f,myBetaWithGCDTest[f,d,m]},{f,1,d}]

m = 15;
d =3;
Print["d = ",d];
Table[{f,myBetaWithGCDTest[f,d,m]},{f,1,m}]//Transpose

m = 15;
d =5;
Print["d = ",d];
Table[{f,myBetaWithGCDTest[f,d,m]},{f,1,m}]//Transpose

m = 15;
d =15;
Print["d = ",d];
Table[{f,myBetaWithGCDTest[f,d,m]},{f,1,m}]//Transpose

m=12;
Clear[h];
Join [{{"d\\f",":",Range[m]}//Flatten},
{Table[–,{m+2}]},
Table[If[Mod[m,d]==0,{d,":",Table[{myBetaWithGCDTest[f,d,m]},{f,1,m}]},h[]]//Flatten,{d,1,m}] //DeleteCases[#,_h]&]

Clear[myTableForPhi];
myTableForPhi[m_]:=(
Clear[h];
Join [{{"d\\f",":",Range[m]}//Flatten},
{Table[–,{m+2}]},
Table[If[Mod[m,d]==0,{d,":",Table[{myBetaWithGCDTest[f,d,m]},{f,1,m}]},h[]]//Flatten,{d,1,m}] //DeleteCases[#,_h]&])

myTableForPhi[15]

myTableForPhi[25]

myTableForPhi[13]

Seuraava Mathematican perusfunktioista rakennettu funktio laskee yhteen funktion  f  arvot  f[d],  missä  d  käy läpi kaikki ne arvot, jotka jakavat annetun luvun m.  (@@ on lyhennysmerkintä funktiosta Apply ja funktiosta Map (multiply apply))

DivisorSum[f_,m_]:= Plus @@ (f /@ Divisors[m])

Testataan tämän funktion avulla Lausetta 4.1.

m=15;DivisorSum[EulerPhi, m]

4.2  Supistettu jäännössysteemi

Määritelmä 4.3
φ(m)  kokonaisluvun muodostama joukko  {(Subscript[r, 1]),(Subscript[r, 2]),…,(Subscript[r, φ(m)])}  on supistettu jäännössysteemi   (reduced residue system) modulo  m,   jos jokainen kokonaisluku  j,  jolle syt(j,m)=1,  on kongruentti (täsmälleen) yhden  luvun  (Subscript[r, i])  kanssa (1≤i≤φ(m)).

Supistettu jäännössysteemi voidaan helposti generoida seuraavien funktiomäärittelyjen avulla:

CoPrimeQ[n_Integer, m_Integer] := GCD[n, m] == 1

CoPrimeQ[36,91]

CoPrimeQ[35,91]

Todellakin yllä  7 | 35  ja  7 | 91.

CoPrimes[n_Integer?Positive] := Select[ Range[n], CoPrimeQ[n, #]& ]

CoPrimes[15]

Saatu joukko on supistettu jäännössysteemi modulo 15.

Lemmaa 3.2 vastaavasti saadaan seuraava tulos:

Lemma 4.2
Olkoon  {(Subscript[r, 1]),(Subscript[r, 2]),…,(Subscript[r, ϕ(m)])}  supistettu jäännössysteemi modulo  m  ja olkoon  syt(a,m)=1.
Tällöin  {a (Subscript[r, 1]),a (Subscript[r, 2]),…,a (Subscript[r, ϕ(m)])}  on myös supistettu jäännössysteemi modulo  m.

Tämän lemman avulla voidaan helposti todistaa, että supistetun jäännössysteemin jäännösluokat muodostavat ryhmän kertolaskun suhteen (multiplicative group).

4.3  Eulerin ja Fermat'n lauseet

Lause 4.3	Eulerin lause
Olkoot kokonaisluvut  a  ja  m  suhteellisia alkulukuja. Tällöin

		(a^(φ(m)))≡1 (mod m).

Voimme helposti tarkistaa tämän paikkansapitävyyttä konkreettisissa tapauksissa:

m=12345; a= 11111;
GCD[m,a]
EulerPhi[m]
Mod[a^EulerPhi[m],m]

Eksponentteihin korotukset modulo joku kokonaisluku voidaan suorittaa paljon nopeammin käyttämällä Mathematican PowerMod[a,b,m] -funktiota, joka käyttää mahdollisimman vähän sisäisiä askelia laskiessaan  (a^b) modulo m:

m=123456789; a= 1111111111;  
GCD[m,a]
PowerMod[a, EulerPhi[m], m]

Lauseen 4.3 Todistus: Olkoon {(Subscript[r, 1]),(Subscript[r, 2]),…,(Subscript[r, φ(m)])}  supistettu jäännössysteemi modulo  m.  Lemman 4.2 nojalla

(Subscript[r, 1])·(Subscript[r, 2])··· (Subscript[r, φ(m)])     ≡  (a (Subscript[r, 1]))(a (Subscript[r, 2]))···(a (Subscript[r, φ(m)]))   =    (a^(φ(m) ))· (Subscript[r, 1])·(Subscript[r, 2])··· (Subscript[r, φ(m)])      (mod m).

Koska jokainen tekijä  (Subscript[r, i])  on suhteellinen alkuluku luvun  m  suhteen, voidaan Lauseen 3.3 kohdan 5 nojalla jakaa vasemman ja oikean puolen kongruentit luvut luvulla  (Subscript[r, 1])·(Subscript[r, 2])··· (Subscript[r, φ(m)])   ( = (∏_(i=1)^(φ(m)))(Subscript[r, i]) ).  Tämän tuloksena saadaan  1≡ (a^(φ(m))) (mod m).

□

Olkoon p  alkuluku. Koska jokainen kokonaisluku i, 1≤ i<p, on suhteellinen alkuluku luvun p  suhteen, saadaan φ(p)=p-1.  Eulerin lauseen  ((a^(φ(m)))≡1 (mod m),  kun syt(a,m) = 1)  seurauksena saadaan   (a^(p-1))≡1 (mod p),   josta  edelleen Lauseen 3.3 kohdan 4 (ii) nojalla  (a^p)≡a (mod p)  aina kun  a  ei ole luvun  p  monikerta. Toisaalta  (a^p)≡a (mod p)  on triviaalisti voimassa, jos  a  on luvun  p  monikerta (koska tällöin  p | ((a^p)-a)). Saadaan siis seuraava tulos:

Lause 4.4	Fermat'n pieni lause
Olkoon  p  alkuluku ja  a  kokonaisluku, joka ei ole luvun  p  monikerta. Tällöin

		(a^(p-1))≡1 (mod p)
	
Edelleen kaikille (vapaasti valituille) kokonaisluvuille  a  on voimassa
		
		(a^p)≡a (mod p).

Yksittäistapauksissa voidaan suorittaa testausta Mathematica-funktiolla PowerMod:

Prime[10000]   (* saadaan 10000. alkuluku *)

p= 104729; a= 9999999;
PrimeQ[p]
PowerMod[a,p,p]==Mod[a,p]

Kuten olemme huomanneet,  φ(p)=p-1,  kun  p  on alkuluku. Koska täsmälleen yksi jokaisesta  p:stä (kpl) peräkkäisestä kokonaisluvusta on jaollinen luvulla  p,  saamme seuraavan vahvemman Eulerin φ-funktiota koskevan tuloksen:

Lause 4.5
Jos  p  on alkuluku ja  k ∈ (SuperPlus[ℤ]),  niin 

 		φ((p^k)) =  (p^k) – ((p^k)/p) = (p^k)(1-(1/p)).

Todistus: 
Jakojäännökset modulo  (p^k)  ovat  0, 1, 2, ..., (p^k)- 1,  joita on siis  (p^k)  kappaletta.  Näistä luvulla  p  jaollisia ovat luvut  0, p, 2p, 3p, ..., ((p^(k-1))-1)p,  joita on  ((p^(k-1))-1) + 1 = (p^(k-1))  kappaletta.  Näin ollen luvun  (p^k)  kanssa suhteellisia alkulukuja on  (p^k) - (p^(k-1)) kappaletta.  Siis  φ((p^k)) =  (p^k) - (p^(k-1)) = (p^k) – ((p^k)/p) = (p^k)(1-(1/p)).

□

Harjoituksia

25	Todista (tai kertaa ajatuksella) Lause 4.4 (Fermat'n pieni lause):  Olkoon  p  alkuluku 
	ja  a  kokonaisluku, joka ei ole luvun  p  monikerta. Tällöin

		(a^(p-1))≡1 (mod p)
	
	Edelleen kaikille (vapaasti valituille) kokonaisluvuille  a  on voimassa
		
		(a^p)≡a (mod p).

26	Osoita Fermat'n pienen lauseen nojalla, että

	a)	(2^198) ≡ 1 (mod 199)
	b)	(10^12)≡ 1 (mod 11)
	c)	(10^25) ≡ 10 (mod 11)

27	Kertaa Lauseen 4.5 todistus:  Jos  p  on alkuluku ja  k ∈ (SuperPlus[ℤ]),  niin 

 		φ((p^k)) =  (p^k) – ((p^k)/p) = (p^k)(1-(1/p)).

4.4  Eulerin funktio ja kertolaskun säilyminen

Määritelmä 4.4
Funktio  f: ℕ⟶ℕ  on kertolaskun säilyttävä (multiplicative), jos jokaiselle kokonaislukuparille  (m, n)  pätee:

		syt(m,n) =1  ⟹   f(m·n)=f(m)·f(n).

Lause 4.6
Eulerin funktio  φ(m)  on  kertolaskun säilyttävä.

Todistus (1. tapa):  Olkoon syt(m, n) = 1  ja olkoot { (Subscript[a, 1]),(Subscript[a, 2]),… ,(Subscript[a, φ(m)])} sekä  { (Subscript[b, 1]),(Subscript[b, 2]),… ,(Subscript[b, φ(n)])}  supistettuja jäännössysteemejä  modulo  m  (vastaavasti n).  Riittää osoittaa, että  φ(m)·φ(n)  kokonaislukua  n·(Subscript[a, i ])+m·(Subscript[b, j]),  1≤i≤φ(m)  ja  1≤j≤φ(n),  muodostavat supistetun jäänössysteemin modulo m·n. On suhteellisen helppo nähdä, että kokonaisluvut  n·(Subscript[a, i])+m·(Subscript[b, j]),  1≤i≤φ(m)  ja  1≤j≤φ(n),  ovat erillisiä modulo  m·n  ja että ne ovat suhteellisia alkulukuja luvun  m·n  kanssa. (Käytä Lemmaa 3.2  ja kohtaa (3.2)).

Tulee vielä todistaa, että  k,  jolle  syt(k,m·n)=1,  on kongruentti luvun  n·(Subscript[a, i])+m·(Subscript[b, j])  kanssa modulo  m·n  jollekin  1≤i≤φ(m)  ja  1≤j≤φ(n).  Koska  syt(k,m)=1  ja  syt(k,n)=1,   on Lemman 4.2 nojalla olemassa kokonaisluvut  i  ja  j,  1≤i≤φ(m)  ja  1≤j≤φ(n),  joille

k ≡ n·(Subscript[a, i]) (mod m)   ja   k ≡ m·(Subscript[b, i]) (mod n).

Tästä seuraa, että molemmat  m  ja  n  jakavat luvun  k-n·(Subscript[a, i])-m·(Subscript[b, j]),  ts.  k-n·(Subscript[a, i])-m·(Subscript[b, j]) = m·(Subscript[m, 1])  ja  k-n·(Subscript[a, i])-m·(Subscript[b, j]) = n·(Subscript[n, 1])  joillekin  (Subscript[m, 1]), (Subscript[n, 1])∈ℤ.   Koska  m·(Subscript[m, 1]) = n·(Subscript[n, 1])  ja  syt(m,n)=1,  todetaan Lemman 1.5 nojalla, että  m | (Subscript[n, 1])  ja  n | (Subscript[m, 1]),  ts.  m·n |  m·(Subscript[m, 1]) = n·(Subscript[n, 1]).  Tämä tarkoittaa sitä, että   m·n  jakaa luvun  k-n·(Subscript[a, i])-m·(Subscript[b, j]),  ts  k≡(n·(Subscript[a, i])+m·(Subscript[b, j])) mod(m·n).

□

Lauseen 4.6 Todistus (2. tapa):  Olkoon  syt(m, n) = 1.  Jakojäännökset  (mod mn)  ovat

m kpl{({{ }, { }, { }})(Overscript[(Overscript[({{ ,  ,  ,  ,  }, {0, 1, 2, ⋯, n-1}, {n, n+1, n+2, ⋯, n+(n-1)}, {2n, 2n+1, 2n+2, ⋯, 2n+(n-1)}, {⋯, ⋯, ⋯, ⋯, ⋯}, {(m-1)n, (m-1)n+1, (m-1)n+2, ⋯, (m-1)n+(n-1)}, {↑, ↑, ↑, ⋯, ↑}, {≡0(mod n), ≡1(mod n), ≡2(mod n), ⋯, ≡(n-1)(mod n)}}), ⏞]), n kpl])

Kunkin pystyrivin luvut kuuluvat samaan jäännösluokkaan (mod n)  ja kahden eri pystyrivin alkiot eri jäännösluokkiin (mod n).  Täten on  φ(n)  pystyriviä, joiden kaikki luvut ovat suhteellisia alkulukuja luvun  n  suhteen. 

Koska  syt(m,n)=1,  kunkin pystyrivin kaikki alkiot ovat keskenään epäkongruentteja (mod  m),  ts.  k n + l  ≢ k' n + l  (mod m),  sillä  k n + l  – (k' n + l ) = (k – k') n  ei ole jaollinen luvulla  m,  jos  k ≠ k',  0 ≤ k, k' ≤ m – 1. 

Kussakin pystyrivissä on siis  m  keskenään epäkongruenttia lukua (mod m).  Täten kussakin pystyrivissä on tarkalleen yksi alkio kustakin jäännösluokasta (mod m).  Edelleen jokaisessa näistä pystyriveistä on  φ(m)  lukua, jotka ovat suhteellisia alkulukuja luvun  m  suhteen. Näin ollen on  φ(n)·φ(m)  lukua, jotka ovat suhteellisia alkulukuja sekä luvun  m  että  luvun  n  suhteen.  Toisaalta näitä lukuja on  φ(m·n)  kappaletta.  Siis φ(m·n) = φ(m)·φ(n).

□

Induktiolla todistetaan, että jos luvut  (Subscript[m, 1]), (Subscript[m, 2]), ... , (Subscript[m, k])  ovat pareittain suhteellisia alkulukuja, niin   φ((Subscript[m, 1])· (Subscript[m, 2]) ⋯ (Subscript[m, k])) = φ((Subscript[m, 1]))·φ((Subscript[m, 2])) ⋯ φ((Subscript[m, k])).

Esimerkki 4.1  (Harjoitus) 
Etsi alla olevasta taulukosta kokonaisluvun  120  kaikki alkuluokat (edustajat).  Käy läpi Lauseen 4.6 todistus yksittäistapauksessa: φ(120)= φ(8·15) = φ(8)·φ(15)  = 4·8 =32. Ensimmäinen kyseeseen tuleva  sarake on tehty malliksi. Merkitse myös näkyviin poimittavien lukujen (merkitään neliöillä) edustamat alkuluokat (tai ainakin osa niistä) modulo  8   ja modulo  15.

Table[Range[0,7]+i*8,{i,0,14}]

(({{ , ↓,  , ↓,  , ↓,  , ↓}, {0, 1, 2, 3, 4, 5, 6, 7}, {8, 9, 10, 11, 12, 13, 14, 15}, {16, 17, 18, 19, 20, 21, 22, 23}, {24, 25, 26, 27, 28, 29, 30, 31}, {32, 33, 34, 35, 36, 37, 38, 39}, {40, 41, 42, 43, 44, 45, 46, 47}, {48, 49, 50, 51, 52, 53, 54, 55}, {56, 57, 58, 59, 60, 61, 62, 63}, {64, 65, 66, 67, 68, 69, 70, 71}, {72, 73, 74, 75, 76, 77, 78, 79}, {80, 81, 82, 83, 84, 85, 86, 87}, {88, 89, 90, 91, 92, 93, 94, 95}, {96, 97, 98, 99, 100, 101, 102, 103}, {104, 105, 106, 107, 108, 109, 110, 111}, {112, 113, 114, 115, 116, 117, 118, 119}}))

Lause 4.7
Olkoon  m = ((Subscript[p, 1])^(Subscript[k, 1]))·((Subscript[p, 2])^(Subscript[k, 2])) ⋯((Subscript[p, r])^(Subscript[k, r]))  luvun  m  esitys erisuurten alkulukujen  (Subscript[p, 1]), (Subscript[p, 2]), ..., (Subscript[p, r])  tulona.  Tällöin 
			φ(m)=m (1-(1/(Subscript[p, 1]))) (1-(1/(Subscript[p, 2])))⋯ (1-(1/(Subscript[p, r]))),
toisin sanoen			
			φ(m)=m(∏_(p alkuluku, p|m))(1-(1/p))

Todistus:  Yhdistä Lause 1.7 (aritmetiikan peruslause), Lause 4.5 ja Lause 4.6. Yksityiskohdat jätetään harjoitustehtäväksi.

□

Esimerkki 4.2
Lasketaan  φ(3000).  Koska  3000 = (2^3)·3 ·(5^3),  saadaan Lauseen 4.7 nojalla

		φ(3000) = 3000·(1-(1/2))·(1-(1/3))·(1-(1/5)) = 3000·(1/2)·(2/3)·(4/5) = 800.

Siis luvuista 0, 1, 2, ..., 2999  on suhteellisia alkulukuja luvun  3000  suhteen tarkalleen  800  kappaletta.  Samoin alkuluokkia (mod 3000)  on  800.

Mathematica-funktioden Length ja EulerPhi sekä aiemmin määrittelemämme CoPrimes -funktion avulla (ks. myös Apply) voidaan myös testata Lausetta 4.7:

m=100;
Length[CoPrimes[m]]
EulerPhi[m]

m*Apply[Times,Table[If[PrimeQ[i]&& IntegerQ[(m/i)],1-(1/i),1],{i,2,m}]]

Harjoituksia

28	Täydennä Esimerkin 4.1 taulukko, ts. etsi alla olevasta taulukosta kokonaisluvun  
	120  kaikki alkuluokat (edustajat).  Käy läpi Lauseen 4.6 todistus yksittäistapauksessa: 
	φ(120)= φ(8·15) = φ(8)·φ(15)  = 4·8 =32.  Ensimmäinen kyseeseen tuleva 
	sarake on tehty malliksi. Merkitse myös näkyviin poimittavien lukujen (merkitään neliöillä) 
	edustamat alkuluokat (tai ainakin osa niistä) modulo  8   ja modulo  15.

(({{ , ↓,  , ↓,  , ↓,  , ↓}, {0, 1, 2, 3, 4, 5, 6, 7}, {8, 9, 10, 11, 12, 13, 14, 15}, {16, 17, 18, 19, 20, 21, 22, 23}, {24, 25, 26, 27, 28, 29, 30, 31}, {32, 33, 34, 35, 36, 37, 38, 39}, {40, 41, 42, 43, 44, 45, 46, 47}, {48, 49, 50, 51, 52, 53, 54, 55}, {56, 57, 58, 59, 60, 61, 62, 63}, {64, 65, 66, 67, 68, 69, 70, 71}, {72, 73, 74, 75, 76, 77, 78, 79}, {80, 81, 82, 83, 84, 85, 86, 87}, {88, 89, 90, 91, 92, 93, 94, 95}, {96, 97, 98, 99, 100, 101, 102, 103}, {104, 105, 106, 107, 108, 109, 110, 111}, {112, 113, 114, 115, 116, 117, 118, 119}}))

29	Laske Esimerkin 4.2 tavalla  φ(11000).  Kuinka monta luvuista 
	0, 1, 2, ..., 10999  on suhteellisia alkulukuja luvun  11000  suhteen, 
	ts. kuinka monta alkuluokkaa on modulo 11000?

4.5  Suurien potenssien nopea laskeminen: Eulerin lause ja peräkkäiset neliöönkorotukset

Tarkastellaan kappaleen 4 lopuksi Eulerin funktion  φ  käyttämistä suurien potenssien
  
	(a^f) (mod m)  

nopeassa laskemisessa, kun  syt(a, m) = 1.  Jakoalgoritmin nojalla 

	f = q φ(m) + r,  0 ≤ r < φ(m).
	
Eulerin lauseen nojalla  (a^(φ(m)))≡1 (mod m),  joten  

	(a^f) = (a^( q φ(m)+r)) = ((((a^(φ(m)))))^q)(a^r) ≡ (a^r) (mod m).  
	
Olkoon luvun  r  binääriesitys  

	r = (Subscript[e, k])·(2^k) + (Subscript[e, k-1])·(2^(k-1)) + ⋯ + (Subscript[e, 1])·2 + (Subscript[e, 0]),  (Subscript[e, i]) ∈ {0,1},  (Subscript[e, k]) = 1.  
	
Lasketaan peräkkäisillä neliöönkorotuksilla seuraavat jäännösluokkat  [(Subscript[a, 1])], [(Subscript[a, 2])], ..., [(Subscript[a, k])] (mod m).  Edustajiksi valitaan itseisarvoltaan pienimmät mahdolliset luvut tai yksinkertaisesti jakojäännökset väliltä  0, ... , m-1:

(Subscript[a, 1]) ≡  (a^2)  (mod m) 
	(Subscript[a, 2]) ≡  ((Subscript[a, 1])^2)  (mod m)     ( ≡ ((((a^2)))^2) = (a^4) = (a^(2^2)) (mod m))
	(Subscript[a, 3]) ≡  ((Subscript[a, 2])^2)  (mod m)     ( ≡ ((((a^(2^2))))^2) = (a^((2^2)·2)) = (a^(2^3)) (mod m))
	
	⋮
	
	(Subscript[a, k]) ≡  ((Subscript[a, k-1])^2)  (mod m)     ( ≡ ((((a^(2^(k-1)))))^2) = (a^((2^(k-1))·2)) =  (a^(2^k)) (mod m)).
	
Saadaan siis  
	
	(a^f)≡ (a^r)=  (a^((Subscript[e, k])·(2^k)+(Subscript[e, k-1])·(2^(k-1))+ ⋯ + (Subscript[e, 2])·(2^2)+(Subscript[e, 1])·2+(Subscript[e, 0])))
= (a^((Subscript[e, k])·(2^k)))·(a^((Subscript[e, k-1])·(2^(k-1))))⋯ (a^((Subscript[e, 2])·(2^2)))·(a^((Subscript[e, 1])·2))·(a^(Subscript[e, 0]))
= ((((a^(2^k))))^(Subscript[e, k]))·((((a^(2^(k-1)))))^(Subscript[e, k-1]))⋯ ((((a^(2^2))))^(Subscript[e, 2]))·((((a^2)))^(Subscript[e, 1]))·(a^(Subscript[e, 0]))    (mod m), 

toisin sanoen
	
(4.1)	(a^f) ≡  ((((Subscript[a, k])))^(Subscript[e, k]))·((((Subscript[a, k-1])))^(Subscript[e, k-1]))⋯((((Subscript[a, 2])))^(Subscript[e, 2]))·((((Subscript[a, 1])))^(Subscript[e, 1]))·(a^(Subscript[e, 0]))    (mod m)

josta  (a^f) (mod m)  on nopeasti laskettavissa.

Esimerkki 4.3
Lasketaan   (17^17850989) (mod 541).  Tässä on siis kyseessä tapaus  (a^f) (mod m),  jossa  a = 17  ja  m = 541  ovat alkulukuja. Täten  syt(a, m) = 1.  Edelleen  φ(m) = 540,  f = 17850989 = 33057·540 + 209,  missä jakojäännöksen  r = 209  binääriesitys on  r = (Subscript[11010001, 2]).  Kertoimet  (Subscript[e, i]);  i = 0, 1, ..., 7 (= k);  esityksessä  r = (Subscript[e, k])·(2^k) + (Subscript[e, k-1])·(2^(k-1)) + ⋯ + (Subscript[e, 1])·2 + (Subscript[e, 0]),  ovat siis seuraavat:

	(Subscript[e, 0]) = (Subscript[e, 4]) = (Subscript[e, 6]) = (Subscript[e, 7]) = 1    ja    (Subscript[e, 1]) = (Subscript[e, 2]) = (Subscript[e, 3]) = (Subscript[e, 5]) = 0.  

Lasketaan peräkkäisillä neliöönkorotuksilla lukuja  (Subscript[a, 1]), (Subscript[a, 2]), ...  kohdan (4.1) mukaista esitystä varten:

	a   = 17				  		(Subscript[e, 0]) = 1 
	(Subscript[a, 1]) =  (a^2) = (17^2) = 289 (mod 541)  			(Subscript[e, 1]) = 0 
	(Subscript[a, 2]) =  ((Subscript[a, 1])^2) = (289^2) = 83521 ≡ 207 (mod 541)		(Subscript[e, 2]) = 0
	(Subscript[a, 3]) =  ((Subscript[a, 2])^2) ≡ (207^2) = 42849 ≡ 110 (mod 541)		(Subscript[e, 3]) = 0
	(Subscript[a, 4]) =  ((Subscript[a, 3])^2) ≡ (110^2) = 12100 ≡ 198 (mod 541)		(Subscript[e, 4]) = 1 
	(Subscript[a, 5]) =  ((Subscript[a, 4])^2) ≡ (198^2) = 39204 ≡ 252 (mod 541)		(Subscript[e, 5]) = 0
	(Subscript[a, 6]) =  ((Subscript[a, 5])^2) ≡ (252^2) = 63504 ≡ 207 (mod 541)		(Subscript[e, 6]) = 1 
	(Subscript[a, 7]) =  ((Subscript[a, 6])^2) ≡ (207^2) = 42849 ≡ 110 (mod 541)		(Subscript[e, 7]) = 1 

Nyt kohdan (4.1) ja Lauseen 3.3 (kohta 4) nojalla:

	(17^17850989) 	≡  ((((Subscript[a, 7])))^(Subscript[e, 7]))·((((Subscript[a, 6])))^(Subscript[e, 6]))⋯((((Subscript[a, 2])))^(Subscript[e, 2]))·((((Subscript[a, 1])))^(Subscript[e, 1]))·(a^(Subscript[e, 0]))
			≡  (((110))^1)·(((207))^1)·(((252))^0)·(((198))^1)·(((110))^0)·(((207))^0)·(((289))^0)·(((17))^1)
			=  110·207·1·198·1·1·1·17
			=  (110·207)·(198·17)   (voidaan ryhmitellä vaikkapa näin)
			=  22770·3366
			≡  48·120
			=  5760
			≡  350     (mod 541)

Vaikka  (17^17850989)  on erittäin suuri luku (siinä on lähes 22 miljoonaa numeroa), tarvittiin laskelmissa vain Eulerin lausetta ja  7  peräkkäistä neliöön korotusta sen selville saamiseen, että  (17^17850989) ≡ 350 (mod 541).  Matemaattisissa tietokoneohjelmissa peräkkäisten neliöönkorotusten ideaa käytetään luonnollisesti hyväksi suurten lukujen moduloaritmetiikassa.

Harjoituksia

30	Laske   (17^1785) (mod 47)  käyttämällä Eulerin lausetta ja peräkkäisiä neliöönkorotuksia.

Etätehtävät kappaleeseen 4

4.  Eulerin ja Fermat'n lauseet

4.1–3  	Alkuluokka ja Eulerin φ-funktio
	Supistettu jäännössysteemi
	Eulerin ja Fermat'n lauseet

24	Määritä alkuluokat modulo  m,  ts. joukon  (Subscript[ℤ, m]^( * ))  alkiot sekä  φ(m) tapauksissa  
	m = 7  ja  m = 12.  Laske myös  φ(46), φ(55), φ(81)  ja  φ(144).

25	Todista (tai kertaa ajatuksella) Lause 4.4 (Fermat'n pieni lause):  Olkoon  p  alkuluku 
	ja  a  kokonaisluku, joka ei ole luvun  p  monikerta. Tällöin

		(a^(p-1))≡1 (mod p)
	
	Edelleen kaikille (vapaasti valituille) kokonaisluvuille  a  on voimassa
		
		(a^p)≡a (mod p).

26	Osoita Fermat'n pienen lauseen nojalla, että

	a)	(2^198) ≡ 1 (mod 199)
	b)	(10^12)≡ 1 (mod 11)
	c)	(10^25) ≡ 10 (mod 11)

27	Kertaa Lauseen 4.5 todistus:  Jos  p  on alkuluku ja  k ∈ (SuperPlus[ℤ]),  niin 

 		φ((p^k)) =  (p^k) – ((p^k)/p) = (p^k)(1-(1/p)).

4.4  Eulerin funktio ja kertolaskun säilyminen

28	Täydennä Esimerkin 4.1 taulukko, ts. etsi alla olevasta taulukosta kokonaisluvun  
	120  kaikki alkuluokat (edustajat).  Käy läpi Lauseen 4.6 todistus yksittäistapauksessa: 
	φ(120)= φ(8·15) = φ(8)·φ(15)  = 4·8 =32.  Ensimmäinen kyseeseen tuleva 
	sarake on tehty malliksi. Merkitse myös näkyviin poimittavien lukujen (merkitään neliöillä) 
	edustamat alkuluokat (tai ainakin osa niistä) modulo  8   ja modulo  15.

(({{ , ↓,  , ↓,  , ↓,  , ↓}, {0, 1, 2, 3, 4, 5, 6, 7}, {8, 9, 10, 11, 12, 13, 14, 15}, {16, 17, 18, 19, 20, 21, 22, 23}, {24, 25, 26, 27, 28, 29, 30, 31}, {32, 33, 34, 35, 36, 37, 38, 39}, {40, 41, 42, 43, 44, 45, 46, 47}, {48, 49, 50, 51, 52, 53, 54, 55}, {56, 57, 58, 59, 60, 61, 62, 63}, {64, 65, 66, 67, 68, 69, 70, 71}, {72, 73, 74, 75, 76, 77, 78, 79}, {80, 81, 82, 83, 84, 85, 86, 87}, {88, 89, 90, 91, 92, 93, 94, 95}, {96, 97, 98, 99, 100, 101, 102, 103}, {104, 105, 106, 107, 108, 109, 110, 111}, {112, 113, 114, 115, 116, 117, 118, 119}}))

29	Laske Esimerkin 4.2 tavalla  φ(11000).  Kuinka monta luvuista 
	0, 1, 2, ..., 10999  on suhteellisia alkulukuja luvun  11000  suhteen, 
	ts. kuinka monta alkuluokkaa on modulo 11000?

4.5  Suurien potenssien nopea laskeminen: Eulerin lause ja peräkkäiset neliöönkorotukset

30	Laske   (17^1785) (mod 47)  käyttämällä Eulerin lausetta ja peräkkäisiä neliöönkorotuksia.

5.  Lineaarisen kongruenssiyhtälön ratkaiseminen

5.1  Yksi lineaarinen kongruenssiyhtälö

Kongruenssiyhtälöt ovat yksinkertaisimmillaan yhden lineaarisen kongruenssiyhtälön (linear congruence relation) tapauksessa:

a x≡b (mod m)

Tässä kohdassa ei nyt tarkastella ns. kiinalaisen jäännöslauseen tilannetta, jossa muuttuja  x  toteuttaa useita lineaarisia kongruenssiyhtälöitä yhtäaikaisesti.

Lause 5.1
Lineaarisella kongruenssiyhtälöllä  a x≡b (mod m)  on ratkaisu  x  jos ja vain jos  d = syt(a,m)  jakaa luvun  b.  Tässä tapauksessa erilaisten ratkaisujen (jäännösluokkien modulo m) lukumäärä on  syt(a,m).  Ratkaisujen muoto esitetään todistuksen kohdassa (5.3).

Todistus:  Koska  a x≡b (mod m) ⇔ m | (ax – b) ⇔ ax – b = km ⇔  b = ax – km = d(a'x – km'),  missä  d = syt(a,m)),  a=a' d, m=m' d  ja  k ∈ ℤ,  on selvää, että ehto  d = syt(a,m) | b  on välttämätön, jotta kongruenssiyhtälöllä  a x≡b (mod m)  olisi ratkaisu  x.  Osoitamme, että tämä on myös riittävä ehto.

Olkoon siis  d=syt(a,m).  Kirjoitetaan  a=a' d, m=m' d  ja  b=b'd,  missä  syt(a',m')=1.  
Tällöin 

(5.1)  	a x≡b (mod m) 
	⇔ ax – b = km ⇔ a'd x – b'd = k m'd ⇔ a' x – b' = k m' ⇔
(5.2) 	a'x≡b' (mod m').  

Koska  syt(a',m')=1,  on olemassa luvut  u,v∈ℤ,  joille  1 = ua' + vm'  (ks. Lause 1.4).  Siis  b' = ua'b' + vb'm',  ts.  a'(ub') – b' = (–vb')m',  ts.  a'(ub') ≡ b' (mod m').  Näin ollen  x' = ub'  on yksi (5.2):n ratkaisu ja siis myös (5.1):n ratkaisu.  Lemman 3.2 nojalla tämä  x' (= ub')  on myös yksikäsitteinen (5.2):n ratkaisu modulo  m'  (voit todeta myös suoraan, että jokaiselle (5.2):n ratkaisulle  x''  pätee  x''≡x' (mod m')).  Jokainen yhtälön  a x≡b (mod m)  ratkaisu  x  toteuttaa ehdon  x≡x' (mod m'),  missä  a'x'≡b' (mod m') (totea tämä!).  Siis jokainen yhtälön  a x≡b (mod m)  ratkaisu  x  modulo  m  voidaan kirjoittaa muotoon  x = x'+i m',  0≤i<d  (huom.  m = m'd).  Koska  a'x'=b'+k m',  k∈ℤ,  niin jokaiselle  0≤i<d  pätee

a(x'+i m')=d a'x'+i d a'm'=d b'+k d m'+i a 'm=b+(k+ia')m.

Näin ollen luvut  x'+i m',  0≤i<d,  edustavat yhtälön  a x≡b (mod m)  kaikkia ratkaisuja modulo  m,  ts. ratkaisuja ovat jäännösluokat  

(5.3)	[x'+i m'] ∈(Subscript[ℤ, m]),  0≤i<d ,

missä  x'  on myös yksikäsitteinen kongruenssin (5.2) ratkaisu modulo  m'.

□

5.2  Käänteisalkio modulo  m

Yhtälön  a x≡b (mod m), syt(a,m)=1,  ratkaisu (Lausen 5.1 nojalla ratkaisuna on vain yksi jäännösluokka modulo m) voidan löytää Eukleideen algoritmin laajennetulla versiolla (Algoritmi 2.2). Todellakin, ehdosta  u a+v m=1  seuraa, että  u a-1= (-v) m,  ts.  u a≡1 (mod m).  Kertomalla tämä kongruenssi puolittain luvulla  b,  nähdään nyt Lauseen 3.3 kohdan 4 (ii) nojalla, että yhtälön  a x≡b (mod m)  ratkaisu  x  on muotoa  b u  (= u b)  modulo  m.  Jos  syt(a,m)=1,  merkitään usein symbolilla  (a^(-1))  (mod m)  sitä yksikäsitteistä alkiota  u ∈(Subscript[ℤ, m]),  jolle  u a≡1 (mod m).

Esimerkki  5.1

Lasketaan  (7^(-1))  modulo  117.

ExtendedGCD[7,117]

Siis  1 = -50·7 + 3·117,  ts.  -50·7 - 1 = (-3)·117,  ts.  -50·7 ≡ 1 (mod 117).  Näin ollen  (7^(-1)) ≡ -50 ≡ -50 + 117 ≡ 67 (mod 117).  

Tarkistetaan vielä:  67·7 = 469 = 4·117 + 1,  ts.  67·7 ≡ 1  (mod 117),  kuten pitääkin.

Esimerkki  5.2  (Laajennettu Eukleideen algoritmi)
Ratkaistaan  14 x≡26 (mod 34).  Huomaamme, että  syt(14,34)=2,  joka jakaa luvun 26. 
Ratkaistaan ensin  7 x'≡13 (mod  17). Laajennetulla Eukleideen algoritmilla löydämme  5·7+(-2) 17=syt(7, 17)=1.  Niinpä  7·5 ≡ 1 (mod 17)  ja  x'  voidaan laskea seuraavasti:  x'≡(7^(-1))·13≡5·13≡14 (mod 17).

Lauseen 5.1 ja sen todistuksen nojalla, ks. (5.3), yhtälön  14 x≡26 (mod 34)  ratkaisuja ovat  14  ja  14 + 17 = 31  modulo 34,   ts. ratkaisut ovat jäännösluokat  [14]  ja [31] ∈(Subscript[ℤ, 34]).

Esimerkki  5.3  (Eulerin lause)
Ratkaistaan  123456789 x ≡ 135798642 (mod 179424673).  Tarkistetaan ensin jakaako syt(123456789, 179424673)  luvun  135798642. Tässä syt = 1.  Seuravaksi lasketaan  (123456789^(-1)) (mod 179424673)  ja sitten  (123456789^(-1))·135798642,  josta ratkaisuksi saadaan  x ≡ 21562478 (mod 179424673).

Lasketaan tässä  (123456789^(-1)) (mod 179424673)  Eukleideen algoritmin sijasta Eulerin lauseen avulla.  Todellakin, kongruenssi  (a^(φ(m)))≡1 (mod m)  antaa  a (a^(φ(m)-1))≡1 (mod m),  joten  (a^(-1))≡(a^(φ(m)-1)) (mod m).

GCD[148953050, 179424673]
PowerMod[123456789, EulerPhi[179424673]-1, 179424673]

Siis luku  172609538  on luvun  123456789  käänteisalkio modulo  179424673.  Yhtälön  123456789 x≡135798642 (mod 179424673)  ratkaisu  x  saadaan seuraavasti:

Mod[135798642 *172609538,179424673]

Tarkistus:

Mod[123456789*21562478, 179424673]

Siis kongruenssiyhtälö  123456789 x ≡ 135798642 (mod 179424673)  toteutuu aina, kun  x ≡ 21562478 (mod 179424673).  Lausen 5.1 nojalla muita ratkaisuja ei ole, koska  syt(123456789, 179424673) = 1.

5.3  Kongruenssiyhtälön ratkaiseminen tietokoneella

Mathematica-funktio PowerMod laskee kääänteisalkion hyvin tehokkaalla tavalla näin:

PowerMod[123456789,-1, 179424673]

Mathematica-funktio Solve antaa kongruenssiyhtälön  a x≡b (mod m)  kaikki ratkaisut, jos ne ovat olemassa:

Clear[x];
Solve[ {12 x == 8, Modulus== 16}, x]

Jos halutaan vain ratkaisut, voidaan kirjoittaa seuraavasti:

x /. Solve[ {12 x == 8, Modulus== 16}, x]

Lukija voi kokeilla myös seuraavia tehtäviä:

x /. Solve[ {13 x == 1, Modulus== 16}, x]

Solve[ {12 x == 7, Modulus== 16}, x]

Osan 1 etätehtävät – kooste kaikista kappaleista

1.  Jaollisuus

1.1  Tekijöihin jako

1  	Onko kokonaisluku  19  seuraavien kokonaislukujen tekijä?
	a)  57		b)  –95		c)  209		d)  10001

2  	Etsi seuraavien kokonaislukujen kaikki tekijät.
	a)  57		b)  71		c)  100		d)  1024

1.2  Jakoalgoritmi

3	Suorita jakolasku  543 : 21  ja kirjoita tulos jakoyhtälönä muodossa
	jaettava =  vaillinainen osamäärä  kertaa  jakaja  plus  jakojäännös,
	ts. muodossa 	a = q b + r,  0≤ r < |b |,  missä  a = 543,  b = 21,
	q = vaillinainen osamäärä  ja  r = jakojäännös.

4 	Muunna 10–järjestelmän luku  511  
	a)  binääriluvuksi  
	b)  8–kantaiseen järjestelmään 
	c)  esitä luku  (Subscript[1234, 7])  10–järjestelmän lukuna

5  	Muuta luku 10–järjestelmän luku  2358  
	a)  binääriluvuksi
	b)  7–kantaiseen järjestelmään

1.3  Alkuluvut

6	Osoita, että  113  on alkuluku.

7	Mitä tarkoittavat seuraavat tulomuodot?
	
	a)  (((∏_(i=1)^4) i)^( 3))	b)  (((∏_(i=1)^n) i)^( ))	c)  (((∏_(i=1)^k) (1/(i^2)))^( ))	d)  (((∏_(i=2)^n) (1-(1/i)))^( ))

8	Todista hieman eri tavalla (tai kertaa ajatuksella) Lause 1.2 (Eukleides): Alkulukuja on ääretön määrä.

1.4–5  Suurin yhteinen tekijä ja pienin yhteinen jaettava. Aritmetiikan peruslause.

9	Laske Esimerkin 1.2 tavalla  syt(a, b)  ja  pyj(a, b),  kun
	
	a = (3^2)·(5^3)·(7^4)  ja  b = (2^4)·(3^3)·(7^2).   
 
	Totea näille luvuille, että  syt(a,b) · pyj(a,b) = ab.

10	Kertaa Lauseen 1.7 (Aritmetiikan peruslause) alkuosan todistus:
	Jokainen kokonaisluku  a ≥ 2  voidaan esittää tekijöiden järjestystä 
	lukuunottamatta alkulukujen  (Subscript[p, i])  tulona muodossa  a = (∏_i)(Subscript[p, i]^(Subscript[e, i])),  (Subscript[e, i])∈ℕ.
	Yksikäsitteisyyden todistusta ei tässä siis nyt vaadita.

2.  Eukleideen algoritmi

2.1–2	Suurimman yhteisen tekijän tehokas laskutapa 
	ja lineaarikombinaatio  syt(a,b)=u a+v b

11	Määritä  syt(1233, 63)  ja esitä se muodossa  s 1233 + t 63,  missä  s, t ∈ ℤ.
	Välivaiheet tulee merkitä selkeästi näkyviin

12  	Määritä  syt(2333, 187)  ja esitä se muodossa  s 2333 + t 187,  missä  s, t ∈ ℤ.

12'  	Lisäharjoitus. Valitse itse luvut  a  ja  b.  Laske valitsemillasi luvuilla d = syt(a, b)  
	ja esitä  d  muodossa  d = s a + t b,  missä  s, t ∈ ℤ.

3.  Kongruenssit

3.1  Jakojäännös ja kongruenssi

13	Mitkä seuraavista kongruensseista ovat tosia?

	a)	19 ≡ 1 (mod 9)
	b)	19 ≡ –8 (mod 9)
	c)	18 ≡ 0 (mod 9) 
	d)	29 ≡–2 (mod 9)

14	Osoita, että  a≡b (mod m)  täsmälleen silloin, kun kokonaisluvuilla  
	a  ja  b  on sama jakojäännös modulo  m.

3.2  Jäännösluokka

15	Tarkastellaan kokonaislukujen jakautumista jäännösluokkiin modulo 4, ts.
	tarkastellaan joukkoa  (Subscript[ℤ, 4]) =  {[0], [1], [2], [3]}.  Esitä Esimerkin 3.4 tavalla, 
	mitkä luvut kuuluvat seuraaviin jäännösluokkiin. 
	a)  [0] 		b)  [1]		c)  [2] 		d)  [3].

3.3  Täydellinen jäännössysteemi

16	Kertaa Lemman 3.1 todistus:  Olkoon   k a≡k b (mod m)  ja  syt(k,m)=d.  
	Tällöin	 a≡b  (mod m/d).

17	Kertaa Lemman 3.2 todistus: Olkoon  {(Subscript[a, 1]),(Subscript[a, 2]),…,(Subscript[a, m])}  täydellinen jäännössysteemi 
	modulo  m  ja olkoon  syt(k,m)=1.  Tällöin  {k (Subscript[a, 1]),k (Subscript[a, 2]),…,k (Subscript[a, m])}  on myös 
	täydellinen jäännössysteemi modulo  m.

3.4  Kongruenssien laskusääntöjä

18	Kertaa Lauseen 3.3 kohdan 4 (iii) todistus: Olkoon  m  annettu positiivinen kokonaisluku, 
	a ≡ b (mod m)  ja  c ≡ d (mod m).  Tällöin  a c ≡ b d (mod m).

19	Esitä joukkojen  (Subscript[ℤ, 8])  ja  (Subscript[ℤ, 9])  yhteen- ja kertolaskutaulut.

20	Ratkaise joukossa  (Subscript[ℤ, 7]) = {[0], [1], [2], [3], [4], [5], [6]}  yhtälö  [2] x + [3] = [4].

21	Etsi jakojäännös, kun

	a)	(10^515)	jaetaan luvulla  7	(5)
	b)	(8^391)	jaetaan luvulla  5	(2)
	c)	(7^348)	jaetaan luvulla  11	(9)
	d)	(3^323)   	jaetaan luvulla  7	(5)
	e)	127·((10^515)+(3^323))    jaetaan luvulla  7	  (3)

	Laske sopivasti jakojäännöksillä ja merkitse kaikki välivaiheet näkyviin.
	Oikea vastaus on merkitty valmiiksi sulkeiden sisään.

22	Etsi jakojäännös, kun

	a)	(2^203)	jaetaan luvulla  5	(3)
	b)	(3^4567)	jaetaan luvulla  6	(3)
	c)	55·( (2^203) + (3^4567))    jaetaan luvulla  7	  (0)

	Laske sopivasti jakojäännöksillä ja merkitse välivaiheet näkyviin.
	Oikea vastaus on tässäkin merkitty valmiiksi sulkeiden sisään.

23	Oletetaan tunnetuksi tulos  P(b) ≡ P(c) (mod m),  kun  
	P(x) = (Subscript[a, 0])(x^n) + (Subscript[a, 1])(x^(n-1)) + ⋯ + (Subscript[a, n-1])x + (Subscript[a, n]);  (Subscript[a, i]) ∈ ℤ;  ja  b ≡ c (mod m).  
	Olkoon lisäksi  q  n-numeroinen kokonaisluku ja sen peräkkäiset numerot  
	(Subscript[a, 1]), (Subscript[a, 2]), ... , (Subscript[a, n]);  (Subscript[a, i]) ∈ {0, 1, ... , 9}.  Osoita, että  9 | q  jos ja vain jos  
	9 | ((Subscript[a, 1]) + (Subscript[a, 2]) + ⋯ + (Subscript[a, n])).  Onko luku  987654321  jaollinen 9:llä?

4.  Eulerin ja Fermat'n lauseet

4.1–3  	Alkuluokka ja Eulerin φ-funktio
	Supistettu jäännössysteemi
	Eulerin ja Fermat'n lauseet

24	Määritä alkuluokat modulo  m,  ts. joukon  (Subscript[ℤ, m]^( * ))  alkiot sekä  φ(m) tapauksissa  
	m = 7  ja  m = 12.  Laske myös  φ(46), φ(55), φ(81)  ja  φ(144).

25	Todista (tai kertaa ajatuksella) Lause 4.4 (Fermat'n pieni lause):  Olkoon  p  alkuluku 
	ja  a  kokonaisluku, joka ei ole luvun  p  monikerta. Tällöin

		(a^(p-1))≡1 (mod p)
	
	Edelleen kaikille (vapaasti valituille) kokonaisluvuille  a  on voimassa
		
		(a^p)≡a (mod p).

26	Osoita Fermat'n pienen lauseen nojalla, että

	a)	(2^198) ≡ 1 (mod 199)
	b)	(10^12)≡ 1 (mod 11)
	c)	(10^25) ≡ 10 (mod 11)

27	Kertaa Lauseen 4.5 todistus:  Jos  p  on alkuluku ja  k ∈ (SuperPlus[ℤ]),  niin 

 		φ((p^k)) =  (p^k) – ((p^k)/p) = (p^k)(1-(1/p)).

4.4  Eulerin funktio ja kertolaskun säilyminen

28	Täydennä Esimerkin 4.1 taulukko, ts. etsi alla olevasta taulukosta kokonaisluvun  
	120  kaikki alkuluokat (edustajat).  Käy läpi Lauseen 4.6 todistus yksittäistapauksessa: 
	φ(120)= φ(8·15) = φ(8)·φ(15)  = 4·8 =32.  Ensimmäinen kyseeseen tuleva 
	sarake on tehty malliksi. Merkitse myös näkyviin poimittavien lukujen (merkitään neliöillä) 
	edustamat alkuluokat (tai ainakin osa niistä) modulo  8   ja modulo  15.

(({{ , ↓,  , ↓,  , ↓,  , ↓}, {0, 1, 2, 3, 4, 5, 6, 7}, {8, 9, 10, 11, 12, 13, 14, 15}, {16, 17, 18, 19, 20, 21, 22, 23}, {24, 25, 26, 27, 28, 29, 30, 31}, {32, 33, 34, 35, 36, 37, 38, 39}, {40, 41, 42, 43, 44, 45, 46, 47}, {48, 49, 50, 51, 52, 53, 54, 55}, {56, 57, 58, 59, 60, 61, 62, 63}, {64, 65, 66, 67, 68, 69, 70, 71}, {72, 73, 74, 75, 76, 77, 78, 79}, {80, 81, 82, 83, 84, 85, 86, 87}, {88, 89, 90, 91, 92, 93, 94, 95}, {96, 97, 98, 99, 100, 101, 102, 103}, {104, 105, 106, 107, 108, 109, 110, 111}, {112, 113, 114, 115, 116, 117, 118, 119}}))

29	Laske Esimerkin 4.2 tavalla  φ(11000).  Kuinka monta luvuista 
	0, 1, 2, ..., 10999  on suhteellisia alkulukuja luvun  11000  suhteen, 
	ts. kuinka monta alkuluokkaa on modulo 11000?

4.5  Suurien potenssien nopea laskeminen: Eulerin lause ja peräkkäiset neliöönkorotukset

30	Laske   (17^1785) (mod 47)  käyttämällä Eulerin lausetta ja peräkkäisiä neliöönkorotuksia.

Kirjallisuutta

Keijo Väänänen (Oulun yliopisto) luentorunko ja harjoitustehtävät
Salakirjoitukset (801346A), 4 op
http://math.oulu.fi/materiaalit/luentorungot/Salausmenetelmat.pdf

Markku Niemenmaa, Kari Myllylä, Juha-Matti Tirilä (Oulun yliopisto) 
Algebra I -kurssin luentorunko 
http://math.oulu.fi/materiaalit/luentorungot/AlgebraI-k2010.pdf

Lukuteorian osuus (jakoalgoritmi, jaollisuus, kongruenssit) 
löytyy myös useimmista algebran ja diskreetin matematiikan 
kirjoista, joista alla on mainittu muutamia.  

[1]  Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, 
	 Introduction to Algorithms, MIT Press, 2000, 
	 ISBN 0-262-03141-8
[2]  Reijo Ervall, Koodausteoria, Julkaisu C:2:2, 
 	 Hämeen amattikorkeakoulu, Hämeenlinna, 1995, 
 	 ISBN 951-784-016-0 (ei ilmeisesti julkaista enää)
[3]  Larry J. Gerstein, Discrete Mathematics and Algebraic 
	 Structures, 1987, ISBN 0-7167-1804-9 
	 (tai uudempi painos)
[4]  Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, 
	 Addison-Wesley,1999, ISBN 0-201-30424-4
[5]  Josef Gruska, Foundations of Computing, International 
	 Thompson Computer Press, 1997, ISBN 1-85032-243-0
[6]  Seppo Ilkka, Diskreettiä matematiikkaa 524, OTATIETO, 1998, 
	 ISBN 951-672-176-1
[7]  Robert F. Lax, Modern Algebra and Discrete Structures, 
 	 Addison-Wesley, 1991, ISBN 0-06-043878-9
[8]  Keith W. Nicholson, Introduction to Abstract Algebra, 
	 Wiley-Interscience, 1999, ISBN 0-471-33109-0
[9]  Kenneth H. Rosen, Discrete Mathematics and Its 
	 Applications, McGraw-Hill, 1999, ISBN 0-07-116756-0; 
	 ks. myös http://www.mhhe.com
[10] Arto Salomaa, Public-Key Cryptography, EATCS Monographs 
	 on Theoretical Computer Science, Springer-Verlag, 1990, 
	 ISBN 0-387-52832-8
[11] Henk C.A. van Tilborg, Fundamentals of Cryptology, 
	 A Professional Reference and Interactive Tutorial 
	 (+ Mathematica CD), Kluwer Academic Publishers, 2000, 
	 ISBN 0-7923-8675-2
[12] Dominic Welsh, Codes and Cryptography, Oxford University 
	Press, 1993, ISBN 0-19-853287-3

Liitteet

Liite 1.  Laajennettu Eukleideen algoritmi – suoraviivainen tapa

- johdanto
- matemaattinen induktiotodistus
- matriisien kertolaskun käyttömahdollisuus
- käsinlaskuesimerkkejä
- kaikki välivaiheet esittävä ohjelma Mathematicalla

Laajennettu Eukleideen algoritmi - suoraviivainen tapa

Etsitään annettujen positiivisten lukujen  a  ja  b  suurimman yhteisen tekijän  d = syt(a, b)  esitys lukujen  a  ja  b  lineaarkombinaationa muodossa  d  = u a + v b;  u, v ∈ ℤ;  suoraviivaisella tavalla. Tässä tavassa jakoalgoritmin tuottama jakojäännös  (Subscript[r, i])  esitetään jokaisella askeleella muodossa  (Subscript[u, i]) a + (Subscript[v, i]) b.  Viimeisen jakojäännöksen  (Subscript[r, n])  ollessa nolla, on viimeinen nollasta eroava jakojäännös  (Subscript[r, n-1])  etsitty lineaarikombinaatio  d = syt(a,b)=(Subscript[r, n-1])=u a+v b.  Aloitetaan laskemalla yksityiskohtaisesti useita ensimmäisiä rivejä:

a≥b>0

	a = (Subscript[q, 1])b+(Subscript[r, 1]);		(Subscript[r, 1]) 	= a – (Subscript[q, 1])b = (Subscript[u, 1])a + (Subscript[v, 1])b,  
					   missä  (Subscript[u, 1]) = 1, (Subscript[v, 1]) = – (Subscript[q, 1]) ∈ ℤ
	b = (Subscript[q, 2])(Subscript[r, 1])+(Subscript[r, 2]);		(Subscript[r, 2]) 	= b – (Subscript[q, 2])(Subscript[r, 1]) = b – (Subscript[q, 2])(a – (Subscript[q, 1])b) = – (Subscript[q, 2])a + (1 – (Subscript[q, 2])(Subscript[v, 1]))b 
					= (Subscript[u, 2])a + (Subscript[v, 2])b, 
					   missä  (Subscript[u, 2]) = – (Subscript[q, 2]), (Subscript[v, 2]) = 1 – (Subscript[q, 2])(Subscript[v, 1])
	(Subscript[r, 1]) = (Subscript[q, 3])(Subscript[r, 2])+(Subscript[r, 3]);		(Subscript[r, 3]) 	= (Subscript[r, 1]) – (Subscript[q, 3])(Subscript[r, 2]) = (a – (Subscript[q, 1])b ) – (Subscript[q, 3])(b – (Subscript[q, 2])(a – (Subscript[q, 1])b )) 
					= (Subscript[u, 1])a + (Subscript[v, 1])b – (Subscript[q, 3])((Subscript[q, 2])a + (1 – (Subscript[q, 2])(Subscript[v, 1]))b)
					= (Subscript[u, 1])a + (Subscript[v, 1])b – (Subscript[q, 3])( (Subscript[u, 2])a + (Subscript[v, 2])b)
					= ((Subscript[u, 1]) – (Subscript[q, 3])(Subscript[u, 2]))a  + ((Subscript[v, 1]) – (Subscript[q, 3])(Subscript[v, 2]))b
					= (Subscript[u, 3])a + (Subscript[v, 3])b,
					   missä  (Subscript[u, 3]) = (Subscript[u, 1]) – (Subscript[q, 3])(Subscript[u, 2]), (Subscript[v, 3]) = (Subscript[v, 1]) – (Subscript[q, 3])(Subscript[v, 2])
	(Subscript[r, 2]) = (Subscript[q, 4])(Subscript[r, 3])+(Subscript[r, 4]);		(Subscript[r, 4]) 	= (Subscript[r, 2]) – (Subscript[q, 4])(Subscript[r, 3]) = (b – (Subscript[q, 2])(a – (Subscript[q, 1])b )) – (Subscript[q, 4])((a – (Subscript[q, 1])b ) – (Subscript[q, 3])(b – (Subscript[q, 2])(a – (Subscript[q, 1])b )))
					= (Subscript[u, 2])a + (Subscript[v, 2])b – (Subscript[q, 4])((Subscript[u, 3])a + (Subscript[v, 3])b)
					= ((Subscript[u, 2]) – (Subscript[q, 4])(Subscript[u, 3]))a + ((Subscript[v, 2]) – (Subscript[q, 4])(Subscript[v, 3]))b
					= (Subscript[u, 4])a + (Subscript[v, 4])b,
					   missä  (Subscript[u, 4]) = (Subscript[u, 2]) – (Subscript[q, 4])(Subscript[u, 3]), (Subscript[v, 4]) = (Subscript[v, 2]) – (Subscript[q, 4])(Subscript[v, 3])
	(Subscript[r, 3]) = (Subscript[q, 5])(Subscript[r, 4])+(Subscript[r, 5]);		(Subscript[r, 5]) 	= (Subscript[r, 3]) – (Subscript[q, 5])(Subscript[r, 4]) = (Subscript[u, 5])a + (Subscript[v, 5])b,  missä (Subscript[u, 5]) = (Subscript[u, 3]) – (Subscript[q, 5])(Subscript[u, 4]), (Subscript[v, 5]) = (Subscript[v, 3]) – (Subscript[q, 5])(Subscript[v, 4])
	
ja niin edelleen.
	
Meillä on siis
	
	a = (Subscript[q, 1])b + (Subscript[r, 1]),	(Subscript[r, 1]) = a – (Subscript[q, 1])b
	b = (Subscript[q, 2])(Subscript[r, 1])+(Subscript[r, 2]),	(Subscript[r, 2]) = b – (Subscript[q, 2])(Subscript[r, 1]). 
	
Tämän lisäksi yleiset jakojäännökset sekä kertoimet  (Subscript[u, i])  ja  (Subscript[v, i])  ovat ilmeisestikin muotoa
	
		(Subscript[r, i]) = (Subscript[r, i-2]) – (Subscript[q, i])(Subscript[r, i-1]) = (Subscript[u, i])a + (Subscript[v, i])b,  
missä  		(Subscript[u, i]) = (Subscript[u, i-2]) – (Subscript[q, i]) (Subscript[u, i-1])
	ja 	(Subscript[v, i]) = (Subscript[v, i-2]) – (Subscript[q, i])(Subscript[v, i-1]), aina kun  i ≥ 3.   (*)
	
Koska 		(Subscript[u, 1]) = 1, (Subscript[v, 1]) = (Subscript[–q, 1])
	ja	(Subscript[u, 2]) = (Subscript[–q, 2]), (Subscript[v, 2]) = 1 – (Subscript[q, 2])(Subscript[v, 1]),
niin		(Subscript[u, 2]) = (Subscript[u, 0])– (Subscript[q, 2])(Subscript[u, 1]), (Subscript[v, 2]) = (Subscript[v, 0])– (Subscript[q, 2])(Subscript[v, 1]),  kun  (Subscript[u, 0]) = 0  ja  (Subscript[v, 0]) = 1.
Toisin sanoen, valitsemalla  (Subscript[r, 0]) = b;  (Subscript[u, 0]) = 0  ja  (Subscript[v, 0]) = 1  sekä  (Subscript[u, 1]) = 1, (Subscript[v, 1]) = (Subscript[–q, 1]),  voidaan (*) laajentaa 
koskemaan myös arvoa  i = 2.  Saadaan siis
	
			(Subscript[r, 1]) = a – (Subscript[q, 1])b
			(Subscript[r, i]) = (Subscript[r, i-2]) – (Subscript[q, i])(Subscript[r, i-1]) = (Subscript[u, i])a + (Subscript[v, i])b 
			(Subscript[u, i]) = (Subscript[u, i-2]) – (Subscript[q, i]) (Subscript[u, i-1])
			(Subscript[v, i]) = (Subscript[v, i-2]) – (Subscript[q, i])(Subscript[v, i-1]), aina kun  i ≥ 2. 
	
Merkitään vielä  (Subscript[r, -1])=a, (Subscript[r, 0])=b;  (Subscript[u, -1]) = 1  ja  (Subscript[v, -1]) = 0  sekä  (Subscript[u, 0]) = 0  ja  (Subscript[v, 0]) = 1.  Tällöin ensimmäinen yhtäsuuruus 
(Subscript[r, 1]) = a – (Subscript[q, 1])b  sekä arvot  (Subscript[u, 1])  ja  (Subscript[v, 1])  saadaan yleisistä palautuskaavoista myös tapauksessa  i = 1: 
			
			(Subscript[r, i]) = (Subscript[r, i-2]) – (Subscript[q, i])(Subscript[r, i-1]) = (Subscript[u, i])a + (Subscript[v, i])b 
			(Subscript[u, i]) = (Subscript[u, i-2]) – (Subscript[q, i]) (Subscript[u, i-1])
			(Subscript[v, i]) = (Subscript[v, i-2]) – (Subscript[q, i])(Subscript[v, i-1]), aina kun  i ≥ 1. 
			
Yllä esitetyistä laskelmista voidaan myös havaita, että luvun  a  (> 0)  kerroin  (Subscript[u, i])  on positiivinen aina kun indeksi  i  on pariton ja negatiivinen aina kun  i > 0  on parillinen.  Luvun  b  (> 0)  kertoimen  (Subscript[v, i])  etumerkki puolestaan vaihtelee päinvastoin:  (Subscript[v, i]) on negatiivinen aina kun indeksi  i > 0  on pariton ja positiivinen aina kun  i  on parillinen. 

Esitetään seuraavaksi tämä laajennettu Eukleideen algoritmi valmiin ohjelman muodossa (kuten jo kappaleessa 2.2), ja todistetaan sen virheetön toiminta matemaattisella induktiolla.

Algoritmi 2.2	Laajennettu Eukleideen algoritmi 

	syöte		a≥b>0
	alkuarvot	(Subscript[r, -1])=a; (Subscript[r, 0])=b;
			  (Subscript[u, -1])=1; (Subscript[u, 0])=0; (Subscript[v, -1]) =0; (Subscript[v, 0]) =1;n=0;
	while  (Subscript[r, n])>0  do  begin
					aseta  	n=n+1;
				tulosta	(Subscript[r, n-2])=(Subscript[q, n])(Subscript[r, n-1])+(Subscript[r, n]),  (Subscript[r, n-1]) > (Subscript[r, n]) ≥ 0;
				aseta 	(Subscript[u, n])=(Subscript[u, n-2])-(Subscript[q, n]) (Subscript[u, n-1]);
				aseta 	(Subscript[v, n])=(Subscript[v, n-2])-(Subscript[q, n]) (Subscript[v, n-1]);
				end
	aseta	 u=(Subscript[u, n-1]); v= (Subscript[v, n-1]);

(2.2)  	syt(a,b)=(Subscript[r, n-1])=u a+v b

Algoritmin 2.2 oikeellisuuden todistus:
Aluksi huomataan, että luvut (Subscript[r, n]), n≥1, muodostavat ei-negatiivisten kokonaislukujen aidosti vähenevän jonon. Näin ollen algoritmin toiminta päättyy vähintään a iteraation jälkeen (käytännössä huomattavan paljon nopeammin).  Algoritmin palauskaavasta  (Subscript[r, i]) = (Subscript[r, i-2]) – (Subscript[q, i])(Subscript[r, i-1]) seuraa, että jokainen jakojäännöksien  (Subscript[r, i-2])  ja  (Subscript[r, i-1])  yhteinen tekijä on myös jakojäännöksien  (Subscript[r, i])  ja  (Subscript[r, i-1]) yhteinen tekijä. Toisaalta jokainen jakojäännöksien  (Subscript[r, i])  ja  (Subscript[r, i-1])  tekijä  t  on myös lukujen  (Subscript[r, i-2])  ja  (Subscript[r, i-1])  tekijä, koska muodoista  (Subscript[r, i]) = t (Subscript[r, i])'  ja  (Subscript[r, i-1]) = t (Subscript[r, i-1])' (t, (Subscript[r, i])', (Subscript[r, i-1])' ∈ (SuperPlus[ℤ]))  seuraa palautuskaavan nojalla, että  (Subscript[r, i-2]) = (Subscript[r, i]) + (Subscript[q, i])(Subscript[r, i-1]) = t (Subscript[r, i])' + (Subscript[q, i]) t (Subscript[r, i-1])' = t ((Subscript[r, i])' + (Subscript[q, i]) (Subscript[r, i-1])'),  ts.  t  on luvun  (Subscript[r, i-2])  (ja oletuksen mukaan myös luvun  (Subscript[r, i-1]))  tekijä.  Siis syt((Subscript[r, i-2]),(Subscript[r, i-1]))=syt((Subscript[r, i-1]),(Subscript[r, i])),  aina kun  1 ≤ i ≤ n,  ja näin ollen

syt(a,b)=syt((Subscript[r, -1]),(Subscript[r, 0]))=syt((Subscript[r, 0]),(Subscript[r, 1]))=syt((Subscript[r, 1]),(Subscript[r, 2]))=…=syt((Subscript[r, n-1]),(Subscript[r, n]))=syt((Subscript[r, n-1]),0)=(Subscript[r, n-1]).

Tämä todistaa ensimmäisen yhtäsuuruuden kohdassa (2.2).

Osoitamme nyt, että kaikille  k,  -1≤k≤n,  on voimassa

(2.3)	(Subscript[u, k]) a+(Subscript[v, k]) b=(Subscript[r, k]).

Huomaa, että tässä sijoitus k=n-1 tuottaa toisen yhtäsuuruuden kohdassa (2.2).  Kun  k=-1  ja  k=0  relaatio (2.2) on voimassa alkuarvojen  (Subscript[r, -1])=a; (Subscript[r, 0])=b; (Subscript[u, -1])=1; (Subscript[u, 0])=0; (Subscript[v, -1]) =0; (Subscript[v, 0]) =1;  valinnan perusteella. Jatketaan matemaattisella induktiolla. Tehdään induktio-oletus (i.o.), että (2.2) on voimassa, kun  n = k–2  ja kun  n = k–1.  Algoritmin palautuskaavojen ja induktio-oletuksen nojalla seuraa, että

(Subscript[r, k]) =(Subscript[r, k-2])-(Subscript[q, k])(Subscript[r, k-1])(Overscript[=, i.o.]) {(Subscript[u, k-2]) a+(Subscript[v, k-2]) b}-(Subscript[q, k]) {(Subscript[u, k-1]) a+(Subscript[v, k-1]) b}=((Subscript[u, k-2])  – (Subscript[q, k]) (Subscript[u, k-1]))a+((Subscript[v, k-2])–  (Subscript[q, k]) (Subscript[v, k-1])) b 
= (Subscript[u, k]) a + (Subscript[v, k]) b.

Induktioperiaatteen nojalla kohta (2.3) on tosi.  Näin ollen Algoritmi 2.2 toimii oikein.

□

Tietenkään ei ole välttämätöntä tallettaa kaikkia muuttujien  (Subscript[r, k]), (Subscript[u, k]) ja (Subscript[v, k])  väliarvoja. Vain kaksi viimeistä yhdessä  (Subscript[q, k]):n  kanssa riittää. Muut väliarvot olivat mukana algoritmissa vain helpottamassa todistuksen lukemista.

Huomautus.  Koska kertoimet  (Subscript[u, i])  ja  (Subscript[v, i])  lasketaan lineaaristen yhtälöiden

			(Subscript[u, i]) = (Subscript[u, i-2]) – (Subscript[q, i]) (Subscript[u, i-1])
			(Subscript[v, i]) = (Subscript[v, i-2]) – (Subscript[q, i])(Subscript[v, i-1])
			
avulla, voitaisiin ne – ja saman tien seuraavalla askeleella tarvittavat  (Subscript[u, i-1])  ja  (Subscript[v, i-1]) – tuottaa ja tallentaa matriisimuodossa seuraavasti:

			(({{(Subscript[u, i]), (Subscript[v, i])}, {(Subscript[u, i-1]), (Subscript[v, i-1])}})) = (({{-(Subscript[q, i]), 1}, {1, 0}}))(({{(Subscript[u, i-1]), (Subscript[v, i-1])}, {(Subscript[u, i-2]), (Subscript[v, i-2])}})).
			
Koska  (Subscript[u, -1])=1; (Subscript[u, 0])=0; (Subscript[v, -1]) =0; (Subscript[v, 0]) =1;  meillä on	 		
			
			(({{(Subscript[u, 0]), (Subscript[v, 0])}, {(Subscript[u, -1]), (Subscript[v, -1])}})) = (({{0, 1}, {1, 0}})).

Kun  i = 1,  saadaan

			(({{(Subscript[u, 1]), (Subscript[v, 1])}, {(Subscript[u, 0]), (Subscript[v, 0])}})) = (({{-(Subscript[q, 1]), 1}, {1, 0}}))(({{0, 1}, {1, 0}})).
			
Seuravassa askeleessa saadaan

			(({{(Subscript[u, 2]), (Subscript[v, 2])}, {(Subscript[u, 1]), (Subscript[v, 1])}})) = (({{-(Subscript[q, 2]), 1}, {1, 0}}))(({{(Subscript[u, 1]), (Subscript[v, 1])}, {(Subscript[u, 0]), (Subscript[v, 0])}})) = (({{-(Subscript[q, 2]), 1}, {1, 0}}))((({{-(Subscript[q, 1]), 1}, {1, 0}}))(({{0, 1}, {1, 0}}))).
			
Tässä kahden viimeisen matriisin ympärillä olevat sulkumerkit voidaan jättää merkitsemättä matriisien liitäntä- eli assosiatiivisuusominaisuuksien nojalla.

Lopullisessa lineaarikombinaatiossa  syt(a,b)=(Subscript[r, n-1])=u a+v b  kertoimet ovat  u=(Subscript[u, n-1]); v= (Subscript[v, n-1]) ja ne löytyvät  n – 1  matriisikertolaskun jälkeen saatavan tulomatriisin ensimmäiseltä vaakariviltä sen jälkeen, kun tarvittavat kertoimet  (Subscript[q, i])  ovat löytyneet:  

			(({{(Subscript[u, n-1]), (Subscript[v, n-1])}, {(Subscript[u, n-2]), (Subscript[v, n-2])}})) =  (({{-(Subscript[q, n-1]), 1}, {1, 0}})) ⋯ (({{-(Subscript[q, 2]), 1}, {1, 0}}))(({{-(Subscript[q, 1]), 1}, {1, 0}}))(({{0, 1}, {1, 0}})).

Alla olevassa käsinlaskuesimerkissä, jossa lasketaan  syt(368, 123), saadaan  (Subscript[q, 1])= 2  ja  (Subscript[q, 2]) = 1.  Tuossa tapauksessa on kolme riviä, joten  n = 3.  Kertoimiksi saadaan  u=(Subscript[u, n-1])=-1 ; v= (Subscript[v, n-1])= 3.  Nämä luvut löytyvät tulomatriisin ensimmäiseltä vaakariviltä:

(({{-1, 1}, {1, 0}})).(({{-2, 1}, {1, 0}})).(({{0, 1}, {1, 0}}))

Jätämme lukijalle tämän elegantin laskentatavan ohjelmoinnin harjoitustehtäväksi emmekä enää käsittele sitä tässä yhteydessä.

Käsinlaskuesimerkki:  a = 368  ja  b = 123

Tässä  syt = 1,  mikä nähdään Eukleideen algoritmilla seuraavasti:

({{368, "=", 2, "*", 123, "+", 122}, {123, "=", 1, "*", 122, "+", 1}, {122, "=", 122, "*", 1, "+", 0}, {"", "", "", "", "", "", ""}})"" 
Viimeinen nollasta eroava jakojäännös = 1 = syt(368, 123).

Esitetään  syt = 1  nyt lukujen  a = 368  ja  b = 123  lineaarikombinaationa.  Tässä yksinkertaisessa tilanteessa laskelmat on helppo tehdä käsin.  Meillä siis on voimassa

(Subscript[r, i]) = (Subscript[r, i-2]) – (Subscript[q, i])(Subscript[r, i-1]) = (Subscript[u, i])a + (Subscript[v, i])b,  
missä  (Subscript[u, i]) = (Subscript[u, i-2]) – (Subscript[q, i]) (Subscript[u, i-1]), (Subscript[v, i]) = (Subscript[v, i-2]) – (Subscript[q, i])(Subscript[v, i-1]),  
(Subscript[u, 0]) = 0  ja  (Subscript[v, 0]) = 1  sekä  (Subscript[u, 1]) = 1, (Subscript[v, 1]) = (Subscript[–q, 1]).

Niinpä laskemme seuraavasti:

(Subscript[r, i-2]) =  (Subscript[q, i])(Subscript[r, i-1]) + (Subscript[r, i]) ;		(Subscript[r, i]) = (Subscript[r, i-2]) – (Subscript[q, i])(Subscript[r, i-1])= (Subscript[u, i])a + (Subscript[v, i])b ;				(Subscript[u, i]), (Subscript[v, i]), (Subscript[q, i])
-----------------------	         -----------------------------------			   -----------
368 = 2*123 + 122 ; 		122 = 368 – 2*123 ;    				(Subscript[u, 1]) = 1, (Subscript[v, 1]) = (Subscript[–q, 1])= –2

123 = 1*122 + 1 ;		1 = 123 – 1*(368 – 2*123) = –1* 368 + 3*123 ;   	(Subscript[u, 2]) = (Subscript[u, 0]) – (Subscript[q, 2])(Subscript[u, 1]) = 0 – 1*1 = –1, 
											(Subscript[v, 2]) = (Subscript[v, 0]) – (Subscript[q, 2])(Subscript[v, 1]) = 1 – 1*(–2) = 3 
											    
122 = 122*1 + 0 ;		1 = syt(368, 123) = u a + v b,  missä  u = (Subscript[u, 2]) = –1  ja  v = (Subscript[v, 2]) = 3.

Siis  syt(368, 123) = 1 = –1* 368 + 3*123.  Tämä tulos on helppo varmistaa ja todeta oikeaksi.

Käsinlaskuesimerkki:  a = 1431  ja  b = 1368

Tässä  syt = 9,  mikä nähdään Eukleideen algoritmilla seuraavasti:

({{1431, "=", 1, "*", 1368, "+", 63}, {1368, "=", 21, "*", 63, "+", 45}, {63, "=", 1, "*", 45, "+", 18}, {45, "=", 2, "*", 18, "+", 9}, {18, "=", 2, "*", 9, "+", 0}})

Viimeinen nollasta eroava jakojäännös = 9 = syt(1431, 1368).

Laketaan vielä lineaarikombinaatio  9 = (Subscript[u, i])a + (Subscript[v, i])b.  Tässä  a = 1431  ja  b = 1368  sekä kuten edellä

(Subscript[r, i]) = (Subscript[r, i-2]) – (Subscript[q, i])(Subscript[r, i-1]) = (Subscript[u, i])a + (Subscript[v, i])b,  
missä  (Subscript[u, i]) = (Subscript[u, i-2]) – (Subscript[q, i]) (Subscript[u, i-1]), (Subscript[v, i]) = (Subscript[v, i-2])– (Subscript[q, i])(Subscript[v, i-1]),  
(Subscript[u, 0]) = 0  ja  (Subscript[v, 0]) = 1  sekä  (Subscript[u, 1]) = 1, (Subscript[v, 1]) = (Subscript[–q, 1]).
 
Keskitytään nyt vain kaikkein oleellisiimpaan, eli lukujen  (Subscript[u, i])  ja  (Subscript[v, i])  laskemiseen kullakin askeleella:
 
(Subscript[r, i-2]) =  (Subscript[q, i])(Subscript[r, i-1]) + (Subscript[r, i]) ;		(Subscript[r, i]) = (Subscript[r, i-2]) – (Subscript[q, i])(Subscript[r, i-1])= (Subscript[u, i])a + (Subscript[v, i])b ;			(Subscript[u, i]), (Subscript[v, i]), (Subscript[q, i])
-----------------------	         -----------------------------------		    ----------- 
1431 = 1*1368 + 63		63 = a – b = (Subscript[u, 1])a + (Subscript[v, 1])b;  			(Subscript[u, 1]) = 1,  (Subscript[v, 1]) = (Subscript[–q, 1]) = –1	

1368 = 21*63 + 45		45 = (Subscript[u, 2])a + (Subscript[v, 2])b;  				(Subscript[u, 2]) = (Subscript[u, 0]) – (Subscript[q, 2])(Subscript[u, 1]) = 0 – 21*1 = –21, 
										(Subscript[v, 2]) = (Subscript[v, 0]) – (Subscript[q, 2])(Subscript[v, 1]) = 1 – 21*(–1) = 22  

63 = 1*45 + 18		18 = (Subscript[u, 3])a + (Subscript[v, 3])b;				(Subscript[u, 3]) = (Subscript[u, 1]) – (Subscript[q, 3])(Subscript[u, 2]) = 1 – 1*(–21) = 22, 
										(Subscript[v, 3]) = (Subscript[v, 1]) – (Subscript[q, 3])(Subscript[v, 2]) = –1 – 1*22 = –23 

45 = 2*18 + 9			  9 =  (Subscript[u, 4])a + (Subscript[v, 4])b;				(Subscript[u, 4]) = (Subscript[u, 2]) – (Subscript[q, 4])(Subscript[u, 3]) = –21 – 2*22 = –65, 
										(Subscript[v, 4]) = (Subscript[v, 2]) – (Subscript[q, 4])(Subscript[v, 3]) = 22 – 2*(–23) = 68
										 
18 = 2*9 + 0			  9 = syt(1431, 1368) = u a + v b,  missä  u = (Subscript[u, 4]) = –65  ja  v = (Subscript[v, 4]) = 68.

Siis  syt(1431, 1368) = 9 = –65*1431 + 68*1368.  Tarkista vielä tämä tulos kertomalla luvut ja laskemalla saadut tulot yhteen.

Laajennetun Eukleideen algoritmin ohjelmointi Mathematicalla

Esitetään aluksi Eukleideen perusalgoritmi ilman lineaarikombinaatiota. Tällöin laskelmien rakenne on varsin yksinkertainen. Jos käyttäjän antama (positiivinen luku)  a  on pienempi kuin  b,  vaihdetaan ensin näiden lukujen  a  ja  b  järjestys:

Clear[f];
f[{a_,b_}]:=If[a≥b,{a,"=",Floor[a/b],"*",b,"+",a-Floor[a/b]*b},
f[{b,a}]];
f[{a_,_,_,_,b_,_,r_}]:=Module[{myPr=""},If[r==0,Print["\nTässä syt = ",b,".","\n\nTulos nähdään Eukleideen algoritmilla seuraavasti:\n"];myPr,{b,"=",Floor[b/r],"*",r,"+",b-Floor[b/r]*r}]];

Clear[Eukleides];
Eukleides[a_,b_]:=(
Print[(steps=Rest[NestWhileList[f,{a,b},(#=!= "")&]])//TableForm];Print["Viimeinen nollasta eroava jakojäännös = ",
Last[steps[[Length[steps]-2]]]," = syt(",a,", ", b,")."]
)

Esimerkki:

Eukleides[1234,2345]

Palautetaan seuraavaksi mieleen yllä todistetun laajennetun algoritmin pseudokoodi:

Algoritmi 2.2	Laajennettu Eukleideen algoritmi 

	syöte		a≥b>0
	alkuarvot	(Subscript[r, -1])=a; (Subscript[r, 0])=b;
			  (Subscript[u, -1])=1; (Subscript[u, 0])=0; (Subscript[v, -1]) =0; (Subscript[v, 0]) =1;n=0;
	while  (Subscript[r, n])>0  do  begin
					aseta  	n=n+1;
				tulosta	(Subscript[r, n-2])=(Subscript[q, n])(Subscript[r, n-1])+(Subscript[r, n]),  (Subscript[r, n-1]) > (Subscript[r, n]) ≥ 0;
				aseta 	(Subscript[u, n])=(Subscript[u, n-2])-(Subscript[q, n]) (Subscript[u, n-1]);
				aseta 	(Subscript[v, n])=(Subscript[v, n-2])-(Subscript[q, n]) (Subscript[v, n-1]);
				end
	aseta	 u=(Subscript[u, n-1]); v= (Subscript[v, n-1]);

Meillä on siis aluksi:

(Subscript[r, -1])=a; (Subscript[r, 0])=b; (a≥b>0)
(Subscript[u, -1])=1; (Subscript[u, 0])=0; (Subscript[v, -1]) =0; (Subscript[v, 0]) =1;n=0;
(Subscript[r, -1]) = a = (Subscript[q, 1])b+(Subscript[r, 1]);	(Subscript[r, 1]) = a – (Subscript[q, 1])b = (Subscript[u, 1])a + (Subscript[v, 1])b,  missä  (Subscript[u, 1]) =  (Subscript[u, -1]) – (Subscript[q, 1])(Subscript[u, 0]), (Subscript[v, 1]) = (Subscript[v, -1]) – (Subscript[q, 1])(Subscript[v, 0])
(Subscript[r, 0]) = b = (Subscript[q, 2])(Subscript[r, 1])+(Subscript[r, 2]);	(Subscript[r, 2]) = b – (Subscript[q, 2])(Subscript[r, 1]) = (Subscript[u, 2])a + (Subscript[v, 2])b,  missä  (Subscript[u, 2]) = (Subscript[u, 0]) – (Subscript[q, 2])(Subscript[u, 1]), (Subscript[v, 2]) = (Subscript[v, 0]) – (Subscript[q, 2])(Subscript[v, 1])
(Subscript[r, 1]) = (Subscript[q, 3])(Subscript[r, 2])+(Subscript[r, 3]);		(Subscript[r, 3]) = (Subscript[u, 3])a + (Subscript[v, 3])b,  missä  (Subscript[u, 3]) = (Subscript[u, 1]) – (Subscript[q, 3])(Subscript[u, 2]), (Subscript[v, 3]) = (Subscript[v, 1]) – (Subscript[q, 3])(Subscript[v, 2])
(Subscript[r, 2]) = (Subscript[q, 4])(Subscript[r, 3])+(Subscript[r, 4]);	  	(Subscript[r, 4]) = (Subscript[u, 4])a + (Subscript[v, 4])b,  missä  (Subscript[u, 4]) = (Subscript[u, 2]) – (Subscript[q, 4])(Subscript[u, 3]), (Subscript[v, 4]) = (Subscript[v, 2]) – (Subscript[q, 4])(Subscript[v, 3])

Esitetään nyt jakoalgoritmin suorittava funktio  jako  ja sitä käyttävä funktio  laajennettuEukleides:

Clear[jako];
jako[{a_,b_}]:=If[a≥b,
Print[(Subscript[r, -1]),"=",a,"=", (Subscript[q, 1]),"*",(Subscript[r, 0]),"+",(Subscript[r, 1]),"=",Floor[a/b],"*",b,"+",a-Floor[a/b]*b,";  ",(Subscript[r, 1]),"=",a-Floor[a/b]*b,"=",(Subscript[u, 1]),"a +",(Subscript[v, 1]),"b"," = ","(",1-0,")*",a," + (",0-Floor[a/b],")*",b];
{1,a, Floor[a/b], b, a-Floor[a/b]*b,{0,1},1-0,a,0-Floor[a/b],b} (* = {indeksi=n=1,(Subscript[r, -1]),(Subscript[q, 1]),(Subscript[r, 0]),(Subscript[r, 1]),{(Subscript[u, 0]),(Subscript[v, 0])},(Subscript[u, 1])=(Subscript[u, -1])-(Subscript[q, 1])*(Subscript[u, 0]),a,(Subscript[v, 1])=(Subscript[v, -1])-(Subscript[q, 1])*(Subscript[v, 0]),b} *),
jako[{b,a}]];
jako[{n_,r1_,q3_,r2_,r3_,{u2_,v2_},u3_,a_,v3_,b_}]:=Module[{i,q4,r4,u4,v4,nextStep},If[r3==0,"",
(q4=Floor[r2/r3];r4=r2-q4*r3;u4=u2-q4*u3;v4=v2-q4*v3;nextStep={i=n+1,r2,q4,r3,r4,{u3,v3},u4,a,v4,b};Print[(Subscript[r, i-2]),"=",r2,"=", (Subscript[q, i]),"*",(Subscript[r, i-1]),"+",(Subscript[r, i]),"=",q4,"*",r3,"+",r4,";  ",(Subscript[r, i]),"=",r4,"=",(Subscript[u, i]),"a +",(Subscript[v, i]),"b"," = ","(",u4,")*",a," + (",v4,")*",b];
nextStep)]];

Clear[laajennettuEukleides];
laajennettuEukleides[a_,b_]:=(Print["Laajennettu Eukleideen algoritmi toimii seuraavasti:"];
Print["a = ",Max[a,b],", b = ",Min[a,b]];
lastRelevantStep=NestWhile[jako,{a,b},(#=!= "")&,1,Infinity,-2];Print["Viimeinen nollasta eroava jakojäännös = ",lastRelevantStep[[5]]," = syt(",a,", ", b,")."];
Print["Lineaarikombinaatio:  ",lastRelevantStep[[5]]," = u a + v b = ","(",lastRelevantStep[[7]],")*",Max[a,b]," + (",lastRelevantStep[[9]],")*",Min[a,b],"."];);

Esimerkki:  laajennettuEukleides[123,368]

laajennettuEukleides[123,368]

Tarkistuslaskelmia luvuilla  a  ja  b  sekä tuloksena saaduilla luvuilla  u  ja  v:

lastRelevantStep  
(* siis {i,(Subscript[r, i-2]),(Subscript[q, i]),(Subscript[r, i-1]),(Subscript[r, i]),{(Subscript[u, i-1]),(Subscript[v, i-1])},(Subscript[u, i]),a,(Subscript[v, i]),b}, kun i = n-1 *)

Print["Lineaarikombinaatio  u a + v b = ","(",lastRelevantStep[[-4]],")*",lastRelevantStep[[-3]]," + (",lastRelevantStep[[-2]],")*",lastRelevantStep[[-1]],"  tuottaa sievennettynä luvun:"];

lastRelevantStep[[-4]]*lastRelevantStep[[-3]]+lastRelevantStep[[-2]]*lastRelevantStep[[-1]]

Tämähän on aivan oikein.

Esimerkki:  laajennettuEukleides[34527,18273645]

laajennettuEukleides[34527,18273645]

Tarkistuslaskelmia luvuilla  a  ja  b  sekä tuloksena saaduilla luvuilla  u  ja  v:

lastRelevantStep  
(* siis {i,(Subscript[r, i-2]),(Subscript[q, i]),(Subscript[r, i-1]),(Subscript[r, i]),{(Subscript[u, i-1]),(Subscript[v, i-1])},(Subscript[u, i]),a,(Subscript[v, i]),b}, kun i = n-1 *)

Print["Lineaarikombinaatio  u a + v b = ","(",lastRelevantStep[[-4]],")*",lastRelevantStep[[-3]]," + (",lastRelevantStep[[-2]],")*",lastRelevantStep[[-1]],"  tuottaa sievennettynä luvun:"];

lastRelevantStep[[-4]]*lastRelevantStep[[-3]]+lastRelevantStep[[-2]]*lastRelevantStep[[-1]]

Tämäkin on oikein.

Kokeillaan saadun syt(a,b) :n laskemista vielä Eukleideen perusalgoritmilla ilman lineaarikombinaatiota. Tällöin laskelmien rakenne on yksinkertainen. Samat laskelmat ovat toki näkyvissä jo edellisen tulostuksen vasemmanpuoleisessa reunassa.

Eukleides[34527,18273645]

Esimerkki:  a = Fibonacci[100]; b = Fibonacci[99];
laajennettuEukleides[354224848179261915075, 218922995834555169026]

a=Fibonacci[100]
b=Fibonacci[99]

laajennettuEukleides[a,b]

Tähän väliin jäävät ohjelman tulostukset on tarkoituksella poistettu.

Tarkistuslaskelmia luvuilla  a  ja  b  sekä tuloksena saaduilla luvuilla  u  ja  v:

lastRelevantStep  
(* siis {i,(Subscript[r, i-2]),(Subscript[q, i]),(Subscript[r, i-1]),(Subscript[r, i]),{(Subscript[u, i-1]),(Subscript[v, i-1])},(Subscript[u, i]),a,(Subscript[v, i]),b}, kun i = n-1 *)

Print["Lineaarikombinaatio  u a + v b = ","(",lastRelevantStep[[-4]],")*",lastRelevantStep[[-3]]," + (",lastRelevantStep[[-2]],")*",lastRelevantStep[[-1]],"  tuottaa sievennettynä luvun:"];

lastRelevantStep[[-4]]*lastRelevantStep[[-3]]+lastRelevantStep[[-2]]*lastRelevantStep[[-1]]

Tulos on oikein!

Näille suurille luvuille  Fibonacci[100]  ja  Fibonacci[99]  tarvittiin suurimman yhteisen tekijän laskemiseen vain   97 + 1 = 98  askelta, vaikka kyseessä on hankalin mahdollinen tapaus (kun algoritmin toiminnan nopeutta verrataan luvun  b  arvoon,  a >b ≥ 1). Todellakin, algoritmin toiminta on hitaimmillaan silloin, kun jakojäännös  (Subscript[r, k])  pienenee kussakin askeleessa  (Subscript[r, k-2])=(Subscript[q, k])(Subscript[r, k-1])+(Subscript[r, k])  mahdollisimman vähän.  Tällaiseen tilanteeseen puolestaan joudutaan, jos  (Subscript[r, k-2])=(Subscript[r, k-1])+(Subscript[r, k])  aina kun  2≤k≤n-1,  ts. jos jokaisella askeleella osamäärä  (Subscript[q, k])  saa arvon  1  (mahdollisesti ensimmäistä askelta  a = (Subscript[q, 1])b  + (Subscript[r, 1])  lukuunottamatta).  Tarkemmin tätä asiaa käsitellään päätekstin Kappaleessa 2.3.

Se että kaikki kertoimet  (Subscript[q, i]) ovat ykkösiä tapauksessa  a = Fibonacci[100],  b = Fibonacci[99]  näkyy helpoiten perusalgoritmista:

Eukleides[ a=Fibonacci[100],b=Fibonacci[99] ]

Huomautus.  Koska tässä lineaarikombinaatio  u a + v b = 1,  saadaan  u a – 1 = –v b,  ts.  u a ≡ 1 (mod b)  ja näin ollen  u ≡  (a^(-1)) (mod b).  Salakirjoituksissa tällaisilla käänteisalkioilla on hyvin keskeinen merkitys, kuten tullaan näkemään. Tämän viimeisen esimerkin tapauksessa lauseke  u a + v b  on
	
	(83621143489848422977)*354224848179261915075 + (–135301852344706746049)*218922995834555169026 = 1,

joten  
	83621143489848422977 ≡ (354224848179261915075^(-1)) (mod 218922995834555169026), 
	
ts. 

	83621143489848422977*354224848179261915075 ≡ 1 (mod 218922995834555169026).

Liite 2.  Ryhmien ja kuntien perusteet

1.  Ryhmät

1.1  Johdanto

Erilaisissa matematiikan probleemoissa törmätään usein muotoa  a + x = b  tai  a x = b  oleviin yhtälöihin, joissa tuntematon muuttuja on  x.  Lukujoukkoja koskevissa tarkasteluissa edellinen yhtälö johtaa negatiivisten lukujen määrittelyyn,  jälkimmäinen johtaa rationaalilukujen määrittelyyn.  Vastaavia yhtälöitä esiintyy myös matriiseilla.  Jos  A  on neliömatriisi, jonka determinantti on nollasta eroava, voidaan yhtälön  AX = B  ratkaisu esittää muodossa  X = (A^(-1))B.
Yhtälön  5 + x  = 2   ratkaisu perustuu eräisiin laskusääntöihin, jotka yleistettynä muodostavat ryhmän määritelmän:
                  5 + x = 2
                  –5 + (5 + x) = –5 + 2     	(lisätään alkio  –5)
                  (–5 + 5) + x = –5 + 2  	(liitäntä- eli assosiatiivisuusominaisuus  a + (b + c) = (a + b) + c )
                  0 + x         = –5 +2   	(laskettu  –5 + 5)
                   x              =  –5  + 2    	(luvun  0  ominaisuus)
                   x            =  –3            	(lasketaan  –5 + 2 )
Ratkaisussa käytettiin seuraavia kokonaislukujen ominaisuuksia:  Jokaisella kokonaisluvulla  a  on vastaluku  –a,  jolle  –a + a = 0.  Kokonaislukujen joukossa on neutraalialkio  0,  jolle  0 + a = a + 0 = a  kaikilla  a ∈ ℤ.  Lisäksi yhteenlasku on assosiatiivinen, eli  a + (b + c) = (a + b) + c.  Yhteenlaskussa ei laskujen suoritusjärjestyksellä ole siis väliä.

Yllä mainituja ominaisuuksia on monilla matemaattisilla objekteilla, mm. matriiseilla. Niitä sanotaan ryhmäominaisuuksiksi.

1.2  Ryhmän määritelmä ja esimerkkejä ryhmistä.

Määritelmä 1.  (Ryhmä, Group)  
Olkoon  G  ei-tyhjä joukko ja  *  tässä joukossa määritelty binäärioperaatio.  Pari  < G, * >  on ryhmä,  jos seuraavat ominaisuudet ovat voimassa:

1)  a*b ∈ G  aina kun  a  ja  b  ∈ G 	(G  on suljettu operaation  *  suhteen)   
2)  (a*b)*c = a*(b*c)  kaikilla  a,b,c ∈ G   (assosiatiivisuus) 
3)  on olemassa neutraalialkio  e,  jolle  e*a = a*e = a  kaikilla  a ∈ G
4)  kaikilla  a ∈ G  on olemassa käänteisalkio  (a^(-1)),  jolle  (a^(-1))*a = a*(a^(-1))= e

Huomautus.  Jatkossa binäärioperaatiota ei ole aina kaikissa yhteyksissä tarpeen tarkalleen yksilöidä.  Niissä tapauksissa, joissa  binäärioperaatio voidaan ymmärtää asiayhteyden perusteella, voidaan myös pelkkää joukkoa  G  nimittää ryhmäksi.

Esimerkki 1.  <ℤ, +>  on ryhmä, koska siinä on neutraalialkio  0  ja jokaisella luvulla on vastaluku  –a.  Sen sijaan  <ℤ, *>  ei ole ryhmä,  koska esimerkiksi luvulla  2  ei ole käänteisalkiota kertolaskun suhteen (luku 1/2 ei kuulu kokonaislukuihin).

Esimerkki 2.  ℚ ∖ {0}  on ryhmä kertolaskun suhteen, koska luku  1  on neutraalialkio ja kuuluu rationaalilukuihin. Lisäksi jokaisella rationaaliluvulla  (a/b) (≠ 0)  on käänteisluku  (b/a),  jolle  (b/a)* (a/b) = 1.

Määritelmä 2.  (Abelin ryhmä)  
Ryhmää  <G, *>  sanotaan Abelin ryhmäksi, 
jos  a*b = b*a  kaikilla  a, b ∈ G   (kommutatiivisuus).

Esimerkki 3.  <ℤ, +>  on Abelin ryhmä, koska  a + b = b + a   kaikille kokonaisluvuille  a  ja  b.

Esimerkki 4.  Ei-singulaaristen  2x2 –neliömatriisien joukko ei ole Abelin ryhmä, koska yleensä  AB ≠ BA   (tulo ei ole kommutatiivinen)

A=(({{1, 2}, {4, 5}}));  B=(({{-1, 2}, {3, 2}})); 
tulo1=A.B     //MatrixForm
tulo2=B.A     //MatrixForm

Esimerkki 5.  Joukko  (Subscript[ℤ, 5]) = {[0], [1], [2], [3], [4]}  on ryhmä kun laskutoimituksena on yhteenlasku modulo 5.  Seuraavasta yhteenlaskutaulusta nähdään kaikkien alkioiden vasta-alkiot.  Taulukko on symmetrinen diagonaalin suhteen, joten ryhmä on Abelin ryhmä.

taulukko=Table[Mod[x+y,5],{x,0,4},{y,0,4}]  //MatrixForm

Esimerkki 6.  Joukko  (Subscript[ℤ, 7]) ∖ {0}  eli {[1], [2], [3], [4], [5], [6]}  on Abelin ryhmä kertolaskun (mod 7) suhteen. Kertotaulu:

taulukko=Table[Mod[x y,7],{x,1,6},{y,1,6}] //MatrixForm

Mitkä ovat alkioiden  [4]  ja  [5]  käänteisalkiot tässä ryhmässä?

2.  Ryhmien perusominaisuudet

Lause 1.  Olkoon  <G, *>  ryhmä sekä  a, b  ja  c  joukon  G  alkioita.  Seuraavat implikaatiot ovat voimassa:

1)	jos  a*b = a*c,  niin  b = c,
2)	jos  b*a = c*a,  niin  b = c.

Todistus.  Olkoon  a*b = a*c.   Koska  a ∈ G,  alkiolla  a  on olemassa käänteisalkio  (a^(-1)),  jolle  (a^(-1))*a = e.
Nyt	(a^(-1))*(a*b) = (a^(-1))*(a*c),  josta assosiatiivisuuden perusteella 
          	((a^(-1))*a)*b = ((a^(-1))*a)*c  ja edelleen  e*b = e*c,  josta saadaan väite  b = c.
Vastaavasti osoitetaan lauseen toinen osa.   □

Lause 2.  Olkoon  <G, *>  ryhmä.  Tällöin yhtälöillä
a*x = b  ja  y*a = b  on yksikäsitteiset ratkaisut  x, y ∈ G.

Todistus.  Olkoon  a*x = b.  Tällöin  (a^(-1))*(a*x) = ((a^(-1))*a)*x = e*x = x.  Siis  x = (a^(-1))*(a*x) = (a^(-1))b.
Ratkaisu on siten  x = (a^(-1))b.  Osoitetaan vielä ratkaisun yksikäsitteisyys.
Olkoon  x  ja  x'  ratkaisuja, ts.  a*x = b  ja  a*x' = b.  Tällöin  a*x = a*x'  ja Lauseen 1 nojalla  x = x'.
Vastaavasti osoitetaan, että (yksikäsitteisesti)  y = b*(a^(-1)).   □

Lause 3.  Ryhmän  <G, *>   neutraalialkio  e  on yksikäsitteinen.
Alkion  a  käänteisalkio  (a^(-1))  on yksikäsitteinen.

Todistus jätetään harjoitustehtäväksi.

Seuraus 1.  Olkoot  a  ja  b  ryhmän  <G, *>  alkioita.
Tällöin  (((a*b))^(-1)) = (b^(-1))* (a^(-1)).

Todistus.  ((b^(-1))*(a^(-1)))*(a*b) = (b^(-1))*((a^(-1))*(a*b)) = (b^(-1))*(((a^(-1))*a)*b) = (b^(-1))*(e*b) = (b^(-1))*b = e.  
Vastaavalla tavalla osoitetaan, että  (a*b)*((b^(-1))*(a^(-1))) = e.   □

Harjoitus.   Abelin ryhmässä  <G, *>  on 3 alkiota:  neutraalialkio  e,  sekä  a  ja  b.  Kirjoita  ryhmän kertotaulu.

3.  Aliryhmät

Määritelmä 3.  (Ryhmän kertaluku)   
Äärellisen ryhmän  G  alkioiden lukumäärää sanotaan ryhmän  G  kertaluvuksi ja merkitään  |G|  tai  #G.  
(Yleisemmin joukon  S  alkioiden lukumäärää sanotaan sen kertaluvuksi ja merkitään  |S|.  Myös termejä kardinaaliluku ja mahtavuus käytetään. )

Määritelmä 4.  (Aliryhmä)   
Olkoon ryhmän  <G, *>  osajoukko  H  suljettu operaation  *  suhteen (ts.  a,b ∈ H  =>  a*b ∈ H)  ja olkoon  H   (tarkemmin sanottuna <H, *>)  itsessään ryhmä operaation  *  suhteen.  Tällöin joukkoa  H  sanotaan ryhmän  G  aliryhmäksi  ja merkitään  H ≤ G.

Määritelmä 5.  (Aito ja triviaali aliryhmä)  
Jos  H  on ryhmän  G  aliryhmä ja  H ≠ G,  sanotaan että  H  on ryhmän  G  aito aliryhmä.  Ryhmä  {e}  on ryhmän  G  triviaali aliryhmä.

Esimerkki 1.  Joukko  H = {... , –4, –2, 0, 2, 4, ... }  on kokonaislukujen joukon aliryhmä, kun laskutoimituksena on yhteenlasku.   

Perustelu.  Ryhmäaksiomit toteutuvat, koska joukossa  H  on neutraalialkio 0,  jokaisella luvulla on vasta-alkio joukossa  H.  Lisäksi  H  on suljettu yhteenlaskun suhteen, koska parillisten lukujen summakin on parillinen.

Lause 4.  Ryhmän  G  osajoukko  H  on ryhmän aliryhmä jos ja vain jos
1)  	H  on suljettu ryhmän  G  ryhmäoperaation  suhteen,
2) 	neutraalialkio  e  kuuluu joukkoon  H,
3)  	jokaisella  joukon  H  alkiolla  a  on käänteisalkio  (a^(-1))  joukossa  H.

Todistus.  Kohta "vain jos, ts. ⟹":  Oletetaan, että  H  on ryhmän  G  aliryhmä. Tällöin ominaisuuksien 1–3 täytyy toteutua aliryhmän määritelmästä.  Kohta "jos, ts. ⟸":  Oletetaan, että ominaisuudet 1–3 ovat voimassa.  Tällöin riittää osoittaa, että joukossa  H  ovat voimassa ryhmäaksiomit.  Ehdot 2–3 takaavat neutraalialkion ja käänteisalkion olemassaolon.  Assosiatiivisuusominaisuus seuraa siitä, että joukon  H  alkiot ovat samalla joukon  G  alkioita, joilla assosiatiivisuus on voimassa, koska  G  on ryhmä.   □

4.  Sykliset ryhmät ja ryhmän generaattori

Määritelmä 6.  (Alkion potenssi) 
Olkoon  G  ryhmä ja  a  sen alkio sekä  m ∈ (SuperPlus[ℤ]).  Tällöin määritellään

(a^m) = a*a*a* ⋯ *a     (m tekijää) 
(a^0) = e   (neutraalialkio) 
(a^(-m)) = ((((a^(-1))))^m) = (a^(-1))*(a^(-1))*(a^(-1))* ⋯ * (a^(-1))     (m tekijää)

Huomautus.  Jatkossa lasketaan ilman välivaiheita siten, että seuraavat yhtäsuurudet ajatellaan tunnetuiksi:

	(a^m)*(a^n) = (a^(m+n))
	((((a^m)))^n) = (a^mn)
	(a^n)*(a^(-n))= (a^(-n))*(a^n)= e.  

Totea, että nämä sinällään varsin ilmeiset tulokset ovat voimassa aina kun  m, n ∈ ℤ.

Sykliset ryhmät

Lause 5.  Olkoon  G  ryhmä ja  a  sen alkio.  Tällöin 

                     H = {(a^n) |  n ∈ ℤ }

 on ryhmän  G  aliryhmä ja samalla pienin ryhmän  G  aliryhmä, joka sisältää alkion  a.

Todistus.  Osoitetaan, että Lauseen 4 ominaisuudet 1–3 ovat voimassa.
1)  Jos  x  ja  y  kuuluvat joukkoon  H,  niin niiden muoto on:  x = (a^n)  ja  y = (a^m).  Tällöin  x*y = (a^n)*(a^m)= (a^(n+m))  joten tulo  x*y ∈ H.
2)  (a^0) = e,  joten neutraalialkio  e ∈ H.  
3)  Jos  x ∈ H,  niin  x = (a^n).  Tällöin alkio  (a^(-n ))∈  H  ja  (a^n)*(a^(-n))= (a^(-n))*(a^n)= e,  joten  (a^(-n)) on alkion  x  käänteisalkio.
Osoitetaan vielä, että H  on pienin ryhmän  G  aliryhmä, joka sisältää alkion  a.  Tätä varten olkoon  K  ryhmän  G  aliryhmä, joka sisältää alkion  a.  Sulkeutuvuusominaisuuden perusteella myös  (a^(-1)) ∈ K,  ja  a*a, a*a*a, ... , eli yleisesti alkion  a  positiivisen eksponentin omaavat potenssit  (a^n) ∈ K.  Vastaavasti alkion  (a^(-1))  potenssit  (a^(-m))  kuuluvat joukkoon  K.  Koska  K  on ryhmä, myös neutraalialkio  e = (a^0) ∈ K.   Siis  K  sisältää kaikki potenssit  (a^n),  missä  n ∈ ℤ.  Siten  H ≤ K.  Näin ollen  H  on pienin ryhmän  G  aliryhmä, joka sisältää alkion  a.   □

Määritelmä 7.  (Syklinen aliryhmä <a>)  
Ryhmää  H = { (a^n) | n ∈ ℤ }  sanotaan alkion  a  generoimaksi ryhmän  G  sykliseksi aliryhmäksi  ja merkitään  <a>.

Ryhmän generaattori

Määritelmä 8.  (Ryhmän generaattori  g)
Jos alkion  a ∈ G  generoima syklinen aliryhmä on itse  G,  ts. jos  < a > = G,  niin alkiota  a  sanotaan ryhmän  G  generaattoriksi.  Ryhmää  G  sanotaan sykliseksi, jos on olemassa alkio  a ∈ G,  joka generoi ryhmän  G.

Esimerkki 1.   Alkio  [3]  generoi ryhmän  (Subscript[ℤ, 7]) = {[1], [2], [3], [4], [5], [6]},  kun operaationa on kertolasku modulo 7  (huom. tässä ja alla merkintä  (Subscript[ℤ, m])  tarkoittaa alkion  [0]  puuttumisen takia eri joukkoa, kuin päätekstin Kappaleessa 3).

Tuloksen, että alkio  [3]  generoi ryhmän  (Subscript[ℤ, 7]),  voi todeta oikeaksi laskemalla käsin, tai käyttämällä Mathematica-komentoa  PowerMod[3,n,7]. Tässä laskennallisesti helpossa tapauksessa voisi myös käyttää yksinkertaista kutsua  Mod[(3^n),7].

Table[PowerMod[3,n,7],{n,1,6}]

Esimerkki 2.  Alkio [2]  sen sijaan ei ole ryhmän  (Subscript[ℤ, 7])  generaattori, vaan generoi sen aliryhmän  {[1], [2], [4]}.

Table[PowerMod[2,n,7],{n,1,6}]

Tehtävä.  Olkoon  G =  (Subscript[ℤ, 13]) ={[1], [2], ... , [12]},  missä ryhmäoperaationa on kertolasku modulo 13.
Etsi ryhmän  G  generaattorit.

Nimityksiä.  Olkoon  a  ryhmän  G  alkio.  Jos syklinen aliryhmä  <a>  on äärellinen, niin alkion  a  kertaluvuksi sanotaan sen määrittämän syklisen aliryhmän kertalukua  | <a> |.  Muutoin sanotaan, että alkion  a  kertaluku on ääretön.  Alkion  a  kertaluvusta käytetään merkintää  ord(a).

5.  Syklisten ryhmien ominaisuuksia

Lause 6.  Jokainen syklinen ryhmä on Abelin ryhmä.

Todistus.  Kuten Kappaleen 1 Määritelmä 2 esitti, ryhmä  G  on Abelin ryhmä, jos  a*b = b*a  kaikilla  a, b ∈ G.  Olkoon nyt  G  syklinen ryhmä ja  a  sen generaattori.  Jos  x  ja  y ∈ G,  on olemassa  n, m ∈ ℤ  siten, että  x = (a^m)  ja  y = (a^n).  Tällöin  x*y = (a^m)*(a^n)= (a^(m+n))= (a^n)*(a^m)= y*x.   □

Lause 7.  Syklisen ryhmän aliryhmä on syklinen.

Todistus.  Olkoon  G  syklinen ryhmä,  a  sen generaattori ja olkoon  H  ryhmän  G  aliryhmä.
Jos  H = {e}, niin  H = <e>  on syklinen.  Muutoin  (a^n)∈ H eräällä  n∈ℤ.  Olkoon  m  pienin positiivinen kokonaisluku, jolle  (a^m) ∈ H.  Osoitamme, että  g = (a^m)  generoi aliryhmän  H, eli että  <g> = H.  Osoitetaan siis, että jokainen  b ∈ H on  alkion  g  potenssi.  Koska  b ∈ H,  ja  H  on ryhmän  G  aliryhmä, on  b = (a^n)  jollekin  n∈ℤ.  Jakoalgoritmin mukaan  n = qm + r  joillekin kokonaisluvuille  q  ja  r,  missä  0 ≤ r < m.  Siten  (a^n)= (a^(qm + r)) = ((((a^m)))^q)*(a^r).  Tästä seuraa, että  (a^r) = ((((a^m)))^(-q))*(a^n),  joka kuuluu joukkoon  H,  koska  ((((a^m)))^(-q))  ja  (a^n) ovat aliryhmän  H  alkioita.  Koska  0 ≤ r < m  ja  m  oli pienin positiivinen kokonaisluku, jolle  (a^m)∈ H,  täytyy olla  r = 0.  Siten  b = (a^n) = (a^(qm + r)) = ((((a^m)))^q) = (g^q),  joten  g = (a^m)  generoi aliryhmän  H.  Näin ollen  H  on syklinen.   □

Seuraus 2.  Kokonaislukujen joukon sykliset aliryhmät yhteenlaskun suhteen ovat ryhmät 
nℤ  =  {na |  a ∈ ℤ }.

Esimerkki 1.  Ryhmä  3ℤ = {..., –6, –3, 0, 3, 6, ...}  on kokonaislukujen joukon syklinen aliryhmä yhteenlaskun suhteen.

Syklisten ryhmien rakenne

Olkoon  G  syklinen ryhmä ja  a  sen generaattori.  Tarkastellaan tilanteita, jossa kertaluku  |G|  (tai #G)  on  1) ääretön ja  2) äärellinen: 
1)  Jos  G  on ääretön, kaikki generaattorin  a  potenssit ovat keskenään erisuuria.
Vastaoletus:  On olemassa erisuuret  h  ja  k  (h > k)  siten, että  (a^h) = (a^k).  Tällöin kertomalla alkiolla  (a^(-k))  saadaan  (a^(h-k))= e.  Olkoon  m  pienin positiivinen luku, jolle  (a^m) = e.  Osoitetaan, että ryhmällä  G  on tällöin vain  m  erisuurta alkiota  e, a, (a^2), ... , (a^(m-1)).  Olkoon  (a^n)∈ G. Tällöin jakoalgoritmin nojalla  n = qm + r,  missä  0 ≤ r < m,  ja  (a^n)= (a^(qm+r)) = ((((a^m)))^q)*(a^r) = (e^q)*(a^r) = (a^r).  Siis  (a^n)  on jokin alkioista  e, a, ... , (a^(m-1))  ja  G  on äärellinen.  Vastaoletus on väärä ja siten kaikki alkion  a  potenssit ovat erisuuria.   □

2)  Jos  G  on äärellinen,  kaikki generaattorin  a  potenssit eivät voi olla erisuuria, vaan on olemassa  h  ja  k  (h > k),  joille  (a^h) = (a^k),  josta  (a^(h-k))= e.  Olkoon  m  pienin positiivinen kokonaisluku, jolle  (a^m) = e  (m  on olemassa, koska edellä  (a^(h-k))= e, h > k).  Tällöin ryhmä  G  koostuu alkioista  e, a, (a^2), ... , (a^(m-1))  ja  m  on sen kertaluku.   □

Lause 8.  Joukko  (Subscript[ℤ, n]) = {[0], [1], [2], ..., [n – 1]}  laskutoimituksena yhteenlasku modulo  n,  on syklinen ryhmä.

Perustelu.  Esimerkiksi alkio  [1]  on ryhmän generaattori, sillä jokainen joukon alkio voidaan esittää muodossa  k [1] = [1] + [1] + ⋯ + [1]  (k termiä),  missä  k  on kokonaisluku väliltä  [0, n – 1].  Neutraalialkio on  [0],  koska   [0] + x = x + [0] = x  kaikilla  x ∈ (Subscript[ℤ, n]).  Alkion  x  käänteisalkio on  [n] – x,  sillä  x + ([n] – x) = ([n] – x) + x = [n] = [0]  modulo  n.   □

Huomautus.  Olemme lainanneet merkintätavan kertolaskuoperaation yhdeydessä käytetystä tavasta.  Aina kun operaatio   *  on yhteenlasku  (+),  niin  (a^n);  n > 0;  tulkitaan monikertana  na = a + a + a + ⋯  + a  (n termiä),  (a^0) = e  ja  (a^(-n));  n > 0;  tulkitaan monikertana  n(-a) = (-a) + (-a) + (-a) + ⋯  + (-a)  (n termiä).

Äärellisten syklisten ryhmien aliryhmistä

Lause 9.  Olkoon  G  äärellinen syklinen ryhmä, jonka kertaluku on  n  ja olkoon  a  sen generaattori.  Olkoon  b = (a^s).  Tällöin  b  generoi ryhmän  G  syklisen aliryhmän  H,  jossa on  n/d  alkiota, missä  d = syt(n, s).

Todistus.  Se, että  b  generoi syklisen aliryhmän  H,  on osoitettu Lauseessa 7.  Osoitetaan, että aliryhmässä  H  on  n/d  alkiota. Seuraten Lauseen 7 todistusta, aliryhmässä  H  on  m  alkiota, missä  m  on pienin positiivinen luku, jolle  (b^m)= e.  Nyt  b = (a^s)  ja  (b^m) = (a^(sm ))= e,  joten  n | ms.  Mikä on pienin positiivinen kokonaisluku  m,  jolle  n | ms?  Olkoon  d = syt(n, s). Tällöin  d  voidaan esittää lineaarikombinaationa muodossa  d = un + vs,  missä  u,v ∈ ℤ.  Koska  d  on tekijänä sekä luvuissa  n  ja  s,  niin  1 = u (n/d) + v (s/d),  missä sekä  n/d  ja  s/d  ovat kokonaislukuja.  Tällöin  n/d  ja  s/d  ovat suhteellisia alkulukuja.  Olkoon  m  pienin sellainen luku, että  ((m s)/n)= ((m s / d)/(n/d)) on kokonaisluku.  Nyt  n/d  on tekijänä osamäärässä  ms/d  ja tästä seuraa, että  n/d  on luvun  m  tekijä.  Pienin tällainen luku  m = n/d.  Siten aliryhmän  H  kertaluku on  n/d.   □

Seuraus 3.  Jos  a  on äärellisen syklisen ryhmän  G  generaattori ja  | G | = n,  niin 
kaikki muut generaattorit ovat muotoa  (a^r),  missä  syt(r, n) = 1.

6.  Sivuluokat ja Lagrangen teoreema

Sivuluokat

Määritelmä 9.  (Sivuluokka)   
Olkoon   H  ryhmän  G  aliryhmä.  Joukon  G  osajoukkoa  aH = {a*h | h∈H },  missä  a∈G,  sanotaan alkion  a  generoimaksi ryhmän  H  vasemmaksi sivuluokaksi.  Vastaavasti joukkoa  Ha = {h*a | h∈H },  a∈G,  sanotaan alkion  a  generoimaksi ryhmän  H  oikeaksi sivuluokaksi.

Jos  H  on ryhmän  G  aliryhmä, jokainen ryhmän  G  alkio kuuluu johonkin ryhmän  H  sivuluokkaan.  (Jos  x  on mielivaltainen ryhmän  G  alkio, niin  x = x*(h^(-1))*h,  missä  h ∈ H on mielivaltainen.  Tällöin  x  kuuluu ryhmän  H  sivuluokkaan  aH,  missä  a = x*(h^(-1)).)

Lause 10.  Ryhmän  G  aliryhmän  H  jokaisella sivuluokalla on yhtä monta alkiota.

Todistus.  Olkoon  G  ryhmä ja  H  sen aliryhmä.  Olkoon  g  ryhmän  G  alkio.  Määritellään kuvaus  f: H -> gH  siten, että  f(x) = g*x  kaikilla  x ∈ H.  Osoitetaan, että  f  on bijektio.  Olkoot  g*x  ja  g*y  kaksi sivuluokan  gH  alkiota ja  g*x = g*y.  Koska  G  on ryhmä, kertomalla alkion  g  käänteisalkiolla saadaan  x = y.  Kuvaus  f  on siis bijektio ja siten kaikilla aliryhmän  H  vasemmanpuolisilla sivuluokilla on sama määrä alkioita.  Samoin todistetaan väite oikeanpuolisille sivuluokille.  Näin ollen aliryhmän  H  sivuluokat muodostavat ryhmän  G  osituksen (partition), ts. näiden sivuluokkien unioni on  G  ja  jokaisen sivuluokkaparin leikkausjoukko on tyhjä joukko.   □

Lause 11.  (Lagrangen teoreema)  
Äärellisen ryhmän  G  aliryhmän  H  kertaluku on ryhmän  G  kertaluvun tekijä.

Todistus.  Olkoon  n  ryhmän  G  kertaluku ja  m  aliryhmän  H  kertaluku.  Lauseen 10 mukaan jokaisessa aliryhmän  H  sivuluokassa on täsmälleen  m  alkiota.  Olkoon  r   ryhmän  H  sivuluokkien lukumäärä, kun luokat on muodostettu ryhmän  G  vasemmista sivuluokista.  Tällöin Lauseen 10 todistuksen perusteella  n = rm,  joten  m  on todellakin kertaluvun  n  tekijä.   □

Seuraus 4.  Jokainen ryhmä, jonka kertaluku on alkuluku, on syklinen.

Todistus.  Olkoon  G  ryhmä ja alkuluku  p  sen kertaluku.  Olkoon  a ≠ e  ryhmän  G  alkio ja  <a>  sen virittämä syklinen aliryhmä.  Tällöin aliryhmässä  <a>  on ainakin alkiot  e  ja  a.  Lauseen 10 nojalla syklisen aliryhmän  <a>  kertaluku  m  on tekijänä ryhmän  G  kertaluvussa  p,  mutta koska  p  on alkuluku,  m = p  ja  <a>  on  G,  joten ryhmä  G  on syklinen.   □

Lause 12.  Äärellisen ryhmän jokaisen alkion kertaluku on tekijänä ryhmän kertaluvussa.

Todistus.  Olkoon  G  äärellinen ryhmä, jonka kertaluku on  n  ja olkoon  a  ryhmän  G  alkio.  Tällöin alkion  a  kertaluku (siis ord(a))  on määritelmän mukaan sen generoiman syklisen aliryhmän  <a>  kertaluku – ja  <a>  on ryhmän  G  aliryhmä.  Lauseen 11 nojalla alkion  a  kertaluku on tekijänä ryhmän  G  kertaluvussa.   □

Onko Lause 12 voimassa myös toiseen suuntaan? 
Voidaan osoittaa, että jos  G  on Abelin ryhmä, sen kertaluvun jokaista tekijää  k  kohden löytyy ryhmän  G  alkio, jonka kertaluku on  k.

7.  Renkaat ja kunnat

Useimmat lukijat tuntevat rationaali-, reaali ja kompleksilukujoukkojen yhteen- ja kertolaskua koskevat ominaisuudet, ts. niiden algebralliset rakenteet. Näistä joukoista, yhdessä niissä määriteltyjen laskutoimitusten kanssa, käytetään nimitystä kunta.

Diskreetissä matematiikassa, erityisesti kryptologiassa ja koodausteoriassa, äärellisten kuntien teoria on keskeinen. Esittelemme seuraavassa lyhyesti tarvittavat käsitteet. Kunnan määritelmä pohjautuu ryhmän käsitteeseen, jota käsittelimme edellä. Ennen kuin esitämme kunnan määritelmän, on kuitenkin käytännöllistä ensin määritellä rakenne nimeltä rengas. Esimerkiksi kokonaislukujen joukko  ℤ  muodostaa renkaan, mutta ei muodosta kuntaa, koska nollasta eroavilla alkioilla ei yleensä ole kertolaskun käänteisalkiota.

Käytämme alla kahdesta binäärioperaatiosta tarkoituksella merkintöjä  +  ja  ·,  koska niitä käytetään tutujen joukkojen  ℤ, (Subscript[ℤ, m]), ℚ, ℝ  ja  ℂ  yhteydessä. Kuitenkin merkintöjen tarkoitus on olla voimassa yleisesti mitä erilaisempien joukkojen ja niissä määriteltyjen operaatioiden yhteydessä. Vaikka yleinen abstrakti rakenne on yhteinen, nämä operaatiot voivat ensi näkemältä poiketa paljonkin siitä, mikä tähän saakka on ollut tuttua yhten- ja vähennyslaskuoperaattoreiden yhteydestä. Näihin (abstraktin algebran) rakenteisiin voi perehtyä lisää lukemalla esimerkiksi kirjoja Nicholson [8] ja van Tilborg [11].

Rengas

Määritelmä 10.  (Rengas, Ring)
Kolmikko  (R,+,· )  on rengas, jos
1)  <R, +>  on kommutatiivinen (vaihdannainen) ryhmä (siis Abelin ryhmä).
     Tässä yksikköalkiosta (ts. neutraalialkiosta) käytetään merkintää  0.
2)  Operaatio  ·  on assosiatiivinen (liitännäinen).
3)  Distributiivisuus (osittelu) on voimassa, ts. kaikille  r, s, t∈R  on voimassa
     r·(s+t)=r·s+r·t  ja  (r+s)·t=r·t+s·t.

Ryhmän  <R,+>  alkion  a   käänteisalkiota sanotaan vasta-alkioksi ja siitä käytetään merkintää  -a,  samoin kirjoitamme  2a  yhteenlaskun  a+a  asemasta, ja  3a  tarkoittaa  a+a+a,  jne.  Myös  a – b  on lyhennysmerkintä, joka tarkoittaa samaa kuin  a + (-b).  Huomattakoon myös, että  0  todellakin käyttäytyy kuten nolla-alkio, koska kaikilla  r∈R  on voimassa  0r=(r+(-r))r=(r^2)-(r^2)=0  ja vastaavasti  r 0=0.

Olkoon  (R,+,· )  rengas ja  S  joukon  R   osajoukko siten, että  (S,+ ,· )  on itsekin rengas. Tällöin rengasta  (S,+ ,· )  sanotaan renkaan  (R,+,· )  alirenkaaksi. Esimerkiksi  (6ℤ,+ ,· )  on renkaan (2ℤ,+ ,· )  alirengas, ja tämä puolestaan on renkaan  (ℤ,+ ,· )  alirengas.

Olettakaamme, että operaatio  ·  on kommutatiivinen (vaihdannainen) joukossa  R\{0}.  Tällöin sanomme, että rengas  (R,+ ,· )  on kommutatiivinen.  Esimerkkeinä kommutatiivisista renkaista ovat  (ℝ,+ ,· ), (ℚ,+ ,· ), (ℤ,+ ,· ),  ja myös  (m ℤ,+ ,· ),  kun  m≠0.

Tarkastellaan rengasta  (R,+,· ).  Käytetään merkintää  (SuperStar[R])  niistä joukon  R  alkioista, joilla on käänteisalkio kertolaskun suhteen. Tapauksessa, jossa  R ≠ {0}  ja  (SuperStar[R]) =  R\{0},  ts. kun jokaisella nollasta eroavalla joukon  R  alkiolla on käänteisalkio kertolaskun suhteen, sanotaan että rengas   (R,+,· )  on  jakorengas (divison ring, skew field).  Kommutatiivisesta jakorenkaasta käytetään nimitystä kunta.

Alla muotoilemme kunnan määritelmän vielä toisellakin tavalla. Ennen sen esittämistä mainitaan vielä, että Wedderburn'in lauseen mukaan jokainen äärellinen jakorengas on kunta (ks. Nicholson [8]). Tämä näyttäisi viittaavan siihen, että epäkommutatiiviset jakokunnat olisivat harvinaisia. Kuitenkin esimerkki sellaisesta, nimittäin kvaternionit, on tunnettu jo vuodesta 1843.

Kunta

Määritelmä 11.  (Kunta, Field) 
Kolmikko  (F,+ ,· )  on kunta, jos
1)  <F,+>  on kommutatiivinen ryhmä (siis Abelin ryhmä). 
      Yksikköalkiosta (ts. neutraalialkiosta) käytetään merkintää  0.
2)  <F \ {0},·>  on kommutatiivinen ryhmä (siis Abelin ryhmä).  
      Kertolaskun yksikköalkiosta käytetään merkintää  e.
3)  Distributiivisuus (osittelu) on voimassa kuten renkaan tapauksessa yllä.

Päinvastoin kuin joissakin renkaissa, kunnassa ei voi olla niin sanottuja nollan tekijöitä (zero-divisors), ts. alkioita  a ≠ 0  ja  b ≠ 0,  joiden tulo  a·b =  0.  Todellakin, oletetaan, että olisi voimassa  a·b=0  ja  a≠0. Tällöin,   b=e· b=((a^(-1))·a)·b=(a^(-1))·(a· b)=(a^(-1))·0=0, joten jokainen kunnan  F  alkio olisi nolla.

Jos kunnan  (F,+ ,· )  alirenkaalla  (K,+ ,· )  on kunnan rakenne, kutsumme sitä kunnan (F,+ ,· )  alikunnaksi.

Esimerkkejä kunnista ovat muun muassa rationaaliluvut  (ℚ,+ ,· ),  reaaliluvut  (ℝ,+ ,· )  ja kompleksiluvut  (ℂ,+ ,· ).  Näistä jokainen on aina seuraavan lukujoukon alikunta.

Sanomme, että äärellisen ryhmän  <G,*>,  renkaan  (R,+ ,· ),  tai kunnan  (F,+ ,· )  kertaluku on  n,   jos  G,  vastaavasti  R  ja  F,  ovat äärellisiä joukkoja, joiden alkioiden määrä (kardinaaliluku) on  n.  Äärellisten kuntien tapauksessa on tapana merkitä kertalukua luvulla  q.

Osoittautuu, että kertalukua  q  olevia äärellisiä kuntia on olemassa vain, jos  q  on jonkin alkuluvun potenssi, ts.  q = (p^n)  jollekin alkuluvulle  p  ja kokonaisluvulle  n ≥ 1.  Lisäksi nämä äärelliset kunnat ovat itse asiassa yksikäsitteiset (isomorfiset) jokaista kiinnitettyä alkuluvun potenssia  q  kohti. Tämän vuoksi kertalukua  q  olevista äärellisistä kunnista käytetään yleisesti merkintää  (Subscript[𝔽, q])  tai  GF(q)  (missä GF tarkoittaa Galoisin kuntaa (Galois Field) ranskalaisen Galoisin mukaan).

Esimerkiksi lähteissä Nicholson [8] ja van Tilborg [11] esitetään tärkeitä algebran tuloksia runsaasti lisää. Ne tulokset ovat usein hyvin merkittäviä myös salakirjoitusten kannalta, esimerkkinä elliptisiä käyriä koskevat sovellutukset. Kirjan van Tilborg [11] mukana tulevalla CD-levyllä koko kirja [11] on toteutettu hypertekstimuodossa Mathematica-ympäristössä, jossa algoritmitmeja voidaan lisäksi heti kokeilla muutetuilla lähtöarvoilla. Muidenkin ympäristöjen ohjelmoitsijat voivat löytää tuon toteutuksen algoritmeista kiinnostavia ja hyödyllisiä rakenteita sekä yksityiskohtia.