Auli Toikkonen
Aritmeettiset funktiot: kuuluisia matemaatikkoja ja keskeisiä käsitteitä
Informaatioteknologian ja viestinnän tiedekunta Pro gradu -tutkielma
Tiivistelmä
Auli Toikkonen: Aritmeettiset funktiot: kuuluisia matemaatikkoja ja keskeisiä käsitteitä
Pro gradu -tutkielma Tampereen yliopisto
Matematiikan ja tilastotieteen tutkinto-ohjelma Heinäkuu 2021
Tämän tutkielman aiheena ovat aritmeettiset funktiot. Aritmeettiset funktiot ovat kuvauksia, jotka määritellään positiivisille kokonaisluvuille ja jotka saavat arvoksi kompleksilukuja. Työssä tutustutaan aritmeettisten funktioiden keskeisiin käsitteisiin ja kuuluisiin matemaatikoihin. Aluksi määritellään Dirichlet’n tulo ja multiplikatii- vinen funktio. Sen jälkeen esitetään Möbiuksen ja Eulerin funktiot, jotka ovat mul- tiplikatiivisia. Seuraavaksi käsitellään täydellisesti multiplikatiivisia funktioita, joista esimerkkinä on Liouvillen funktio. Tämän jälkeen siirrytään modulaariseen aritme- tiikkaan sekä määritellään täydellisen ja supistetun jäännössysteemin käsitteet. Li- säksi esitetään Ramanujanin summakaava. Sen jälkeen osoitetaan tekijäfunktioiden ominaisuuksia ja määritellään täydelliset luvut, Mersennen alkuluvut ja Fermat’n lu- vut. Lopuksi todistetaan tekijäfunktion keskiarvon kaava. Matemaattisen käsittelyn ohella tutkielmassa tarkastellaan myös teorioiden ja niiden keksijöiden historiaa.
Avainsanat: Dirichlet’n tulo, multiplikatiivinen funktio, Möbiuksen funktio, Eulerin funktio, Liouvillen funktio, täydellinen jäännössysteemi, Ramanujanin summa, tekijäfunktio, Mersennen alkuluku, täydellinen luku, Fermat’n luvut.
Tämän julkaisun alkuperäisyys on tarkastettu Turnitin OriginalityCheck -ohjelmalla.
Sisällys
1 Johdanto 4
2 Aritmeettisten funktioiden peruskäsitteitä 5
2.1 Peter Gustav Lejeune Dirichlet . . . 5
2.2 Dirichlet’n tulo . . . 6
2.3 Multiplikatiiviset funktiot . . . 8
2.4 August Ferdinand Möbius . . . 11
2.5 Möbiuksen funktio . . . 11
2.6 Leonhard Euler . . . 14
2.7 Eulerin funktio . . . 15
2.8 Täydellisesti multiplikatiiviset funktiot . . . 18
2.9 Joseph Liouville . . . 21
2.10 Liouvillen funktio . . . 21
3 Modulaarinen aritmetiikka ja Ramanujanin summa 23 3.1 Karl Friedrich Gauss . . . 23
3.2 Täydellinen ja supistettu jäännössysteemi . . . 24
3.3 Srinivasa Ramanujan . . . 30
3.4 Ramanujanin summa . . . 31
4 Tekijäfunktioiden ominaisuuksia 36 4.1 Tekijäfunktio . . . 36
4.2 Marin Mersenne . . . 38
4.3 Mersennen alkuluku ja täydellinen luku . . . 38
4.4 Pierre de Fermat . . . 40
4.5 Fermat’n luvut . . . 41
4.6 Tekijäfunktion keskiarvo . . . 43
Lähteet 53
1 Johdanto
Tässä tutkielmassa käsitellään lukuteorian alaan kuuluvia aritmeettisia funktiota.
Aritmeettiset funktiot ovat kuvauksia, jotka määritellään positiivisille kokonaislu- vuille ja jotka saavat arvoksi kompleksilukuja. Matemaattisen tarkastelun lisäksi tässä työssä syvennytään monen eri merkittävän matemaatikon historiaan ja heidän vaikutuksiinsa matematiikan ja erityisesti lukuteorian kehitykselle.
Luvussa 2 tutustutaan ensin matemaatikko Peter Gustav Lejeune Dirichlet’n saa- vutuksiin, määritellään Dirichlet’n tulo ja esitetään sen ominaisuuksia. Tämän jäl- keen esitellään multiplikatiiviset funktiot ja osoitetaan Dirichlet’n tulon säilyttävän multiplikatiivisuuden. Sen jälkeen keskitytään August Ferdinand Möbiuksen his- toriaan, määritellään Möbiuksen funktio ja todistetaan Möbiuksen käänteiskaava.
Sitten perehdytään Leonhard Eulerin elämän vaiheisiin ja tieteellisiin tuotoksiin se- kä määritellään Eulerin funktio. Viimeisenä esitetään täydellisesti multiplikatiiviset funktiot, joista esimerkkinä on Joseph Liouvillen mukaan nimetty Liouvillen funktio.
Luvussa 3 käsitellään modulaarista aritmetiikkaa. Luvun alussa tarkastellaan kongruenssin kehittäjän Karl Friedrich Gaussin historiaa, jonka jälkeen todistetaan kongruenssiin liittyviä perustuloksia sekä määritellään täydellisen ja supistetun jään- nössysteemin käsitteet. Tämän jälkeen perehdytään Srinivasa Ramanujaniin ja hänen kehittämäänsä summakaavaan.
Tutkielman viimeisessä luvussa käsitellään tekijäfunktioiden ominaisuuksia. Lu- kuun sisältyvät Marin Mersennen ja Pierre de Fermat’n historiaosuudet. Lisäksi mää- ritellään Mersennen alkuluvut, täydelliset luvut ja Fermat’n luvut. Lopuksi syven- nytään tekijäfunktion keskiarvon kaavan todistamiseen ja siihen läheisesti liittyvän Dirichlet’n tekijäprobleeman historiaan.
Lukijalta edellytetään lukuteorian perustuloksien hallintaa esimerkiksi yliopiston algebran kurssien pohjalta. Tässä tutkielmassa on pääosin käytetty lähdeteoksina A.
Gioian kirjaaThe Theory of Numbers, K. Rosenin teostaElementary Number Theory ja T. Apostolin kirjaaIntroduction to Analytic Number Theory.
2 Aritmeettisten funktioiden peruskäsitteitä
2.1 Peter Gustav Lejeune Dirichlet
Saksalainen Peter Gustav Lejeune Dirichlet (1805–1859) oli yksi 1800–luvun suu- rimmista lukuteoreetikoista. Dirichlet oli nuoresta pitäen kiinnostunut matematii- kasta, joten hän suuntasi Pariisin yliopistoon opiskelemaan alaa. Pariisissa häntä opettivat esimerkiksi Jean-Baptiste Fourier, Jean Hachette, Pierre-Simon Laplace ja Siméon Poisson, jotka olivat aikansa tunnettuja tieteenharjoittajia. Dirichlet opiske- li myös itsenäisesti Carl Gaussin oppeja ja kuljetti aina mukanaan Gaussin teosta Disquisitiones arithmeticae(suomeksi Aritmeettisia tutkimuksia). [10, s. 237]
Ensimmäisessä tieteellisessä julkaisussaan Dirichlet todisti osan Fermat’n suu- resta lauseesta, kun 𝑛 = 5. Lauseessa esitetään, että yhtälöllä 𝑥𝑛+ 𝑦𝑛 = 𝑧𝑛 ei ole olemassa kokonaislukuratkaisuja𝑥 , 𝑦ja𝑧, kun kokonaisluku𝑛 >2. Ennestään Leon- hard Euler ja Pierre de Fermat olivat todistaneet tapaukset, kun 𝑛 = 3 ja 𝑛 = 4.
Tapaus𝑛 =5 koostui kahdesta todistusosuudesta, joista Dirichlet onnistui ratkaise- maan toisen osuuden. Dirichlet’n julkaisun pohjalta Adrien-Marie Legendre jatkoi todistustyön loppuun ja koko ratkaisu julkaistiin vuonna 1825. Myöhemmin Dirichlet ratkaisi kyseisen yhtälön myös, kun𝑛 =14. [10, s. 237–238]
Dirichlet kirjoitti habilitaatiotutkielmansa polynomien jaottomuudesta, aloitti opettamaan Breslaun yliopistossa ja jatkoi edelleen opettajauraansa Berliinissä sijait- sevassa sotakorkeakoulussa. Vuonna 1828 Dirichlet sai professorin viran Berliinin yliopistosta, joka oli yksi aikansa arvostetuimmista instituutioista. Gaussin meneh- dyttyä vuonna 1855 Dirichlet vastaanotti Gaussin kunnianarvoisen paikan Göttin- genin yliopistossa Saksassa. Göttingenissä Dirichlet’n oppilaana oli muun muassa Bernhard Riemann. Dirichlet’n kuoltua Riemannista tuli hänen seuraajansa myötä- vaikuttaen funktioteoriaan, Fourier’n sarjoihin ja geometriaan. [10, s. 238–239]
Dirichlet’n vaikutus matematiikkaan on ollut valtava, erityisesti analyyttisen lu- kuteorian osalta. Fermat’n suuren lauseen lisäksi Dirichlet keskittyi tutkimuksis- saan esimerkiksi neliöjäännöslauseeseen ja alkulukujen perustuloksiin aritmetiikas- sa. Hän loi analyyttisesta lukuteoriasta tutun Dirichlet’n sarjan, antoi oman tarkan määritelmän funktiolle, määritteli ensimmäisenä sarjojen suppenemisen ja loi pohjaa Fourier’n sarjalle ja monille muillekin teorioille. [10, s. 238–239]
2.2 Dirichlet’n tulo
Tässä alaluvussa keskitytään Dirichlet’n tuloon ja tutustutaan Dirichlet’n tulon pe- rusominaisuuksiin.
Määritelmä 2.1. (Vrt. [9, s. 13]).Aritmeettinen funktioon kuvaus 𝑓 :ℤ+ →ℂ, eli se on määritelty positiivisille kokonaisluvuille ja se saa arvoksi kompleksilukuja.
Määritelmä 2.2(Dirichlet’n tulo). (Ks. [9, s. 13]). Aritmeettisten funktioiden 𝑓 ja 𝑔Dirichlet’n tulo(eliDirichlet’n konvoluutio) 𝑓 ∗𝑔määritellään kaavalla
(𝑓 ∗𝑔) (𝑛)=∑︁
𝑑|𝑛
𝑓(𝑑)𝑔 (︂𝑛
𝑑 )︂
, 𝑑 , 𝑛 ∈ℤ+.
Esimerkki 2.1. Lasketaan aritmeettiset funktioiden 𝑓(𝑛)=𝑛ja𝑔(𝑛) =𝑛2 Dirichlet’n tulo, kun𝑛=4. Saadaan
(𝑓 ∗𝑔) (4) =∑︁
𝑑|4
𝑓(𝑑)𝑔 (︂4
𝑑 )︂
=𝑓(1)𝑔(4) + 𝑓(2)𝑔(2) + 𝑓(4)𝑔(1)
=1·16+2·4+4·1
=28.
Lause 2.1. Dirichlet’n tulo on vaihdannainen ja liitännäinen. Toisin sanoen 𝑓 ∗𝑔 =𝑔∗ 𝑓 ja (𝑓 ∗𝑔) ∗ℎ = 𝑓 ∗ (𝑔∗ℎ)
kaikille aritmeettisille funktioille 𝑓 , 𝑔jaℎ.
Todistus. (Ks. [1, s. 108]). Todistetaan ensin vaihdannaisuus. Olkoot 𝑓 ja𝑔aritmeet- tisia funktiota ja𝑛positiivinen kokonaisluku. Silloin
(𝑓 ∗𝑔) (𝑛) =∑︁
𝑑|𝑛
𝑓(𝑑)𝑔 (︂𝑛
𝑑 )︂
=∑︁
𝑐|𝑛
𝑓 (︂𝑛
𝑐 )︂
𝑔(𝑐) =∑︁
𝑐|𝑛
𝑔(𝑐)𝑓 (︂𝑛
𝑐 )︂
= (𝑔∗ 𝑓) (𝑛),
sillä summassa luku𝑑 = 𝑛
𝑐 käy läpi kaikki luvun𝑛tekijät siten, että𝑛=𝑑𝑐, samoin luku𝑐= 𝑛𝑑. Siis 𝑓 ∗𝑔=𝑔∗ 𝑓, mikä osoittaa vaihdannaisuuden.
Osoitetaan seuraavaksi liitännäisyys. Olkoot 𝑓, 𝑔 ja ℎ aritmeettisia funktiota.
Tällöin huomataan, että
(︁(𝑓 ∗𝑔) ∗ℎ)︁
(𝑛) = ∑︁
𝑑𝑐=𝑛
(𝑓 ∗𝑔) (𝑑)ℎ(𝑐)
= ∑︁
𝑑𝑐=𝑛
(︂ ∑︁
𝑎 𝑏=𝑑
𝑓(𝑎)𝑔(𝑏))︂
ℎ(𝑐)
= ∑︁
𝑎 𝑏 𝑐=𝑛
𝑓(𝑎)𝑔(𝑏)ℎ(𝑐)
ja
(︁𝑓 ∗ (𝑔∗ℎ))︁
(𝑛) = ∑︁
𝑎 𝑑=𝑛
𝑓(𝑎) (𝑔∗ℎ) (𝑑)
= ∑︁
𝑎 𝑑=𝑛
𝑓(𝑎)(︂ ∑︁
𝑏 𝑐=𝑑
𝑔(𝑏)ℎ(𝑐))︂
= ∑︁
𝑎 𝑏 𝑐=𝑛
𝑓(𝑎)𝑔(𝑏)ℎ(𝑐).
Siis(𝑓 ∗𝑔) ∗ℎ= 𝑓 ∗ (𝑔∗ℎ)eli Dirichlet’n tulo on liitännäinen. □ Lause 2.2. Määritellään aritmeettinen funktio 𝜀 siten, että 𝜀(1) = 1 ja 𝜀(𝑛) = 0, kun𝑛 >1. Tällöin kaikille aritmeettisille funktioille 𝑓 on voimassa
𝑓 ∗𝜀=𝜀∗ 𝑓 = 𝑓 eli funktio𝜀on neutraalialkio Dirichlet’n tulon suhteen.
Todistus. (Ks. [8, s. 164]). Olkoon 𝑓 aritmeettinen funktio. Saadaan (𝑓 ∗𝜀) (𝑛) =∑︁
𝑑|𝑛
𝑓(𝑑)𝜀 (︂𝑛
𝑑 )︂
= 𝑓(𝑛)𝜀(1) = 𝑓(𝑛)1= 𝑓(𝑛), sillä𝜀(︁𝑛
𝑑
)︁ =0, kun𝑑 < 𝑛. □
Lause 2.3. Olkoon 𝑓 aritmeettinen funktio. Jos 𝑓(1) ≠ 0, niin on olemassa yksikä- sitteinen aritmeettinen funktio𝑔siten, että 𝑓 ∗𝑔=𝜀. Funktiota𝑔sanotaan funktion
𝑓 käänteisfunktioksi Dirichlet’n tulon suhteen ja sitä merkitään symbolilla 𝑓−1. Todistus. (Ks. [1, s. 109]). Todistetaan induktiolla, että yhtälöllä (𝑓 ∗𝑔) (𝑛) =𝜀(𝑛) on yksikäsitteinen ratkaisu𝑔(1), 𝑔(2), . . . , 𝑔(𝑛) kaikilla𝑛∈ℤ+.
1. Perusaskel. Osoitetaan, että väite on tosi, kun𝑛=1.
Saadaan(𝑓 ∗𝑔) (1) = 𝑓(1)𝑔(1)=1 ja𝑔(1) = 1
𝑓(1), sillä 𝑓(1) ≠ 0.
2. Induktioaskel. Olkoon𝑛 >1 ja oletetaan, että funktion𝑔arvot𝑔(1), . . . , 𝑔(𝑛− 1) ovat yksikäsitteisesti määriteltyjä siten, että
(𝑓 ∗𝑔) (𝑛) =𝜀(𝑛)kaikilla𝑛=1,2, . . . , 𝑛−1. Tällöin
(𝑓 ∗𝑔) (𝑛)= 𝑓(1)𝑔(𝑛) +∑︁
𝑑|𝑛 𝑑 >1
𝑓(𝑑)𝑔 (︂𝑛
𝑑 )︂
=0
ja edelleen
𝑔(𝑛) =− 1 𝑓(1)
∑︁
𝑑|𝑛 𝑑 >1
𝑓(𝑑)𝑔 (︂𝑛
𝑑 )︂
, 𝑓(1) ≠ 0.
Siis funktion𝑔arvo luvulla𝑛on yksikäsitteisesti määritelty.
3. Johtopäätös. Väite on tosi induktioperiaatteen nojalla ja lause on näin ollen todis-
tettu. □
2.3 Multiplikatiiviset funktiot
Määritellään seuraavaksi multiplikatiivinen funktio ja todistetaan multiplikatiivisten funktioiden perusominaisuuksia. Lisäksi tässä alaluvussa osoitetaan, että Dirichlet’n tulo säilyttää multiplikatiivisuuden sekä Möbiuksen ja Eulerin funktiot ovat multipli- katiivisia.
1900-luvun alkupuolella multiplikatiivisia funktioita ovat erityisesti tutkineet matemaatikot Eric Temple Bell ja Ramaswamy Vaidyanathaswamy. Bell kirjoitti vuonna 1915 ensimmäisen merkittävän teoksen aritmeettisista funktioista. Washing- tonin yliopiston julkaisemassa teoksessa An arithmetical theory of certain numerical functionBell esitti aritmeettisten funktioiden perustuloksia. Vuonna 1927 Vaidyanat- haswamy julkaisi tutkimuksenOn the inversion of multiplicative arithmetic functions lehdessä Journal of the Indian Mathematical Society. Kirjoituksessaan hän osoit- ti, että multiplikatiivisen funktion käänteisfunktio on multiplikatiivinen. Vaidyanat- haswamy kirjoitti vuonna 1931 laajemman tutkimuksenThe theory of multiplicative arithmetic functions, jossa hänen tuloksensa vastasivat läheisesti Bellin ideoita. [14, s. 579–580]
Määritelmä 2.3. (Vrt. [9, s. 18]). Aritmeettista funktiota 𝑓 sanotaanmultiplikatiivi- seksi, jos funktio 𝑓 ei ole nollafunktio ja 𝑓(𝑚 𝑛) = 𝑓(𝑚)𝑓(𝑛) aina, kun(𝑚, 𝑛) =1.
Huomautus. Merkinnällä(𝑚, 𝑛)tarkoitetaan lukujen𝑚ja𝑛suurinta yhteistä tekijää eli lukua syt(𝑚, 𝑛).
Huomautus. (Ks. [1, s. 105]). Jos aritmeettinen funktio 𝑓 on multiplikatiivinen, niin 𝑓(1)=1. Nimittäin jos 𝑓(𝑎) ≠0 (𝑎 ∈ℤ+), niin
𝑓(𝑎) = 𝑓(𝑎·1)= 𝑓(𝑎)𝑓(1), joten 𝑓(1) =1.
Seuraavasta esimerkistä kuitenkin huomataan, että käänteinen implikaatio ei ole voimassa.
Esimerkki 2.2. ([9, s. 20], tehtävä 7-3.) Funktio 𝑓(𝑚)=2𝑚−1 ei ole multiplikatii- vinen, vaikka 𝑓(1) =1, sillä esimerkiksi 𝑓(6) =11≠ 𝑓(2)𝑓(3) =15.
Lause 2.4. Jos funktiot 𝑓 ja𝑔ovat multiplikatiivisia, niin Dirichlet’n tulo 𝑓 ∗𝑔on multiplikatiivinen.
Todistus. (Ks. [1, s. 109]). Oletetaan, että funktiot 𝑓 ja 𝑔 ovat multiplikatiivisia.
Olkoonℎ= 𝑓 ∗𝑔, ja oletetaan, että (𝑚, 𝑛) =1. Osoitetaan, että silloin ℎ(𝑚 𝑛) = ∑︁
𝑑|𝑚 𝑛
𝑓(𝑑)𝑔 (︂𝑚 𝑛
𝑑 )︂
=ℎ(𝑚)ℎ(𝑛).
Nyt 𝑑|𝑚 𝑛 ja (𝑚, 𝑛) = 1, joten luku 𝑑 voidaan yksikäsitteisesti jakaa tekijöihinsä siten, että𝑑 =𝑎 𝑏, missä𝑎|𝑚ja𝑏|𝑛. Tällöin(𝑎, 𝑏) =1 ja (︁𝑚
𝑎, 𝑛
𝑏
)︁ =1. Täten ℎ(𝑚 𝑛) =∑︁
𝑑|𝑚 𝑛
𝑓(𝑑)𝑔 (︂𝑚 𝑛
𝑑 )︂
=∑︁
𝑎|𝑚
∑︁
𝑏|𝑛
𝑓(𝑎 𝑏)𝑔 (︂𝑚 𝑛
𝑎 𝑏 )︂
=∑︁
𝑎|𝑚
∑︁
𝑏|𝑛
𝑓(𝑎)𝑓(𝑏)𝑔 (︂𝑚
𝑎 )︂
𝑔 (︂𝑛
𝑏 )︂
= (︄
∑︁
𝑎|𝑚
𝑓(𝑎)𝑔 (︂𝑚
𝑎 )︂
)︄ (︄
∑︁
𝑏|𝑛
𝑓(𝑏)𝑔 (︂𝑛
𝑏 )︂
)︄
=ℎ(𝑚)ℎ(𝑛).
Näin ollen Dirichlet’n tulo 𝑓 ∗𝑔on multiplikatiivinen. □ Seuraus 2.1. Jos funktio 𝑓 on multiplikatiivinen ja
𝑔(𝑛) =∑︁
𝑑|𝑛
𝑓(𝑑),
niin funktio𝑔on multiplikatiivinen.
Todistus. (Ks. [1, s. 106]). Todistus suoritetaan vastaavalla tavalla kuin lauseen 2.4
todistus. □
Huomautus. Funktio𝑔on funktion 𝑓 tekijäsummafunktio.
Esimerkki 2.3. Olkoot 𝑓 ja𝑔multiplikatiivisia funktioita jaℎ = 𝑓 ∗𝑔. Tällöin ℎ(10) =(𝑓 ∗𝑔) (10)
=𝑓(1)𝑔(10) + 𝑓(2)𝑔(5) + 𝑓(5)𝑔(2) + 𝑓(10)𝑔(1)
=1·𝑔(10) + 𝑓(2)𝑔(5) + 𝑓(5)𝑔(2) + 𝑓(10) ·1
=𝑔(2)𝑔(5) + 𝑓(2)𝑔(5) + 𝑓(5)𝑔(2) + 𝑓(2)𝑓(5)
=(︁
𝑔(2) + 𝑓(2))︁
𝑔(5) +(︁
𝑔(2) + 𝑓(2))︁
𝑓(5)
=(︁
𝑔(2) + 𝑓(2))︁ (︁
𝑔(5) + 𝑓(5))︁
=(1·𝑔(2) + 𝑓(2) ·1) (1·𝑔(5) + 𝑓(5) ·1)
=(︁
𝑓(1)𝑔(2) + 𝑓(2)𝑔(1))︁ (︁
𝑓(1)𝑔(5) + 𝑓(5)𝑔(1))︁
=ℎ(2)ℎ(5).
Lause 2.5. Jos funktiot𝑔ja 𝑓 ∗𝑔on multiplikatiivisia, niin funktio 𝑓 on multiplika- tiivinen.
Todistus. (Ks. [1, s. 110]). Olkoot funktiot𝑔ja 𝑓 ∗𝑔multiplikatiivisia. Tehdään vas- taoletus, että funktio 𝑓 ei ole multiplikatiivinen. Olkoonℎ = 𝑓 ∗𝑔. Vastaoletuksen nojalla funktio 𝑓 ei ole multiplikatiivinen, joten on olemassa positiiviset kokonais- luvut𝑚 ja𝑛siten, että (𝑚, 𝑛) =1, mutta 𝑓(𝑚 𝑛) ≠ 𝑓(𝑚)𝑓(𝑛). Valitaan luvut𝑚ja𝑛 siten, että niiden tulo𝑚 𝑛on mahdollisimman pieni.
Jos tulo 𝑚 𝑛 = 1, niin tällöin 𝑓(1) ≠ 𝑓(1)𝑓(1) eli 𝑓(1) ≠ 1. Siis ℎ(1) = 𝑓(1)𝑔(1)= 𝑓(1) ≠1 eli funktioℎei ole multiplikatiivinen ja päädytään ristiriitaan.
Jos tulo 𝑚 𝑛 > 1, saadaan 𝑓(𝑎 𝑏) = 𝑓(𝑎)𝑓(𝑏) kaikilla 𝑎 𝑏 < 𝑚 𝑛 ja (𝑎, 𝑏) = 1.
Edelleen
ℎ(𝑚 𝑛) = ∑︁
𝑎|𝑚 𝑏|𝑛 𝑎 𝑏 <𝑚 𝑛
𝑓(𝑎 𝑏)𝑔 (︂𝑚 𝑛
𝑎 𝑏 )︂
+ 𝑓(𝑚 𝑛)𝑔(1)
= ∑︁
𝑎|𝑚 𝑏|𝑛 𝑎 𝑏 <𝑚 𝑛
𝑓(𝑎)𝑓(𝑏)𝑔 (︂𝑚
𝑎 )︂
𝑔 (︂𝑛
𝑏 )︂
+ 𝑓(𝑚 𝑛)
=ℎ(𝑚)ℎ(𝑛) − 𝑓(𝑚)𝑓(𝑛) + 𝑓(𝑚 𝑛).
Koska 𝑓(𝑚 𝑛) ≠ 𝑓(𝑚)𝑓(𝑛), niinℎ(𝑚 𝑛) ≠ ℎ(𝑚)ℎ(𝑛). Siis funktio ℎei ole multipli- katiivinen ja päädytään ristiriitaan. Siis funktio 𝑓 on multiplikatiivinen. □ Lause 2.6. ([9, s. 20], tehtävä 7-1.)Funktio𝜀on multiplikatiivinen.
Todistus. Olkoon funktio 𝑓 multiplikatiivinen funktio. (Multiplikatiivisia funktioita on olemassa: esimerkiksi funktio, joka on identtisesti 1.) Nyt lauseen 2.2 mukaan 𝑓∗ 𝜀=𝜀∗ 𝑓 = 𝑓. Näin ollen lauseen 2.5 nojalla funktio𝜀on multiplikatiivinen. □ Lause 2.7. Jos funktio 𝑓 on multiplikatiivinen, niin käänteisfunktio 𝑓−1on multipli- katiivinen.
Todistus. (Ks. [1, s. 110]). Tämä seuraa suoraan lauseesta 2.5, sillä 𝜀 = 𝑓 ∗ 𝑓−1 =
𝑓−1∗ 𝑓, missä funktio𝜀on multiplikatiivinen. □
2.4 August Ferdinand Möbius
August Ferdinand Möbius (1790–1868) oli saksalainen matemaatikko ja tähtitietei- lijä, joka erityisesti tunnetaan analyyttisen geometrian ja topologian tutkimuksis- taan [15]. Möbius aloitti oikeustieteen opinnot Leipzigin yliopistossa vuonna 1809, mutta ensimmäisen opintovuoden jälkeen hän siirtyi opiskelemaan matematiikkaa, tähtitiedettä ja fysiikkaa. Vuonna 1813 hän matkusti jatko-opintoihin Göttingenin yliopistoon, jossa häntä opetti Carl Gauss antaen vankan taustan matematiikasta ja tähtitieteestä. Möbius kirjoitti väitöskirjansa tähtitieteen alalta vuonna 1815 ja sai tähtitieteen professorin viran Leipzigin yliopistosta vuonna 1816. [11, s. 186]
Möbiuksen matemaattiset julkaisut koskivat pääosin geometriaa. Hän käytti muun muassa homogeenisia koordinaatteja ja projektiivisia muunnoksia projektiivi- sessa geometriassa. Lisäksi hän käsitteli geometrisesti statiikkaa eli tasapaino-oppia mekaniikan alalta, joka tutkii esimerkiksi rakennuksiin ja siltoihin vaikuttavia voi- mia. [15]
Möbius oli edelläkävijä topologiassa. Hänen mukaansa on nimetty Möbiuksen nauha, joka saadaan aikaan kiertämällä nauhan toista päätä puoli kierrosta ennen nauhan päiden yhteen kiinnitystä. Tämän topologisen pinnan Möbius keksi vuonna 1858. [15]
2.5 Möbiuksen funktio
Möbiuksen mukaan on myös nimetty lukuteorian käsite Möbiuksen funktio, joka määritellään seuraavaksi. Lisäksi osoitetaan, että Möbiuksen funktio on multiplika- tiivinen ja todistetaan Möbiuksen käänteiskaava.
Määritelmä 2.4. (Vrt. [1, s. 105]). Möbiuksen funktio 𝜇 on aritmeettinen funktio, joka määritellään seuraavasti:
𝜇(𝑛) =
⎧⎪
⎪⎪
⎪⎪
⎪
⎨
⎪⎪
⎪⎪
⎪⎪
⎩
1, jos𝑛 =1,
(−1)𝑘, jos𝑛 =𝑝1· 𝑝2· · ·𝑝𝑘 missä𝑝1, 𝑝2, . . . , 𝑝𝑘 ovat erisuuria alkuluja, 0, jos 𝑝2|𝑛jollakin alkuluvulla 𝑝 .
Esimerkki 2.4. Lasketaan Möbiuksen funktion arvot luvuille 26, 28 ja 30.
Jakamalla luvut alkulukutekijöihin saadaan 𝜇(26) =𝜇(2·13) =(−1)2=1,
𝜇(28) =𝜇(22·7) =0 ja
𝜇(30) =𝜇(2·3·5)= (−1)3=−1.
Lause 2.8. Möbiuksen funktio 𝜇on multiplikatiivinen.
Todistus. (Ks. [1, s. 106]). Olkoot 𝑚 ja 𝑛 positiivisia kokonaislukuja siten, et- tä (𝑚, 𝑛) = 1. Jos 𝑝2|𝑚 tai 𝑝2|𝑛 jollakin alkuluvulla 𝑝, niin 𝑝2|𝑚 𝑛 ja edelleen 𝜇(𝑚) = 𝜇(𝑚 𝑛) = 0= 𝜇(𝑚)𝜇(𝑛). Jos𝑚 = 𝑝1· 𝑝2· · ·𝑝𝑘 ja𝑛 =𝑞1· 𝑞2· · ·𝑞ℎ, missä 𝑝1, 𝑝2, . . . , 𝑝𝑘ja𝑞1, 𝑞2, . . . , 𝑞ℎovat erisuuria alkulukuja, niin𝜇(𝑚) =(−1)𝑘, 𝜇(𝑛) = (−1)ℎja𝑚 𝑛= 𝑝1·𝑝2· · ·𝑝𝑘·𝑞1·𝑞2· · ·𝑞ℎ. Edelleen𝜇(𝑚 𝑛) =(−1)𝑘+ℎ =(−1)𝑘(−1)ℎ= 𝜇(𝑚)𝜇(𝑛). Näin todistettiin, että Möbiuksen funktio𝜇on multiplikatiivinen. □ Lause 2.9. Möbiuksen funktion tekijäsummafunktio on
∑︁
𝑑|𝑛
𝜇(𝑑) =
⎧⎪
⎪
⎨
⎪⎪
⎩
1, jos𝑛=1, 0, jos𝑛 > 1,
𝑛 ∈ℤ+.
Todistus. (Vrt. [13, s. 272]). Merkitään 𝑀(𝑛) = ∑︁
𝑑|𝑛𝜇(𝑑). Oletetaan ensin, että 𝑛=1. Silloin
𝑀(1)=∑︁
𝑑|1
𝜇(𝑑)= 𝜇(1)=1.
Oletetaan sitten, että𝑛 >1. Lauseen 2.8 nojalla Möbiuksen funktio𝜇on multipli- katiivinen. Edelleen seurauksen 2.1 nojalla Möbiuksen funktion tekijäsummafunktio 𝑀(𝑛)on multiplikatiivinen. Oletetaan, että𝑛= 𝑝𝑘, missä𝑝on alkuluku ja𝑘 on po- sitiivinen kokonaisluku. Huomataan, että jos 𝑘 = 1, niin 𝜇(𝑝) = −1, ja jos 𝑘 ≥ 2, niin𝜇(𝑝𝑘) =0. Siis
𝑀(𝑝𝑘)= ∑︁
𝑑|𝑝𝑘
𝜇(𝑑) =𝜇(1) +𝜇(𝑝) +𝜇(𝑝2) + · · · +𝜇(𝑝𝑘)
=1+ (−1) +0+ · · · +0=0.
Lopuksi oletetaan, että𝑛on positiivinen kokonaisluku, jonkakanoninen alkute- kijähajotelmaon 𝑛 = 𝑝𝛼1
1 𝑝𝛼2
2 · · ·𝑝𝛼𝑘
𝑘 , missä 𝑝1, 𝑝2, . . . , 𝑝𝑘 ovat erisuuria alkuluja, 𝛼1, 𝛼2, . . . , 𝛼𝑘 ovat positiivisia kokonaislukuja ja 𝑝1 < 𝑝2 < · · · < 𝑝𝑘. Edelleen tekijäsummafunktio 𝑀(𝑛)on multiplikatiivinen, joten
𝑀(𝑛) =𝑀(𝑝𝛼1
1 )𝑀(𝑝𝛼2
2 ) · · ·𝑀(𝑝𝛼𝑘
𝑘 ) =0·0· · ·0=0.
Näin ollen lause on todistettu. □
Määritelmä 2.5. (Vrt. [2, s. 31]). Määritelläänyksikköfunktio𝑢siten, että𝑢(𝑛) =1 aina, kun𝑛 ∈ℤ+.
Huomautus. (Vrt. [2, s. 31]). Lauseen 2.9 nojalla ∑︁
𝑑|𝑛𝜇(𝑑) = 𝜀(𝑛). Siis 𝜇∗ 𝑢 = 𝑢∗𝜇 =𝜀, missä𝑢ja𝜇ovat toistensa käänteisfunktioita Dirichlet’n tulon suhteen.
Huomautus. Yksikköfunktio𝑢on multiplikatiivinen.
Lause 2.10 (Möbiuksen käänteiskaava). Olkoot 𝑓 ja 𝑔 aritmeettisia funktioita, ja olkoon𝑛 ∈ℤ+. Tällöin
𝑔(𝑛) =∑︁
𝑑|𝑛
𝑓(𝑑) ⇔ 𝑓(𝑛) =∑︁
𝑑|𝑛
𝑔(𝑑)𝜇 (︂𝑛
𝑑 )︂
.
Todistus. (Ks. [2, s. 32]). Yhtälö𝑔(𝑛) =∑︁
𝑑|𝑛 𝑓(𝑑)voidaan kirjoittaa muodossa𝑔 = 𝑓 ∗𝑢, missä𝑢on yksikköfunktio. Kertomalla yhtälö𝑔= 𝑓 ∗𝑢Möbiuksen funktiolla 𝜇puolittain saadaan, että 𝑔∗ 𝜇 = (𝑓 ∗𝑢) ∗ 𝜇. Dirichlet’n tulon liitännäisyyden ja edellisen huomautuksen nojalla(𝑓 ∗𝑢) ∗𝜇= 𝑓 ∗ (𝑢∗𝜇) = 𝑓 ∗𝜀= 𝑓 .Siis 𝑓 =𝑔∗𝜇.
Todistus suoritetaan toiseen suuntaan vastaavalla tavalla kertomalla yhtälöä 𝑓 =𝑔∗𝜇
yksikköfunktiolla𝑢. □
Seuraus 2.2. Jos funktio𝑔on multiplikatiivinen ja 𝑔(𝑛) =∑︁
𝑑|𝑛
𝑓(𝑑),
niin funktio 𝑓 on multiplikatiivinen.
Todistus. (Ks. [9, s. 22]). Olkoon funktio𝑔multiplikatiivinen. Kirjoitetaan𝑔 = 𝑓 ∗𝑢 ja kerrotaan yhtälö puolittain Möbiuksen funktiolla 𝜇saaden𝑔∗𝜇 = (𝑓 ∗𝑢) ∗𝜇 = 𝑓 ∗ (𝑢∗ 𝜇) = 𝑓 ∗𝜀 = 𝑓. Nyt 𝑔ja 𝜇ovat multiplikatiivisia, joten niiden Dirichlet’n
tulo 𝑓 on multiplikatiivinen. □
Huomautus. Seuraus 2.2 on seurauksen 2.1 tietynlainen käänteistulos.
2.6 Leonhard Euler
Sveitsiläinen Leonhard Euler (1707–1783) oli yksi kaikkien aikojen suurimmista ja tuotteliaimmista matemaatikoista. Elinaikanaan Euler julkaisi yli 500 kirjaa ja artikkelia sekä tuotti noin 800 sivua matemaattista tekstiä vuodessa. [5, s. 618, 620]
Laplacea lainaten: ”Read Euler, read Euler, he is the master of us all” [6, s. 31].
Hän on myös merkittävästi myötävaikuttanut fysiikan alalla, erityisesti optiikassa, mekaniikassa, sähkössä ja magnetismissa [1, s. 118].
Euler oli papin poika ja isänsä toiveen mukaan Euler aloitti 13-vuotiaana opis- kelunsa Baselin yliopistossa tähdätäkseen teologian uralle [13, s. 235]. Yliopiston matematiikan professori Johann Bernoulli kuitenkin huomasi Eulerin poikkeuksel- liset taidot matematiikassa ja fysiikassa. Näin ollen Eulerilla oli mahdollisuus saada lauantaisin yksityisopetusta Bernoullilta. Euler myös ystävystyi Johann Bernoullin kahden pojan Danielin ja Nicolauksen kanssa. Maisteritutkielmansa Euler kirjoitti vuonna 1724, missä hän vertasi René Descartesin ja Isaac Newtonin filosofisia aja- tuksia. [6, s. 32–33] Eulerin kiinnostus matematiikkaa kohtaa sai hänet luopumaan suunnitelmistaan seurata isänsä jalanjälkiä [13, s. 235].
Vuonna 1727 Euler kutsuttiin Venäjälle lääketieteen ja fysiologian osaston jä- seneksi Pietarin tiedeakatemiaan, jonka Katariina I oli perustanut. Euler oli saanut suositukset Daniel ja Nicolaus Bernoullilta, jotka toimivat Pietarin akatemian ma- tematiikan tutkijoina. Myöhemmin vuonna 1733 Eulerista tuli Pietarin akatemian johtava matemaatikko ja akatemian aikakauskirjassa hän julkaisi runsaasti mate- maattista tuotantoaan. Eulerin oikea silmä sokeutui vuonna 1735, mutta se ei Eulerin työtä hidastanut. Vuonna 1741 Euler vastasi myöntävästi Fredrik Suuren kutsuun saapua Berliinin akatemiaan. Euler asui Berliinissä 25 vuotta, mutta sai tältä ajalta palkkaa myös Pietarista, sillä hän levitti tutkimuksiaan sekä Berliinin että Pieta- rin akatemioiden julkaisuissa. Vuonna 1766 Euler palasi takaisin Venäjälle Pietarin akatemiaan Katariina Suuren hyväksynnällä, mutta alkoi sokeutumaan toisestakin silmästä samaisena vuotena. Tämäkään takaisku ei estänyt Euleria julkaisemasta tutkimuksiaan, vaan hän jatkoi töitään lastensa avustamana. Esimerkiksi suosittu al- gebran oppikirja Elements of Algebrajulkaistiin vuonna 1770, jonka tekstin sokea Euler oli sanellut kotiapulaiselle. Eulerin kuoltua Pietarin akatemia jatkoi edelleen hänen tutkimuksiensa julkaisuja lähes 50 vuoden ajan. [5, s. 619–621, 644]
Eulerin merkitys matematiikan kehittymisessä on ollut valtava, sillä hän kehitti laaja-alaisesti puhtaan ja soveltuvan matematiikan tuntemusta. Hänen tutkimuksensa
koskivat pääosin nykyistä lukio- ja yliopistotason matematiikkaa sekä olivat kirjoi- tettu suurimmaksi osaksi nykykielellä ja -merkinnöillä. [5, s. 621]
Euler oli keskeinen matemaattisten merkintöjen kehittäjä, erityisesti monet mer- kintätavat geometriassa, algebrassa, trigonometriassa ja analyysissä ovat peräisin Eu- lerilta. Euler alkoi käyttämään kirjoituksissaan kirjainta𝑒 kuvaamaan luonnollisen logaritmin kantalukua. Ensimmäisen kerran kirjain 𝑒 nähtiin painettuna teoksessa Mechanica vuonna 1736, jonka jälkeen merkintä vakiintui nopeasti. Kreikkalais- ta kirjainta 𝜋 William Jones oli jo aikaisemminkin käyttänyt kuvaamaan ympyrän kehän ja halkaisijan suhdetta, mutta vuonna 1737 Euler otti merkinnän käyttöönsä tunnettuihin oppikirjoihinsa ja täten vakiinnutti laajasti kirjaimen𝜋 käytön. Lisäksi imaginääriyksikön merkitseminen kirjaimella𝑖 on peräisin Eulerilta vuodelta 1777, mikä yleistyi Gaussin käyttäessä sitä teoksessaanDisquisitiones Arithmeticaevuon- na 1801. Käytämme edelleenkin monia muitakin Eulerin merkintätapoja, esimerkiksi merkitsemme kolmion sivuja pienillä kirjaimilla𝑎, 𝑏, 𝑐, summaa merkinnällä∑︁
ja muuttujan𝑥funktiota merkinnällä 𝑓(𝑥). [5, s. 621–623]
Eulerin teokset sisälsivät tärkeitä käsitteitä ja teorioita, jotka ovat luoneet pohjaa nykyiselle matematiikan tietämykselle. Esimerkiksi Eulerin vuonna 1748 ilmestynyt latinankielinen teos Introduction in Analysin Infinitorum oli kaksiosainen tutkiel- ma, joka käynnisti matemaattisen analyysin kehityksen. Teoksen myötä funktiosta tuli analyysin peruskäsite. Euler käsitteli teoksessaan alkeisfunktiota, trigonomet- risia funktioita, trigonometristen funktioiden käänteisfunktioita, logaritmifunktioita ja eksponenttifunktioita lähes samalla tavalla kuin nykyäänkin. Hän myös todisti päättymättömiin sarjoihin liittyviä tuloksia, kuten että
∞
∑︁
𝑛=1
1 𝑛2
= 1 12 + 1
22 + 1
32 + · · · = 𝜋2
6 . [5,s. 623–626]
Lukuteoriasta Euler ei julkaissut alan kirjoja, mutta hän kirjoitti lukuteorian oppeihin liittyviä artikkeleita ja kirjeitä. Muun muassa Euler todisti vuonna 1736 Fermat’n pienen lauseen. [5, s. 641–642]
2.7 Eulerin funktio
Tässä alaluvussa tutustutaan Eulerin mukaan nimettyyn aritmeettiseen funktioon.
Määritelmä 2.6. (Vrt. [7, s. 72]).Eulerin funktio𝜑määritellään kaikille positiivisille kokonaisluvuille kaavalla
𝜑(𝑛) =|{𝑚 ∈ℤ+ : 1 ≤ 𝑚 ≤ 𝑛 ja (𝑚, 𝑛) =1}|.
Esimerkki 2.5. Lasketaan Eulerin funktion 𝜑(𝑛) arvot, kun𝑛= 7 ja𝑛 =8. Tällöin 𝜑(7) =6, sillä (𝑚,7) = 1, kun 𝑚 = 1,2,3,4,5,6. Huomataan, että 𝜑(𝑝) = 𝑝−1, kun 𝑝on alkuluku, sillä kaikille 1 ≤ 𝑚 ≤ 𝑝on voimassa(𝑚, 𝑝) =1, jos ja vain jos 𝑚=1,2, . . . , 𝑝−1. Vastaavasti𝜑(8) =4, sillä(𝑚,8) =1, kun𝑚 =1,3,5,7.
Lause 2.11. Jos 𝑝on alkuluku ja𝛼 ∈ℤ+, niin 𝜑(𝑝𝛼) = 𝑝𝛼−𝑝𝛼−1 = 𝑝𝛼
(︂
1− 1 𝑝 )︂
.
Todistus. (Ks. [13, s. 241]). Lasketaan niiden positiivisten kokonaislukujen määrä, jotka ovat pienempiä tai yhtä suuria kuin luku 𝑝𝛼 ja joiden suurin yhteinen tekijä luvun 𝑝𝛼 kanssa on erisuuri kuin yksi. Tällaisia ovat kokonaisluvut 𝑘 𝑝 siten, että 1 ≤ 𝑘 ≤ 𝑝𝛼−1. Nyt selvästi (𝑘 𝑝, 𝑝𝛼) ≠ 1. Huomataan, että kyseisiä lukuja on siis 𝑝𝛼−1kappaletta. Näin ollen luvun 𝑝𝛼kanssa keskenään jaottomia kokonaislukuja on 𝑝𝛼−𝑝𝛼−1kappaletta. Siis𝜑(𝑝𝛼) = 𝑝𝛼− 𝑝𝛼−1 = 𝑝𝛼
(︂
1− 1
𝑝
)︂
. □
Apulause 2.1. Jos𝑎ja𝑏ovat kokonaislukuja siten, että (𝑎, 𝑏) =𝑑, niin (𝑎/𝑑 , 𝑏/𝑑) =1. Toisin sanoen luvut(𝑎/𝑑)ja (𝑏/𝑑)ovat keskenään jaottomia.
Todistus. (Ks. [13, s. 94]). Olkoot 𝑎 ja 𝑏 kokonaislukuja siten, että (𝑎, 𝑏) = 𝑑. Osoitetaan, että luvuilla (𝑎/𝑑) ja (𝑏/𝑑) ei ole muuta yhteistä jakajaa kuin luku 1.
Oletetaan, että 𝑒 on kokonaisluku siten, että 𝑒 | (𝑎/𝑑) ja 𝑒 | (𝑏/𝑑). Tällöin on olemassa kokonaisluvut 𝑘 ja 𝑙 siten, että 𝑎/𝑑 = 𝑘 𝑒 ja 𝑏/𝑑 = 𝑙 𝑒. Toisin sanoen 𝑎 =𝑑𝑒 𝑘 ja𝑏 =𝑑𝑒𝑙. Näin ollen luku𝑑𝑒on lukujen𝑎ja𝑏 yhteinen tekijä. Mutta nyt oletuksen nojalla(𝑎, 𝑏) =𝑑 ja𝑑𝑒 ≤ 𝑑, joten luku𝑒 =1. Siis (𝑎/𝑑 , 𝑏/𝑑) =1. □ Lause 2.12. Kaikille kokonaisluvuille n on voimassa
∑︁
𝑑|𝑛
𝜑(𝑑) =𝑛.
Todistus. (Ks. [1, s. 119]). Olkoon luku 𝑛jaollinen luvuilla 𝑑1, 𝑑2, . . . , 𝑑𝑘 > 0 (ja vain niillä) sekä määritellään joukko
𝑆𝑖={𝑚 ∈ℤ+ : 𝑚 ≤ 𝑛 ja (𝑚, 𝑛) =𝑑𝑖}, 𝑖 =1,2, . . . , 𝑘 . Jos𝑚 ∈ 𝑆𝑖, niin𝑚 =𝑑𝑖𝑚′jollakin kokonaisluvulla𝑚′, missä(𝑚′, 𝑛
𝑑𝑖) = (𝑚
𝑑𝑖, 𝑛
𝑑𝑖) =1 apulauseen 2.1 nojalla. Koska 0 ≤ 𝑚′ ≤ 𝑛
𝑑𝑖, niin määritelmän 2.6 nojalla joukon𝑆𝑖 alkioiden lukumäärä|𝑆𝑖|= 𝜑
(︂
𝑛 𝑑𝑖
)︂
. Nyt joukot𝑆1, 𝑆2, . . . , 𝑆𝑘ovat joukon{1,2, . . . , 𝑛} ositus, jolloin
𝑘
∑︁
𝑖=1
𝜑 (︂𝑛
𝑑𝑖 )︂
=
𝑘
∑︁
𝑖=1
|𝑆𝑖|=𝑛.
Nyt oletuksen mukaan luku𝑛on jaollinen luvuilla𝑑1, 𝑑2, . . . , 𝑑𝑘, joten {︂ 𝑛
𝑑1 ,
𝑛 𝑑2
, . . . , 𝑛 𝑑𝑘
}︂
= {𝑑1, 𝑑2, . . . , 𝑑𝑘}. Näin ollen∑︁
𝑑|𝑛𝜑(𝑑) =𝑛. □
Apulause 2.2. Funktio𝑔(𝑛) =𝑛 (𝑛∈ℤ+)on multiplikatiivinen.
Todistus. Kaikille positiivisille kokonaisluvuille 𝑚 ja 𝑛 pätee, että 𝑔(𝑚 𝑛) = 𝑚 𝑛 = 𝑔(𝑚)𝑔(𝑛), joten funktio𝑔(𝑛) =𝑛on multiplikatiivinen. □ Lause 2.13. Eulerin funktio𝜑on multiplikatiivinen.
Todistus. (Ks. [1, s. 119]). Lauseen 2.12 mukaan 𝑛 = ∑︁
𝑑|𝑛𝜑(𝑑). Koska apu- lauseen 2.2 nojalla funktio 𝑔(𝑛) = 𝑛 on multiplikatiivinen, niin seurauksen 2.2
nojalla𝜑 on multiplikatiivinen. □
Lause 2.14. Olkoon kokonaisluvun 𝑛 > 1 kanoninen alkutekijähajotelma 𝑛 = 𝑝
𝛼1 1 𝑝
𝛼2 2 · · ·𝑝
𝛼𝑘
𝑘 , missä 𝑝1, 𝑝2, . . . , 𝑝𝑘 ovat erisuuria alkuluja, 𝛼1, 𝛼2, . . . , 𝛼𝑘 ovat positiivisia kokonaislukuja ja 𝑝1 < 𝑝2 <· · · < 𝑝𝑘. Tällöin
𝜑(𝑛) =𝑛 (︂
1− 1 𝑝1
)︂ (︂
1− 1 𝑝2
)︂
· · ·(︂
1− 1 𝑝𝑘
)︂
=𝑛
𝑘
∏︂
𝑖=1
(︂
1− 1 𝑝𝑖
)︂
.
Todistus. (Ks. [1, s. 119]). Eulerin funktion𝜑multiplikatiivisuudesta seuraa, että 𝜑(𝑛) =𝜑(𝑝
𝛼1 1 𝑝
𝛼2 2 · · ·𝑝
𝛼𝑘
𝑘 ) =𝜑(𝑝
𝛼1 1 )𝜑(𝑝
𝛼2
2 ) · · ·𝜑(𝑝
𝛼𝑘 𝑘 ). Nyt lauseen 2.11 nojalla𝜑(𝑝𝛼) = 𝑝𝛼
(︂
1− 1
𝑝
)︂
. Siis 𝜑(𝑛) =𝜑(𝑝𝛼1
1 )𝜑(𝑝𝛼2
2 ) · · ·𝜑(𝑝𝛼𝑘
𝑘 )
=𝑝𝛼1
1
(︂
1− 1 𝑝1
)︂
𝑝𝛼2
2
(︂
1− 1 𝑝2
)︂
· · ·𝑝𝛼𝑘
𝑘
(︂
1− 1 𝑝𝑘
)︂
=𝑝𝛼1
1 𝑝𝛼2
2 · · ·𝑝𝛼𝑘
𝑘
(︂
1− 1 𝑝1
)︂ (︂
1− 1 𝑝2
)︂
· · ·(︂
1− 1 𝑝𝑘
)︂
=𝑛 (︂
1− 1 𝑝1
)︂ (︂
1− 1 𝑝2
)︂
· · · (︂
1− 1 𝑝𝑘
)︂
=𝑛
𝑘
∏︂
𝑖=1
(︂
1− 1 𝑝𝑖 )︂
.
□ Esimerkki 2.6. Lasketaan Eulerin funktion 𝜑(𝑛) arvo, kun 𝑛 = 360. Nyt lausetta 2.14 soveltamalla ja jakamalla luku 360 alkulukutekijöihin saadaan
𝜑(360) =𝜑(23·32·5) =360 (︂
1− 1 2
)︂ (︂
1− 1 3
)︂ (︂
1− 1 5 )︂
=96.
2.8 Täydellisesti multiplikatiiviset funktiot
Esitetään täydellisesti multiplikatiivisten funktioiden määritelmä ja todistetaan vält- tämättömiä ja riittäviä ehtoja sille, että funktio on täydellisesti multiplikatiivinen.
Määritelmä 2.7. (Vrt. [2, s. 33]). Aritmeettista funktiota 𝑓 sanotaan täydellisesti multiplikatiiviseksi, jos funktio 𝑓 ei ole nollafunktio ja 𝑓(𝑚 𝑛) = 𝑓(𝑚)𝑓(𝑛) aina, kun𝑚, 𝑛 ∈ℤ+.
Huomautus. Täydellisesti multiplikatiivinen funktio on aina multiplikatiivinen.
Esimerkki 2.7. Lauseissa 2.8 ja 2.13 osoitettiin, että Möbiuksen ja Eulerin funktiot ovat multiplikatiivisia, mutta kyseiset funktiot eivät ole täydellisesti multiplikatii- visia. Nimittäin esimerkiksi 𝜇(9) = 0, mutta 𝜇(3)𝜇(3) = −1· (−1) = 1. Lisäksi 𝜑(9) =6, mutta𝜑(3)𝜑(3) =2·2=4.
Lause 2.15. (Ks. [2, s. 34]). Olkoon 𝑓 multiplikatiivinen funktio. Tällöin funktio 𝑓 on täydellisesti multiplikatiivinen, jos ja vain jos
𝑓(𝑝𝑎) = 𝑓(𝑝)𝑎
aina, kun𝑝on alkuluku ja𝑎on positiivinen kokonaisluku.
Todistus. Oletetaan, että 𝑓 on täydellisesti multiplikatiivinen funktio. Olkoon 𝑝al- kuluku ja𝑎positiivinen kokonaisluku. Tällöin
𝑓(𝑝𝑎) = 𝑓 (𝑝· 𝑝· · ·𝑝)
⏞ˉˉˉˉˉˉˉˉ⏟⏟ˉˉˉˉˉˉˉˉ⏞
𝑎kappaletta
= 𝑓(𝑝)𝑓(𝑝) · · · 𝑓(𝑝)
⏞ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ⏟⏟ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ⏞
𝑎kappaletta
= 𝑓(𝑝)𝑎.
Oletetaan seuraavaksi, että 𝑓(𝑝𝑎) = 𝑓(𝑝)𝑎 jokaisella alkuluvulla 𝑝 ja jokaisella positiivisella eksponentilla 𝑎. Olkoot 𝑚 ja 𝑛 positiivisia kokonaislukuja, ja olkoot niiden alkutekijähajotelmat muotoa 𝑚 = 𝑝𝑎1
1 · 𝑝𝑎2
2 · · ·𝑝𝑎𝑘
𝑘 ja 𝑛 = 𝑝𝑏1
1 · 𝑝𝑏2
2 · · ·𝑝𝑏𝑘
𝑘 , missä𝑎1, 𝑎2, . . . , 𝑎𝑘 ja𝑏1, 𝑏2, . . . , 𝑏𝑘 ovat ei-negatiivisia kokonaislukuja. Silloin
𝑓(𝑚 𝑛) =𝑓(𝑝
𝑎1 1 · 𝑝
𝑎2 2 · · ·𝑝
𝑎𝑘 𝑘 · 𝑝
𝑏1 1 · 𝑝
𝑏2 2 · · ·𝑝
𝑏𝑘 𝑘 )
=𝑓(𝑝𝑎1+𝑏1
1 · 𝑝𝑎2+𝑏2
2 · · ·𝑝𝑎𝑘+𝑏𝑘
𝑘 ). Nyt funktio 𝑓 on multiplikatiivinen, joten
𝑓(𝑝
𝑎1+𝑏1
1 · 𝑝
𝑎2+𝑏2 2 · · ·𝑝
𝑎𝑘+𝑏𝑘
𝑘 ) = 𝑓(𝑝
𝑎1+𝑏1 1 )𝑓(𝑝
𝑎2+𝑏2
2 ) · · · 𝑓(𝑝
𝑎𝑘+𝑏𝑘 𝑘 ).
Oletuksen nojalla 𝑓(𝑝𝑎) = 𝑓(𝑝)𝑎, jolloin 𝑓(𝑝𝑎1+𝑏1
1 )𝑓(𝑝𝑎2+𝑏2
2 ) · · · 𝑓(𝑝𝑎𝑘+𝑏𝑘
𝑘 ) = 𝑓(𝑝1)𝑎1+𝑏1𝑓(𝑝2)𝑎2+𝑏2· · · 𝑓(𝑝𝑘)𝑎𝑘+𝑏𝑘
= 𝑓(𝑝1)𝑎1𝑓(𝑝1)𝑏1𝑓(𝑝2)𝑎2𝑓(𝑝2)𝑏2· · · 𝑓(𝑝𝑘)𝑎𝑘𝑓(𝑝𝑘)𝑏𝑘
= 𝑓(𝑝1)𝑎1𝑓(𝑝2)𝑎2· · · 𝑓(𝑝𝑘)𝑎𝑘𝑓(𝑝1)𝑏1𝑓(𝑝2)𝑏2· · · 𝑓(𝑝𝑘)𝑏𝑘.
Edelleen oletuksesta ja funktion 𝑓 multiplikatiivisuudesta seuraa, että 𝑓(𝑝1)𝑎1𝑓(𝑝2)𝑎2· · · 𝑓(𝑝𝑘)𝑎𝑘𝑓(𝑝1)𝑏1𝑓(𝑝2)𝑏2· · · 𝑓(𝑝𝑘)𝑏𝑘
= 𝑓(𝑝𝑎1
1 )𝑓(𝑝𝑎2
2 ) · · · 𝑓(𝑝𝑎𝑘
𝑘 )𝑓(𝑝𝑏1
1 )𝑓(𝑝𝑏2
2 ) · · · 𝑓(𝑝𝑏𝑘
𝑘 )
= 𝑓(𝑝𝑎1
1 · 𝑝𝑎2
2 · · ·𝑝𝑎𝑘
𝑘 )𝑓(𝑝𝑏1
1 · 𝑝𝑏2
2 · · ·𝑝𝑏𝑘
𝑘 )
= 𝑓(𝑚)𝑓(𝑛).
Täten lause on todistettu. □
Lause 2.16. Olkoon 𝑓 multiplikatiivinen funktio. Tällöin funktio 𝑓 on täydellisesti multiplikatiivinen, jos ja vain jos
𝑓−1 =𝜇 𝑓
aina, kun𝑛on positiivinen kokonaisluku.
Todistus. (Ks. [2, s. 36]). Oletetaan, että 𝑓 on täydellisesti multiplikatiivinen funktio.
Nyt
(𝜇 𝑓 ∗ 𝑓) (𝑛) =∑︁
𝑑|𝑛
𝜇(𝑑)𝑓(𝑑)𝑓 (︂𝑛
𝑑 )︂
.
Oletuksen nojalla 𝑓 on täydellisesti multiplikatiivinen, joten 𝑓(𝑑)𝑓
(︂𝑛 𝑑 )︂
= 𝑓(𝑛).
Siis
∑︁
𝑑|𝑛
𝜇(𝑑)𝑓(𝑑)𝑓 (︂𝑛
𝑑 )︂
= 𝑓(𝑛)∑︁
𝑑|𝑛
𝜇(𝑑) = 𝑓(𝑛)𝜀(𝑛)=𝜀(𝑛),
sillä 𝑓(1) =1 ja𝜀(𝑛)=0, kun𝑛 >1. Näin ollen 𝑓−1= 𝜇 𝑓. Oletetaan sitten, että 𝑓−1= 𝜇 𝑓. Tällöin
∑︁
𝑑|𝑛
𝜇(𝑑)𝑓(𝑑)𝑓 (︂𝑛
𝑑 )︂
=0 aina, kun𝑛 >1.
Silloin sijoittamalla summaan luku𝑛= 𝑝𝑎saadaan, että
∑︁
𝑑|𝑝𝑎
𝜇(𝑑)𝑓(𝑑)𝑓 (︂𝑝𝑎
𝑑 )︂
=0. Erityisesti
𝜇(1)𝑓(1)𝑓(𝑝𝑎) +𝜇(𝑝)𝑓(𝑝)𝑓(𝑝𝑎−1) =0,
missä𝜇(1) = 𝑓(1) =1 ja 𝜇(𝑝) =−1.Siis 𝑓(𝑝𝑎) = 𝑓(𝑝)𝑓(𝑝𝑎−1), joten induktiolla saadaan, että 𝑓(𝑝𝑎) = 𝑓(𝑝)𝑎, missä funktio 𝑓 on multiplikatiivinen. Näin ollen lauseen 2.16 mukaan funktio 𝑓 on täydellisesti multiplikatiivinen. □ Lause 2.17. ([13, s. 248], tehtävä 47.)Jos funktiot 𝑓 ja𝑔ovat täydellisesti multipli- katiivisia, niin funktio fg on täydellisesti multiplikatiivinen.
Todistus. Oletetaan, että funktiot 𝑓 ja𝑔 ovat täydellisesti multiplikatiivisia. Olkoot 𝑚ja𝑛positiivisia kokonaislukuja. Tällöin
(𝑓 𝑔) (𝑚 𝑛)= 𝑓(𝑚 𝑛)𝑔(𝑚 𝑛) = 𝑓(𝑚)𝑓(𝑛)𝑔(𝑚)𝑔(𝑛)= (𝑓 𝑔) (𝑚) (𝑓 𝑔) (𝑛),
joten funktio 𝑓 𝑔 on täydellisesti multiplikatiivinen. □ Lause 2.18. ([2, s. 49], tehtävä 27.)Jos funktio 𝑓 on täydellisesti multiplikatiivinen, niin
𝑓(𝑔∗ℎ) = (𝑓 𝑔) ∗ (𝑓 ℎ) aina, kun𝑔jaℎovat aritmeettisia funktioita.
Todistus. Oletetaan, että funktio 𝑓 on täydellisesti multiplikatiivinen. Nyt (︁(𝑓 𝑔) ∗ (𝑓 ℎ))︁
(𝑛) =∑︁
𝑑|𝑛
𝑓(𝑑)𝑔(𝑑)𝑓 (︂𝑛
𝑑 )︂
ℎ (︂𝑛
𝑑 )︂
.
Oletuksen nojalla 𝑓 on täydellisesti multiplikatiivinen, joten 𝑓(𝑑)𝑓
(︂𝑛 𝑑 )︂
= 𝑓(𝑛).
Täten
∑︁
𝑑|𝑛
𝑓(𝑑)𝑔(𝑑)𝑓 (︂𝑛
𝑑 )︂
ℎ (︂𝑛
𝑑 )︂
= 𝑓(𝑛)∑︁
𝑑|𝑛
𝑔(𝑑)ℎ (︂𝑛
𝑑 )︂
= (︁
𝑓(𝑔∗ℎ))︁
(𝑛)
ja lause on saatu todistettua. □
2.9 Joseph Liouville
Ranskalainen matemaatikko Joseph Liouville (1809–1882) tunnetaan hänen tutki- muksistaan, kuten lukuteorian, analyysin, matemaattisen fysiikan ja tähtitieteen osa- alueilla. Ranskassa Liouville opiskeli vuodesta 1825 lähtien École Polytechniquen koulutuslaitoksessa ja jatkoi opintojaan Ecole des Ponts et Chausséessiin, missä hän opiskeli vuoteen 1830 asti. Opintojen aikana hän kirjoitti artikkeleita muun muassa elektrodynamiikasta, lämpöteoriasta ja osittaisdifferentiaaliyhtälöistä. [13, s. 248]
Vuonna 1831 Liouville sai assistentin viran École Polytechniquesissa ja aloitti opettamaan eri koulutuslaitoksissa. Liouville perusti samana vuonna aikakauslehden Journal de Mathématiques Pures et Appliquées, jolla oli tärkeä rooli 1800-luvun matematiikan kehitykselle Ranskassa. [13, s. 248] Liouville pysyi lehden päätoi- mittajana vuoteen 1874 saakka. Vuonna 1836 Liouville valmistui tohtoriksi sovel- taessaan Fourier’n sarjaa matemaattisessa fysiikassa. Tämän jälkeen hän sai opettaa yliopistotasolla. [11, s. 175] Vuonna 1838 Liouville nimitettiin professoriksi Éco- le Polytechniquesiin. Liouville sai laitoksen johtajan viran vuonna 1851 Collége de Francen tutkimuslaitoksesta ja mekaniikan laitoksen johtajan viran vuonna 1857 Faculté des Science -instituutiosta. [13, s. 248]
Liouville tutki laaja-alaisesti eri matematiikan aloja. Esimerkiksi Liouville antoi ensimmäisenä täsmällisen esimerkin transsendenttiluvusta määrittäessään Liouvil- len luvun. [11, s. 175] [13, s. 248] Hänen nimensä liitetään kompleksianalyysissä Liouvillen lauseeseen [5, s. 799]. Hänet myös tunnetaan Sturm-Liouvillen teoriasta, jota käytetään integraaliyhtälöiden ratkaisemiseen. Lisäksi hän myötävaikutti dif- ferentiaaligeometriaan. Yhteensä hänen matemaattisten tekstiensä kokonaistuotanto on yli 400 kappaletta, joista melkein puolet käsittelee lukuteoriaa. [13, s. 248]
2.10 Liouvillen funktio
Määritellään Joseph Liouville mukaan nimetty Liouvillen funktio𝜆, joka on tärkeä esimerkki täydellisesti multiplikatiivisesta funktiosta.
Määritelmä 2.8. (Vrt. [2, s. 37]). Liouvillen funktio 𝜆 määritellään siten, että 𝜆(1) = 1 ja jos positiivisen kokonaisluvun 𝑛 kanoninen alkutekijähajotelma on 𝑛= 𝑝𝑎1
1 · 𝑝𝑎2
2 · · ·𝑝𝑎𝑘
𝑘 , niin𝜆(𝑛) =(−1)𝑎1+𝑎2+···+𝑎𝑘.
Lause 2.19. Liouvillen funktio𝜆on täydellisesti multiplikatiivinen.
Todistus. Olkoot𝑚ja𝑛positiivisia kokonaislukuja, ja olkoot niiden alkutekijähajo- telmat muotoa𝑚 = 𝑝𝛼1
1 · 𝑝𝛼2
2 · · ·𝑝𝛼𝑘
𝑘 ja𝑛= 𝑝
𝛽1 1 · 𝑝
𝛽2 2 · · ·𝑝
𝛽𝑘
𝑘 , missä𝛼1, 𝛼2, . . . , 𝛼𝑘 ja 𝛽1, 𝛽2, . . . , 𝛽𝑘 ovat ei-negatiivisia kokonaislukuja. Silloin
𝜆(𝑚 𝑛) =𝜆(𝑝𝛼1
1 · 𝑝𝛼2
2 · · ·𝑝
𝛼𝑘 𝑘 · 𝑝
𝛽1 1 · 𝑝
𝛽2 2 · · ·𝑝
𝛽𝑘
𝑘 )
=(−1)𝛼1+𝛼2+···+𝛼𝑘+𝛽1+𝛽2+···+𝛽𝑘
=(−1)𝛼1+𝛼2+···+𝛼𝑘(−1)𝛽1+𝛽2+···+𝛽𝑘
=𝜆(𝑝
𝛼1 1 · 𝑝
𝛼2 2 · · ·𝑝
𝛼𝑘 𝑘 )𝜆(𝑝
𝛽1 1 · 𝑝
𝛽2 2 · · ·𝑝
𝛽𝑘
𝑘 )
=𝜆(𝑚)𝜆(𝑛).
Näin ollen funktio𝜆on täydellisesti multiplikatiivinen. □ Lause 2.20. Olkoon𝑛≥ 1. Tällöin
∑︁
𝑑|𝑛
𝜆(𝑑) =
⎧⎪
⎪
⎨
⎪⎪
⎩
1, jos luku n on neliö, 0, muulloin.
Lisäksi𝜆−1(𝑛) =|𝜇(𝑛) | kaikille kokonaisluvuille𝑛. Todistus. (Ks. [2, s. 38]). Merkitään𝑔(𝑛) =∑︁
𝑑|𝑛𝜆(𝑑). Tällöin funktio𝑔on seurauk- sen 2.1 perusteella multiplikatiivinen. Nyt
𝑔(𝑝𝑎) = ∑︁
𝑑|𝑝𝑎
𝜆(𝑑) =1+𝜆(𝑝) +𝜆(𝑝2) + · · · +𝜆(𝑝𝑎)
=1−1+1− · · · + (−1)𝑎
=
⎧⎪
⎪
⎨
⎪⎪
⎩
0, jos𝑎on pariton, 1, jos𝑎on parillinen.
Jos𝑛 =∏︁𝑘
𝑖=1𝑝
𝑎𝑖
𝑖 , niin𝑔(𝑛) =∏︁𝑘
𝑖=1𝑔(𝑝
𝑎𝑖
𝑖 ). Jos jokin eksponentti𝑎𝑖on pariton, niin 𝑔(𝑝𝑎𝑖
𝑖 ) = 0 ja 𝑔(𝑛) = 0. Jos kaikki eksponentit 𝑎𝑖 ovat parillisia, niin 𝑔(𝑝𝑎𝑖
𝑖 ) = 1 ja 𝑔(𝑛) = 1. Näin ollen 𝑔(𝑛) = 1, jos luku 𝑛 on neliöllä jaollinen, ja 𝑔(𝑛) = 0 muulloin. Lisäksi Möbiuksen funktion määritelmään 2.4 nojaten saadaan, että 𝜆−1(𝑛) =𝜇(𝑛)𝜆(𝑛)= 𝜇2(𝑛) =|𝜇(𝑛) |. □
3 Modulaarinen aritmetiikka ja Ramanuja- nin summa
3.1 Karl Friedrich Gauss
Karl Friedrich Gauss (1777–1855) oli saksalainen matemaatikko, tähtitieteilijä ja fyy- sikko, joka saavutuksillaan tuli tunnetuksi ja kunnioitetuksi ”matemaatikkojen ruh- tinaaksi” [12, s. 184–185]. Hän oli matemaattisesti huippulahjakas pienestä pitäen.
Sanotaan, että kolmevuotiaana Gauss korjasi virheen isänsä palkkakuitista. Toisen tarinan mukaan kahdeksanvuotias Gauss sai aritmetiikan oppitunnilla opettajaltaan haastavan ja aikaa vievän tehtävän, jossa piti laskea sadan ensimmäisen kokonais- luvun summa. Hetkessä Gauss sai oikeaksi vastaukseksi 50·101 = 5050, sillä hän jaotteli termit pareittain siten, että 1+100=101,2+99=101, . . . ,50+51=101. [13, s. 146] Opettaja kertoi Gaussin poikkeuksellisista taidoista Braunschweigin herttual- le Carl Wilhelm Friedrichille. Herttua alkoi tukemaan rahallisesti Gaussin opiskelua ja Gauss pääsi opiskelemaan Göttigenin yliopistoon vuonna 1795. [5, s. 696]
Vuonna 1796 Gauss ratkaisi 2000 vuotta vanhan matemaattisen ongelman ja kon- struoi 17-sivuisen säännöllisen monikulmion käyttämällä vain viivoitinta ja harppia.
Gauss vastaanotti tohtorin arvon vuonna 1799 ja väitöskirjassaan hän esitti ensim- mäisen täsmällisen todistuksen keskeiselle algebran peruslauseelle, jonka mukaan jokaisella reaalikertoimisella astetta𝑛 olevalla polynomilla on täsmälleen 𝑛juurta.
[13, s. 146] [5, s. 698]
Braunschweigin herttua tuki edelleen Gaussia taloudellisesti, joten Gaussin ei tarvinnut etsiä töitä tai käyttää aikaansa opettamiseen, vaan hänellä oli mahdollisuus keskittyä täysin tutkimustyötön [10, s. 170]. Vuonna 1801 Gauss julkaisi lukuteoriaa käsittelevän klassikkoteoksenDisquisitiones Arithmeticae, jossa muun muassa esi- tellään kongruenssin ja jäännösluokan käsite sekä todistetaan aritmetiikan peruslause ja neliönjäännöslause [12, s. 184] [5, s. 698]. Samaisena vuonna Gauss myötävaikutti tähtitieteen alalla laskiessaan asteroidi Cereksen liikeradan. Gaussin maine kasvoi Euroopassa ja vuonna 1802 hän sai työtarjouksen Pietarin akatemiasta, mutta Gauss jäi Braunschweigiin herttuan korottaessa stipendin suuruutta. Braunschweigin hert- tuan kuoltua sodassa vuonna 1806 Gauss tarvitsi uuden tulonlähteen. Vuonna 1807 Gaussista tuli Göttingenin yliopiston tähtitieteen professori ja observatorion johtaja
viettäen siellä loppuelämänsä. [12, s. 184–185]
Gauss tunnetaan monista tutkimuksistaan geometriassa, algebrassa, analyysissä, tähtitieteessä ja matemaattisessa fysiikassa. Erityisesti hän oli kiinnostunut lukuteo- riasta. Hänen mukaansa ”matematiikka on tieteiden kuningatar ja lukuteoria on ma- tematiikan kuningatar”. [13, s. 146] Matematiikan lisäksi Gauss tutki maanmittausta, magnetismia ja optiikkaa [12, s. 184].
3.2 Täydellinen ja supistettu jäännössysteemi
Tässä alaluvussa tarkastellaan kongruenssin perustuloksia ja määritellään täydellinen ja supistettu jäännössysteemi. Olkoot𝑎, 𝑏 kokonaislukuja ja olkoon𝑚 positiivinen kokonaisluku. Sanotaan, että luku𝑎 on kongruenttiluvun 𝑏 kanssa modulo 𝑚, jos 𝑚 | 𝑎−𝑏. Lukujen𝑎ja𝑏 kongruenssia merkitään𝑎 ≡ 𝑏 (mod 𝑚).
Lause 3.1. Olkoot luvut𝑎,𝑏kokonaislukuja siten, että𝑎 =𝑚 𝑞1+𝑟1ja𝑏 =𝑚 𝑞2+𝑟2, missä0 ≤𝑟1, 𝑟2 < 𝑚. Silloin𝑎 ≡𝑏 (mod 𝑚), jos ja vain jos𝑟1=𝑟2.
Todistus. (Ks. [1, s. 30]). Koska𝑎−𝑏 =𝑚 𝑞1+𝑟1− (𝑚 𝑞2+𝑟2) =𝑚(𝑞1−𝑞2) + (𝑟1−𝑟2), niin 𝑚 | 𝑎− 𝑏, jos vain jos 𝑚 | 𝑟1−𝑟2. Oletuksen nojalla 0 ≤ 𝑟1, 𝑟2 < 𝑚, joten
|𝑟1−𝑟2| < 𝑚, jolloin𝑚 |𝑟1−𝑟2, jos ja vain jos𝑟1=𝑟2. □ Lause 3.2. Jos𝑎 ≡𝑏 (mod 𝑚) ja𝑐 ≡ 𝑑(mod𝑚), niin
(i) 𝑎+𝑐≡ 𝑏+𝑑 (mod 𝑚), (ii) 𝑎−𝑐≡ 𝑏−𝑑 (mod 𝑚), (iii) 𝑎 𝑐≡ 𝑏 𝑑 (mod 𝑚).
Todistus. (Vrt. [13, s. 149]). Oletetaan, että 𝑎 ≡ 𝑏 (mod 𝑚) ja 𝑐 ≡ 𝑑 (mod 𝑚).
Silloin𝑚 | (𝑎−𝑏) ja 𝑚 | (𝑐−𝑑), minkä seurauksena on olemassa kokonaisluvut𝑘 ja𝑙 siten, että𝑘 𝑚 =𝑎−𝑏ja𝑙 𝑚 =𝑐−𝑑.
Kohdassa (i) huomataan, että
(𝑎+𝑐) − (𝑏+𝑑) = (𝑎−𝑏) + (𝑐−𝑑) =𝑘 𝑚+𝑙 𝑚 = (𝑘+𝑙)𝑚,
jolloin𝑚 | [(𝑎+𝑐) − (𝑏+𝑑)]. Siis𝑎+𝑐 ≡ 𝑏+𝑑 (mod 𝑚).
Kohta (ii) todistetaan vastaavalla tavalla siten, että
(𝑎−𝑐) − (𝑏−𝑑) =(𝑎−𝑏) − (𝑐−𝑑) = 𝑘 𝑚−𝑙 𝑚 = (𝑘−𝑙)𝑚,
jolloin𝑚 | [(𝑎−𝑐) − (𝑏−𝑑)]. Tällöin𝑎−𝑐 ≡ 𝑏−𝑑 (mod 𝑚). Todistetaan kohta (iii). Nyt
𝑎 𝑐−𝑏 𝑑 =𝑎 𝑐−𝑏 𝑐+𝑏 𝑐−𝑏 𝑑 =𝑐(𝑎−𝑏) +𝑏(𝑐−𝑑)=𝑐 𝑘 𝑚+𝑏𝑙 𝑚 =𝑚(𝑐 𝑘 +𝑏𝑙). Tällöin𝑚 | (𝑎 𝑐−𝑏 𝑑), joten𝑎 𝑐 ≡ 𝑏 𝑑 (mod 𝑚). □ Seuraus 3.1. (Ks. [9, s. 33]). Jos𝑎 ≡ 𝑏 (mod 𝑚), niin kaikilla𝑘 ∈ℤpätee𝑎 𝑘 ≡𝑏 𝑘 (mod 𝑚).
Todistus. Oletetaan, että𝑎 ≡ 𝑏 (mod 𝑚)eli𝑚 | (𝑎−𝑏). Huomataan, että
(𝑎− 𝑏) | 𝑘(𝑎−𝑏). Tällöin jaollisuuden perusominaisuuksien nojalla𝑚 | 𝑘(𝑎−𝑏)
eli𝑚 | (𝑎 𝑘−𝑏 𝑘). Näin ollen𝑎 𝑘 ≡ 𝑏 𝑘 (mod 𝑚). □
Seuraus 3.2. (Ks. [9, s. 33]). Jos𝑎≡ 𝑏 (mod 𝑚), niin kaikilla𝑘 ∈ℤ+pätee𝑎𝑘 ≡𝑏𝑘 (mod 𝑚).
Todistus. Oletetaan, että𝑎 ≡ 𝑏 (mod 𝑚). Todistetaan induktiolla, että kaikilla 𝑘 ∈ℤ+ pätee𝑎𝑘 ≡ 𝑏𝑘 (mod 𝑚).
1. Perusaskel. Osoitetaan, että väite on tosi, kun𝑘 =1.
Nyt oletuksen nojalla𝑎≡ 𝑏 (mod 𝑚).
2. Induktioaskel. Oletetaan, että väite on tosi, kun𝑘 =𝑛.
Silloin 𝑎𝑛 ≡ 𝑏𝑛 (mod 𝑚) ja oletuksen nojalla edelleen 𝑎 ≡ 𝑏 (mod 𝑚). Tällöin näiden kongruenssiyhtälöiden kertomisesta keskenään saadaan lauseen 3.2 nojalla 𝑎𝑛+1≡ 𝑏𝑛+1 (mod 𝑚).
3. Johtopäätös. Induktioperiaatteen nojalla väite on tosi kaikilla 𝑘 ∈ ℤ+ ja lause on
näin ollen todistettu. □
Lause 3.3. Oletetaan, että (𝑘 , 𝑚) = 𝑑. Silloin 𝑘 𝑎 ≡ 𝑘 𝑏 (mod 𝑚), jos ja vain jos 𝑎 ≡𝑏 (mod 𝑚/𝑑).
Todistus. (Ks. [9, s. 33]). Oletetaan, että (𝑘 , 𝑚) = 𝑑. Silloin 𝑘 = 𝑡 𝑑 ja 𝑚 = 𝑠 𝑑 joillakin kokonaisluvuilla 𝑡 ja 𝑠. Jos 𝑚 | (𝑘 𝑎 − 𝑘 𝑏), niin 𝑘(𝑎− 𝑏) = 𝑢𝑚 jollakin kokonaisluvulla 𝑢. Sijoittamalla yhtälöön 𝑘(𝑎 −𝑏) = 𝑢𝑚 luvut 𝑘 = 𝑡 𝑑 ja 𝑚 = 𝑠 𝑑 saadaan
𝑡 𝑑(𝑎−𝑏) =𝑢 𝑠 𝑑
⇔ 𝑡(𝑎−𝑏) =𝑢 𝑠
⇔ 𝑡 𝑎−𝑡 𝑏 =𝑢 𝑠,
