TAMPEREEN YLIOPISTO Pro gradu -tutkielma
Jussi Kangas
Aritmeettiset funktiot ja
totienttien karakterisointeja
Matematiikan ja tilastotieteen laitos Matematiikka
Kesäkuu 2009
Tampereen yliopisto
Matematiikan ja tilastotieteen laitos
KANGAS, JUSSI Aritmeettiset funktiot ja totienttien karakterisointeja Pro gradu -tutkielma, 99 s.
Matematiikka Kesäkuu 2009
Tiivistelmä
Tässä gradussa käsitellään aritmeettisia funktioita ja niiden ominai- suuksia sekä tiettyjä aritmeettisia funktioita, joita kutsutaan totien- teiksi. Aritmeettinen funktio on reaali- tai kompleksiarvoinen funktio, jonka määrittelyjoukko on positiivisten kokonaislukujen joukko.
Tutkielman alkupuoli keskittyy esittelemään aritmeettisten funktioi- den peruskäsitteitä ja tuloksia. Alkupuolella tutustutaan muun muas- sa käsitteisiin Dirichlet’n konvoluutio, aritmeettisen funktion käänteis- funktio Dirichlet’n konvoluution suhteen, multiplikatiivinen funktio ja täydellisesti multiplikatiivinen funktio. Näitä käsitteitä ja niihin liitty- viä tuloksia tarkastellaan melko laajasti ja monipuolisesti. Tutkielman alkupuolen tarkoitus on antaa lukijalle välineitä tutkielman loppupuo- len tulosten käsittelyyn.
Tutkielman loppupuoli käsittelee totientteja. Totientti on aritmeetti- nen funktio, joka voidaan esittää täydellisesti multiplikatiivisen funk- tion ja täydellisesti multiplikatiivisen funktion käänteisfunktion Dirich- let’n konvoluutiona. Tutkielman loppupuolella esitellään ja kootaan yhteen totienttien ominaisuuksia sekä välttämättömiä ja riittäviä eh- toja sille, että aritmeettinen funktio on totientti. Tällaiset ehdot tun- netaan totienttien karakterisointeina. Tutkielman loppupuolella esitel- lään myös yksi uusi totienttien karakterisointi.
Asiasanat: Aritmeettiset funktiot, multiplikatiiviset funktiot, totientit, täydellisesti multiplikatiiviset funktiot
Sisältö
Johdanto 1
1 Aritmeettisten funktioiden peruskäsitteitä 2
1.1 Määritelmä ja esimerkkejä . . . 2
1.2 Dirichlet’n konvoluutio . . . 4
1.3 Käänteisfunktiot Dirichlet’n konvoluution suhteen . . . 6
2 Multiplikatiivisuus 12 2.1 Multiplikatiivisuuden määritelmä . . . 12
2.2 Multiplikatiivisten funktioiden ominaisuuksia . . . 13
2.2.1 Käänteisfunktion multiplikatiivisuus . . . 17
2.2.2 Möbiuksen funktion multiplikatiivisuus . . . 19
2.2.3 Dirichlet’n konvoluution multiplikatiivisuus . . . 21
2.2.4 Eulerin funktion multiplikatiivisuus . . . 24
2.3 Täydellisesti multiplikatiiviset funktiot . . . 32
2.3.1 Täydellisesti multiplikatiivisten funktioiden karakteri- sointeja ja ominaisuuksia I . . . 33
2.3.2 Täydellisesti multiplikatiivisen funktion käänteisfunktio 36 2.3.3 Täydellisesti multiplikatiivisten funktioiden karakteri- sointeja ja ominaisuuksia II . . . 38
2.4 Aritmeettisen funktion Bellin sarja . . . 44
3 Totientit 48 3.1 Totientin määritelmä ja esimerkkejä . . . 48
3.2 Totienttien karakterisointeja ja ominaisuuksia . . . 49
Viitteet 99
Johdanto
Tämä tutkielma käsittelee aritmeettisia funktioita ja niiden ominaisuuksia sekä tiettyjä aritmeettisia funktioita, joita kutsutaan totienteiksi. Tutkielma jakautuu kahteen osaan. Ensimmäisen osan muodostavat luvut 1 ja 2 ja toisen osan muodostaa luku 3. Ensimmäisen osan tarkoitus on esitellä monipuoli- sesti aritmeettisia funktioita ja niiden ominaisuuksia sekä antaa apuvälineitä toisen osan tulosten käsittelyyn. Toisessa osassa keskitytään pääasiassa edel- lä mainittujen totienttien karakterisointeihin. Totientin karakterisointi tar- koittaa välttämätöntä ja riittävää ehtoa sille, että aritmeettinen funktio on totientti.
Luvussa 1 esitellään aritmeettisen funktion määritelmä ja muutamia tunne- tuimpia aritmeettisia funktioita. Lisäksi tutustutaan aritmeettisten funktioi- den ja tutkielman jatkon kannalta tärkeisiin käsitteisiin, kuten Dirichlet’n konvoluutioon ja funktion käänteisfunktioon tämän konvoluution suhteen.
Luku 2 keskittyy ehkä tärkeimpään aritmeettisten funktioiden luokkaan eli multiplikatiivisiin funktioihin. Pykälässä 2.1 esitellään multiplikatiivisuuden määritelmä ja muutamia tunnetuimpia multiplikatiivisia funktioita, ja pykä- lässä 2.2 esitellään laajasti multiplikatiivisten funktioiden ominaisuuksia. Py- kälässä 2.3 tutustutaan täydellisesti multiplikatiivisiin funktioihin sekä niiden ominaisuuksiin. Pykälässä 2.4 esitellään aritmeettisille funktioille määritelty muodollinen potenssisarja, joka tunnetaan nimellä Bellin sarja.
Luvuissa 1 ja 2 esitellään useita määritelmiä, tuloksia ja esimerkkejä, jotka ovat varsin hyödyllisiä luvussa 3. Tärkeimpinä lähdeteoksina luvuissa 1 ja 2 toimivat Paul J. McCarthyn kirja Introduction to Arithmetical Functions [7]
ja Tom M. Apostolin teos Introduction to Analytic Number Theory [1].
Luku 3 vie lukijan tarkastelemaan totientteja. Totientti on aritmeettinen funktio, joka voidaan esittää täydellisesti multiplikatiivisen funktion ja täy- dellisesti multiplikatiivisen funktion käänteisfunktion Dirichlet’n konvoluu- tiona. Pykälässä 3.1 esitellään totientin määritelmä ja muutamia totientteja sekä huomautuksia totientteihin liittyen. Pykälässä 3.2 esitellään ja käydään läpi lukuisia totienttien karakterisointeja. Lauseessa 3.3 esitellään myös yksi uusi totienttien karakterisointi. Luvun 3 tärkein lähde on Pentti Haukkasen artikkeliSome Characterizations of Totients [4] ja tätä täydentämässä Pentti Haukkasen käsikirjoitus Some Further Characterizations of Totients [5].
Todistusten kannalta tärkeimmät aritmeettisia funktioita koskevat tulokset esitellään tutkielmassa. Lukijan oletetaan hallitsevan lukuteorian perusteet erityisesti jaollisuuteen liittyen sekä algebran ja joukko-opin perusmerkinnät.
Lisäksi lukijan tulisi ymmärtää erilaisia matemaattisia todistustekniikoita.
1 Aritmeettisten funktioiden peruskäsitteitä
Tässä luvussa esitellään aritmeettisen funktion määritelmä ja muutamia tun- netuimpia aritmeettisia funktioita. Lisäksi tutustutaan aritmeettisille funk- tioille määriteltyyn laskutoimitukseen, joka tunnetaan Dirichlet’n konvoluu- tiona tai Dirichlet’n tulona. Aritmeettisten funktioiden tutkimuksen kannal- ta erittäin tärkeä käsite on myös multiplikatiivisuus, mutta tämän käsitteen tärkeyden vuoksi sille on varattu oma lukunsa, jossa siihen keskitytään sy- vällisemmin.
Todettakoon, että kun tekstissä puhutaan luvun n tekijöistä, niin tarkoite- taan luvun n positiivisia tekijöitä. Merkintä Ptarkoittaa kaikkien alkuluku- jen joukkoa ja merkintäN0 tarkoittaa positiivisten kokonaislukujen joukkoa, johon on liitetty luku 0.
Huomautus. Algebran tapojen mukaisesti sovimme, että a0 = 1 kaikilla kantaluvuilla a∈C. Siis myös 00 = 1.
1.1 Määritelmä ja esimerkkejä
Määritelmä 1.1. (Ks. [7, s. 1].) Aritmeettinen funktio on reaaliarvoinen (tai kompleksiarvoinen) funktio, jonka määrittelyjoukko on positiivisten ko- konaislukujen joukko.
Aritmeettisen funktion (puhutaan myös lukuteoreettisesta funktiosta [1, s. 24]) määritelmä ei siis aseta kovinkaan tarkkoja rajoituksia funktiolle tai sille miten se kuvaa positiivisia kokonaislukuja kompleksiluvuiksi. Jokainen kuvaus positiivisten kokonaislukujen joukolta kompleksilukujen joukkoon on aritmeettinen funktio. Näin ollen, kuten esimerkiksi McCarthyn teoksessa [7, s. 1] todetaan, esimerkkejä tällaisista funktioista voitaisiin määritellä täysin mielivaltaisesti ja niitä olisi tarjolla lukuisia. Esimerkiksi voitaisiin määritel- lä, että
f :Z+ −→C, f(n) = 1
√5(αn−βn), missä α= 1 +√ 5
2 ja β =α−1. Näin määriteltynä f on funktio, joka kuvaa positiivisia kokonaislukuja kompleksiluvuiksi (tai tarkemmin sanottuna positiivisiksi kokonaisluvuiksi).
Siis f on aritmeettinen funktio.1
1Näin määriteltynäf kuvaa luvunnFibonaccin lukujonon n.termiksi [8, s. 28].
Koska aritmeettisista funktioista käytetään myös nimitystä lukuteoreettinen funktio, ei liene yllätys, että tunnetuimmat aritmeettiset funktiot kertovat yleensä jotain kuvattavan luvunnominaisuuksista. Seuraavaksi käydään läpi tällaisia funktioita, jotka ovat jatkon kannalta mielenkiintoisia.
Esimerkki 1.1. Eulerin2 funktio φkertoo niiden positiivisten kokonaisluku- jenx määrän, jotka ovat pienempiä tai yhtäsuuria kuin lukunja suhteellisia alkulukuja tämän kanssa. McCarthy muotoilee Eulerin funktion määritelmän siten, että
φ(n) = niiden kokonaislukujenx määrä, joille 1≤x≤n ja (x, n) = 1 kaikilla n ∈ Z+ [7, s. 1]. Eulerin funktio on yksi tunnetuimmista ja luku- teorian kannalta mielenkiintoisimmista aritmeettisista funktioista. Eulerin funktio tunnetaan myös nimellä Eulerin φ-funktio, Eulerin totienttifunktio tai Eulerin totientti [1, s. 25]. Totienttifunktion määritelmä ja totienttifunk- tioiden ominaisuuksia esitellään luvussa 3.
Esimerkki 1.2. (Ks. [7, s. 1].) Olkoonk∈N0. Määritellään funktioσksiten, että
σk(n) = X
d|n
dk kaikilla n∈Z+.
Näin määriteltynä σk-funktio muodostaa joukon erilaisia aritmeettisia funk- tioita, sillä sen lauseke riippuu vakiostak. Tärkeimpiä näistä funktioista ovat σ1 ja σ0, ja näille on vakiintuneet omat merkintätapansakin [7, s. 2]. Merki- tään
σ(n) =σ1(n) = X
d|n
d.
Funktio σ ilmoittaa siis luvun n tekijöiden summan. Lisäksi merkitään τ(n) = σ0(n) = X
d|n
1.
Funktio τ saa näin ollen arvokseen luvun n tekijöiden lukumäärän. Funktio- joukko σk tunnetaan myös nimellä tekijäfunktiot [1, s. 38].
Esimerkki 1.3. Toisen tärkeän funktiojoukon muodostavat funktiot Nα (α∈N0), jotka määritellään siten, että Nα(n) =nα, kun n∈Z+. Funktioil- le Nα käytetään myös merkintää ζα [7, s. 2], mistä saadaankin vakiintunut merkintä tapa N0 =ζ. Funktiota ζ kutsutaan zeta-funktioksi. Zeta-funktio
2Leonhard Euler(1707-1783) oli sveitsiläinen matemaatikko, jota pidetään eräänä mer- kittävimmistä matemaatikoista kautta aikain [8, s. 216].
saa siis arvokseen luvun 1 kaikilla positiivisilla kokonaisluvuilla n. Toinen vakiintunut merkintätapa on N1 =N. Tällöin kyseessä on siis funktio, joka kuvaa luvun aina itsekseen.
Näillä funktioilla on mielenkiintoisia ominaisuuksia, joita tarkastellaan enem- män, kun tutustutaan muutamiin tärkeisiin aritmeettisten funktioiden käsit- teisiin, määritelmiin ja ominaisuuksiin. Jatkossa tutustutaan myös muihin tärkeisiin funktioihin ja niiden ominaisuuksiin.
1.2 Dirichlet’n konvoluutio
Aritmeettiset funktiot noudattavat luonnollisesti tavallisia funktioiden yhteenlasku- ja tulosääntöjä [7, s. 2] eli
(f+g)(n) = f(n) +g(n) kaikillan ∈Z+ ja
(f g)(n) =f(n)g(n) kaikillan ∈Z+.
Näiden perussääntöjen lisäksi aritmeettisille funktioille on määritelty monia muitakin laskutoimituksia, joista keskeisin on Dirichlet’n konvoluutiona (tai Dirichlet’n tulona) tunnettu laskuoperaatio.
Määritelmä 1.2. (Ks. [7, s. 2].) Aritmeettisten funktioiden f ja g Dirich- let’n3 konvoluutio f∗g määritellään lausekkeella
(f ∗g)(n) =X
d|n
f(d)g(n
d) kaikillan ∈Z+.
Aritmeettisten funktioiden tutkimisessa Dirichlet’n konvoluutio on yksi tär- keimmistä työkaluista ja aritmeettisista funktioista paljastuu mielenkiintoisia piirteitä Dirichlet’n konvoluution kautta.
Esimerkki 1.4. Tarkastellaan funktioidenNkjaζDirichlet’n konvoluutiota.
Muistetaan, että Nk(n) = nk ja ζ(n) = 1. Täten määritelmän 1.2 mukaan (Nk∗ζ)(n) = X
d|n
Nk(d)ζ(n
d) =X
d|n
dk =σk(n)kaikilla n∈Z+. Siis σk =Nk∗ζ ja näin ollen kaksi erillistä funktiojoukkoaσk ja Nα saadaan liitettyä toisiinsa Dirichlet’n konvoluution avulla.
3G. Lejeune Dirichlet (1805-1859) oli saksalainen matemaatikko [8, s. 74].
Toinen erittäin mielenkiintoinen esimerkki vastaavasta yhteydestä eri funk- tioiden välillä saadaan, kun tarkastellaan funktioiden φ jaζ Dirichlet’n kon- voluutiota.
Esimerkki 1.5. Voidaan osoittaa (katso esimerkiksi [1, s. 26]), että X
d|n
φ(d) =n kaikillan ∈Z+. (1) Kun muistetaan, että ζ(n) = 1 kaikilla n ∈ Z+, niin yhtälö (1) saadaan muotoon
n =X
d|n
φ(d)ζ(n
d) = (φ∗ζ)(n)
kaikilla n∈Z+. Siis φ∗ζ =N. Täten Dirichlet’n konvoluutio liittää luonte- vasti toisiinsa nämäkin aritmeettiset funktiot.
Dirichlet’n konvoluutio on kommutatiivinen ja assosiatiivinen. Lisäksi se on distributiivinen yhteenlaskun suhteen. (Nämä säännöt ovat myös luonnolli- sesti voimassa aritmeettisten funktioiden tavallisille yhteen- ja kertolaskuil- le.)
Lause 1.1. (Ks. [7, s. 3].) Jos f, g ja h ovat aritmeettisia funktioita, niin a) f ∗g =g∗f,
b) (f ∗g)∗h=f ∗(g∗h) ja c) f ∗(g+h) = f∗g+f ∗h.
Todistus.Sivuutetaan. Todistus löytyy esimerkiksi McCarthyn teoksesta [7, s. 3].
Huomautus. Voidaan helposti todistaa induktiota käyttämällä, että lauseen 1.1 tulokset ovat yleistettävissä useamman funktion tapauksiin. Jos siis k ∈ Z+ ja f, f1, . . . , fk sekä g1, . . . , gk ovat aritmeettisia funktioita, niin lausekkeeseenf1∗ · · · ∗fkvoidaan lisätä sulkuja haluttuihin väleihin ja lisäksi f ∗(g1+· · ·+gk) = f∗g1+· · ·+f ∗gk.
Esimerkki 1.6. (Vrt. tehtävä 1.60 McCarthyn teoksessa [7, s. 48].) Olkoot f jag ovat aritmeettisia funktioita. Määritellään aritmeettiset funktiot F ja G siten, että
F(n) =X
d|n
f(d)ja G(n) = X
d|n
g(d)kaikilla n∈Z+.
Täten siis F = f ∗ ζ ja G = g ∗ ζ. Nyt lauseen 1.1 mukaan Dirichlet’n konvoluutio on assosiatiivinen ja kommutatiivinen ja täten
g∗F =F ∗g =f∗ζ∗g =f ∗g∗ζ =f ∗G.
Jos siis määritellään F ja G kuten edellä, niin X
d|n
f(d)G(n
d) =X
d|n
g(d)F(n d) kaikilla aritmeettisilla funktioilla f ja g.
Seuraava aritmeettinen funktio ei funktiona itsessään ole mitenkään ko- vin mielenkiintoinen, mutta se on Dirichlet’n konvoluution kannalta erittäin oleellinen, joten se esitetään määritelmän muodossa.
Määritelmä 1.3. (Vrt. [7, s. 4].) Määritellään aritmeettinen funktioδsiten, että
δ(n) =
1, jos n= 1 0, jos n6= 1.
Lause 1.2. (Ks. [2, s. 28].) Aritmeettinen funktio δ on ykkösfunktio Dirich- let’n konvoluution suhteen. Eli jos f on aritmeettinen funktio, niin
f∗δ =δ∗f =f.
Todistus. Sivuutetaan. Todistus löytyy esimerkiksi Pentti Haukkasen luen- tomonisteesta [2, s. 28].
1.3 Käänteisfunktiot Dirichlet’n konvoluution suhteen
Koska funktio δ on ykkösfunktio Dirichlet’n konvoluution suhteen, niin on mielekästä tutkia millaiset funktiot ovat kääntyviä Dirichlet’n konvoluution suhteen. Eli tutkitaan millaiselle funktiolle f on olemassa sellainen funktio g, että
f ∗g =g∗f =δ.
Koska Dirichlet’n konvoluutio on kommutatiivinen, riittää tarkastella funk- tioita g, jotka toteuttavat toisen ehdoista f∗g =δ tai g ∗f =δ. Jos nyt on olemassa sellaiset funktiot g ja g0, että f ∗g = f ∗g0 = δ, niin tällöin Di- richlet’n konvoluution assosiatiivisuuden ja funktion g määrittelyn mukaan [7, s. 4]
g =δ∗g = (g0∗f)∗g =g0∗(f∗g) = g0∗δ =g0.
Ehdonf∗g =δtoteuttava funktiog on siis yksikäsitteinen. Täten todetaan, että jos f on kääntyvä Dirichlet’n konvoluution suhteen eli tällainen g on olemassa, niin funktiotagkutsutaan funktionf käänteisfunktioksi Dirichlet’n konvoluution suhteen ja siitä käytetään merkintää f−1 [7, s. 4].
On selvää, että kaikilla aritmeettisilla funktioilla ei ole tällaista käänteisfunk- tiota Dirichlet’n konvoluution suhteen. Jos ajatellaan esimerkiksi funktiota f(n) = 0 kaikilla n∈Z+, niin
(f ∗g)(1) =X
d|1
f(d)g(1
d) = 0 6=δ(1)
kaikilla aritmeettisilla funktioilla g. Seuraava lause antaa välttämättömän ja riittävän ehdon sille, milloin aritmeettisella funktiolla on käänteisfunktio Dirichlet’n konvoluution suhteen
Lause 1.3. Aritmeettisella funktiolla f on käänteisfunktio Dirichlet’n kon- voluution suhteen, jos ja vain jos f(1) 6= 0.
Todistus.(Vrt. [7, s. 4].) Oletetaan ensin, että aritmeettisella funktiollaf on käänteisfunktio Dirichlet’n konvoluution suhteen. Tällöin
1 =δ(1) = (f∗f−1)(1) =X
d|1
f(d)f−1(1
d) = f(1)f−1(1).
Tulon nollasäännön mukaan tästä seuraa välittömästi, että f(1) 6= 0. (Ja tietysti myös, että f−1(1)6= 0. Onhan f−1 myös kääntyvä.)
Oletetaan sitten, että f(1) 6= 0. Olkoon n ∈ Z+. Määritellään funktio g rekursiivisesti siten, että
g(1) = 1
f(1) ja g(n) =− 1 f(1)
X
d|n d>1
f(d)g(n
d)aina, kun n >1.
Nyt
(f ∗g)(1) =X
d|1
f(d)g(n
d) =f(1)g(1) = f(1) f(1) = 1.
Jos taas n >1, niin
(f ∗g)(n) = X
d|n
f(d)g(n d)
= f(1)g(n) +X
d|n d>1
f(d)g(n d)
= −f(1) f(1)
X
d|n d>1
f(d)g(n
d) +X
d|n d>1
f(d)g(n d)
= X
d|n d>1
f(d)g(n
d)−X
d|n d>1
f(d)g(n d)
= 0.
Siis(f∗g)(n) =δ(n)kaikillan ∈Z+. Näin olleng on funktionf käänteisfunk-
tio Dirichlet’n konvoluution suhteen.
Huomautus. Todetaan vielä, että edellä esitetyssä todistuksessa johdettiin kaava aritmeettisen funktion f käänteisfunktiolle Dirichlet’n konvoluution suhteen. Jos siis n ∈Z+, niin
f−1(1) = 1
f(1) ja f−1(n) =− 1 f(1)
X
d|n d>1
f(d)f−1(n
d)aina, kun n >1.
Seuraus 1.1. Oletetaan, että f ja g ovat aritmeettisia funktioita ja h = f ∗g. Tällöin h on kääntyvä Dirichlet’n konvoluution suhteen, jos ja vain jos f ja g ovat kääntyviä Dirichlet’n konvoluution suhteen. Lisäksi tällöin h−1 =f−1 ∗g−1.
Todistus. Oletetaan, että h on kääntyvä Dirichlet’n konvoluution suhteen.
Tällöin lauseen 1.3 mukaan h(1)6= 0. Siis (f ∗g)(1) =X
d|1
f(d)g(n
d) =f(1)g(1) 6= 0.
Tulon nollasäännön mukaan tästä seuraa välittömästi, että f(1) 6= 0 ja g(1) 6= 0. Näin ollen lauseen 1.3 mukaan f ja g ovat kääntyviä Dirichlet’n konvoluution suhteen. Jos taas oletetaan, että f(1) 6= 0 ja g(1) 6= 0, niin selvästi myös (f∗g)(1) =f(1)g(1) 6= 0. Siish(1)6= 0 ja tätenh on kääntyvä.
Oletetaan vielä, että h on kääntyvä. On jo siis todistettu, että tällöin myös f ja g ovat kääntyviä. Nyt assosiatiivisuuden ja kommutatiivisuuden perus- teella todetaan, että
(f∗g)∗(f−1∗g−1) = f∗g∗g−1∗f−1 =f ∗δ∗f−1 =f∗f−1 =δ.
Siis h−1 =f−1∗g−1.
Huomautus. Olkoon k ∈ Z+ ja olkoot f1, . . . , fk aritmeettisia funktioita.
On melko triviaalia, että jos h=f1∗ · · · ∗fk, niin tällöinh on kääntyvä, jos ja vain jos f1, . . . , fk ovat kääntyviä, ja lisäksi tällöin h−1 = f1−1∗ · · · ∗fk−1 kaikilla k ∈ Z+. Tämä tulos voidaan helposti todistaa induktiolla luvun k suhteen.
Lauseen 1.3 perusteella voidaan todeta, että esimerkiksi Eulerin funktio φ on kääntyvä, sillä φ(1) 6= 0. Myös kaikki funktiot σk ja Nα ovat kääntyviä.
Tarkastellaan nyt yhtä näistä käänteisfunktioista.
Esimerkki 1.7. (Vrt. [7, s. 5].) Funktio ζ on siis kääntyvä ja sen käänteis- funktiota Dirichlet’n konvoluution suhteen kutsutaan Möbiuksen4 funktioksi.
Möbiuksen funktiosta käytetään vakiintunutta merkintääµ. Koskaµ∗ζ =δ, Möbiuksen funktiolle saadaan seuraava määrittelevä ominaisuus. Josn ∈Z+, niin
(µ∗ζ)(n) = X
d|n
µ(d)ζ(n
d) =X
d|n
µ(d) =
1, jos n= 1 0, jos n6= 1.
Tästä lausekkeesta saadaan ratkaistua funktiolle µ arvoja seuraavasti. Jos n = 1, niin
1 =X
d|1
µ(d) = µ(1).
Kun taas n on alkulukup, 0 =X
d|p
µ(d) =µ(1) +µ(p) = 1 +µ(p),
mistä seuraa, että µ(p) = −1. Jos taas α ∈ Z+ ja α ≥ 2, niin µ(pα) = 0.
Tämä tulos seuraa induktiivisesti funktion µarvoistaµ(1) = 0ja µ(p) =−1 sekä funktion µ määrittelevästä ominaisuudesta. Olkoonα= 2. Tällöin
0 =X
d|p2
µ(d) =µ(1) +µ(p) +µ(p2) =µ(p2)
4August Ferdinand Möbius (1790-1868) oli saksalainen matemaatikko. Möbius tun- nettaan nykyään ehkä parhaiten keksimänsä yksipuolisen pinnan ansiosta. Tämä pinta tunnetaan nimelläMöbiuksen nauha [8, s. 252].
eli µ(pα) = 0, kun α = 2. Tehdään induktio-oletus, että µ(pα) = 0, kun α =k ≥2. Nyt induktio-oletuksen mukaan
0 = X
d|pk+1
µ(d) =µ(1) +µ(p) +· · ·+µ(pk) +µ(pk+1) =µ(pk+1).
Siis µ(pα) = 0 aina, kunα ∈Z+ ja α≥2.
Nyt siis on määritetty funktion µarvot, kunn= 1tai n=pα, missäα ∈Z+. Tarkemmin funktion µ arvoihin päästään käsiksi seuraavassa luvussa, kun määritellään aritmeettisen funktion multiplikatiivisuus.
Jos yhdistetään aritmeettinen funktio g funktion ζ kanssa käyttämällä Di- richlet’n konvoluutiota (vrt.esimerkki 1.6), niin saadaan funktiof, jonka omi- naisuuksiin päästään nyt helposti käsiksi, jos funktion g ominaisuudet ovat tunnettuja. Toisaalta tämä toimii myös kääntäen. Jos funktionf ominaisuu- det ovat tunnettuja ja f = g ∗ζ, niin funktion g ominaisuuksiin päästään käsiksi Möbiuksen funktiota apuna käyttäen. Tämä tulos tunnetaan nimellä Möbiuksen käänteiskaava.
Lause 1.4. Jos f ja g ovat aritmeettisia funktioita, niin f(n) =X
d|n
g(d), (2)
jos ja vain jos
g(n) =X
d|n
f(d)µ(n
d). (3)
Todistus.(Vrt. [1, s. 32].) Olkoot f ja g aritmeettisia funktioita siten, että yhtälö (2) on voimassa. Toisin sanoen siis f = g ∗ζ. Muistetaan, että ζ∗µ=µ∗ζ =δ. Suoritetaan Dirichlet’n konvoluutio funktionµja yhtälön (2) molempien puolien kanssa. Näin saadaan assosiatiivisuuden perusteella yhtä- löf∗µ=g, joka on sama kuin yhtälö (3). Jos taas oletamme, että yhtälö (3) on voimassa, niin suorittamalla Dirichlet’n konvoluutio puolittainζ-funktion kanssa saadaan yhtälö (3) muotoon g∗ζ =f, joka siis on sama kuin yhtälö
(2).
Esimerkki 1.8. (Ks. [7, s. 6].) Esimerkin 1.4 mukaan σk(n) =X
d|n
Nk(d).
Täten Möbiuksen käänteiskaavan perusteella voidaan todeta, että nk=Nk(n) =X
d|n
σk(d)µ(n
d) kaikillan ∈Z+.
Möbiuksen käänteiskaavan avulla päästään käsiksi myös Eulerin funktion φ lausekkeeseen. Tämä funktiohan määriteltiin siten, että
φ(n) = niiden kokonaislukujen x määrä, joille 1≤x≤n ja (x, n) = 1 kaikilla n ∈ Z+. Tällaisten lukujen x löytäminen saattaa olla hyvinkin työ- lästä, mutta Möbiuksen käänteiskaavan avulla saadaan lauseke funktiolle φ, mikä helpottaa huomattavasti funktion φ arvon määrittämistä.
Esimerkki 1.9. (Vrt. [7, s. 7].) Esimerkin 1.5 ja Dirichlet’n konvoluution kommutatiivisuuden perusteella
N(n) =n =X
d|n
φ(d)kaikilla n∈Z+. Möbiuksen käänteiskaavan perusteella tästä seuraa, että
φ(n) = (N ∗µ)(n) =X
d|n
N(d)µ(n
d) = X
d|n
dµ(n
d) kaikillan ∈Z+. Koska Möbiuksen funktion µ arvoja ei vielä tässä vaiheessa tunneta kovin- kaan tarkasti, tämä kaava ei vielä anna kaikkia funktion φarvoja, mutta sen arvot voidaan määrittää kaikille alkuluvuille ja näiden potensseille.
Olkoot p alkuluku ja α∈Z+. Tällöin φ(pα) =X
d|pα
dµ(pα d ).
Tämä kaava sievenee muotoon
φ(pα) =pαµ(1) +pα−1µ(p) =pα−pα−1 =pα
1− 1 p
,
kun muistetaan, että µ(pα) = 0 kaikillaα ≥2. Myös funktion φ arvot pääs- tään määrittelemään tarkemmin seuraavassa luvussa, kun määritellään arit- meettisen funktion multiplikatiivisuus.
Luvussa 1 esitellyt aritmeettiset funktiot ja niitä koskevat tulokset tulevat jatkossa olemaan edelleen tärkeässä asemassa ja funktioiden ominaisuuksiin tutustutaan lisää, kun saadaan enemmän välineitä niiden tutkimiseen.
2 Multiplikatiivisuus
Tässä luvussa määritellään aritmeettisten funktioiden tutkimisen kannal- ta erittäin tärkeä funktion ominaisuus: multiplikatiivisuus. Funktiota, jol- la tämä ominaisuus on, kutsutaan multiplikatiiviseksi funktioksi tai tällai- sen funktion sanotaan olevan multiplikatiivinen. Lisäksi tässä luvussa tutus- tutaan multiplikatiivisten funktioiden ominaisuuksiin ja syvennetään tieto- ja ensimmäisessä luvussa esitellyistä funktioista. Tämän lisäksi määritellään käsite täydellisesti multiplikatiivinen funktio ja tutustutaan myös tällaisten funktioiden ominaisuuksiin.
2.1 Multiplikatiivisuuden määritelmä
Määritelmä 2.1. (Ks. [7, s. 7].) Aritmeettinen funktio f on multiplikatiivi- nen, jos f(n)6= 0 jollain n∈Z+ ja jos
f(mn) = f(m)f(n) kaikillam, n∈Z+, joilla (m, n) = 1.
Multiplikatiiviset funktiot muodostavat tärkeän joukon aritmeettisia funk- tioita. Niillä on usein erittäin mielenkiintoisia ominaisuuksia ja näiden omi- naisuuksien tutkimista helpottaa nimenomaan funktioiden multiplikatiivi- suus. Täten ei ole yllättävää, että tunnetuimmat (ja täten myös tutkituim- mat) aritmeettiset funktiot, kuten φ ja µ, ovat myös multiplikatiivisia.
Esimerkki 2.1. (Vrt. [1, s. 33].) Olkoot m, n ∈ Z+ ja olkoon (m, n) = 1.
Tällöin
Nk(mn) = (mn)k =mknk =Nk(m)Nk(n) kaikillak ∈Z.
Lisäksi esimerkiksiNk(1) = 1kaikillak ∈Z. Täten Nk on multiplikatiivinen kaikilla k ∈Z.
Huomautus. Oletus (m, n) = 1 on sinällään tarpeeton edellisessä esimer- kissä, mutta koska tutkittiin funktion multiplikatiivisuutta, niin oletus lisät- tiin, jotta määritelmän mukaiset ehdot täyttyisivät. FunktioNk on esimerkki täydellisesti multiplikatiivisesta funktiosta, joita käsitellään myöhemmin.
Esimerkki 2.2. (Vrt. [1, s. 34].) Olkootmjan kuten edellisessä esimerkissä.
Jos m=n= 1, niin
δ(mn) = 1 =δ(m)δ(n), ja jos m 6= 1 tai n 6= 1, niin
δ(mn) = 0 =δ(m)δ(n).
Siis ykkösfunktio δ on multiplikatiivinen. Jälleen huomataan, että oletus (m, n) = 1 on sinällään tarpeeton.
2.2 Multiplikatiivisten funktioiden ominaisuuksia
Lause 2.1. Jos f on multiplikatiivinen funktio, niinf(1) = 1.
Todistus.(Vrt. [1, s. 34].) Olkoonf multiplikatiivinen funktio. Tällöin mää- ritelmän mukaan f ei ole identtisesti nolla eli on olemassa sellainen n ∈Z+, että f(n)6= 0. Koska f on multiplikatiivinen ja (1, m) = 1 kaikillam ∈ Z+, niin
f(n) =f(n1) =f(n)f(1).
Kun jaetaan yhtälö puolittain luvullaf(n), niin todetaan, ettäf(1) = 1.
Esimerkki 2.3. (Ks. [1, s. 34].) Jos f jag ovat multiplikatiivisia funktioita, niin lauseen 2.1 mukaan (f g)(1) = f(1)g(1) = 1. Siis f g ei ole identtisesti nolla. Jos m, n∈Z+ ja (m, n) = 1, niin
(f g)(mn) = f(mn)g(mn) =f(m)g(m)f(n)g(n) = (f g)(m)(f g)(n).
Täten siis myösf g on multiplikatiivinen. Jos oletetaan, ettäg(n)6= 0 kaikilla n ∈Z+, ja määritellään funktioiden f ja g osamäärä siten, että
(f
g)(n) = f(n) g(n),
niin voidaan todeta, että multiplikatiivisuus periytyy myös aritmeettisten funktioiden osamäärälle.
Kuten jo aiemmin mainittiin, multiplikatiivisten funktioiden ominaisuuksien tutkimista helpottaa nimenomaan multiplikatiivisuusominaisuus eli se, että
f(mn) = f(m)f(n) kaikillam, n∈Z+, joilla (m, n) = 1.
Tämän ominaisuuden ansiosta arvoon f(n) päästään luvun n alkulukuteki- jöiden kautta helpommin käsiksi kuin ei-multiplikatiivisilla funktioilla.
Huomautus. Merkintä
n =Y
p∈P
pn(p) =Y
p|n
pn(p)
tarkoittaa luvun n kanonista esitystä, missä siis luku n(p) on alkulukua p vastaava eksponentti luvun n kanonisessa esityksessä. Huomataan, että jos n = 1, niin n(p) = 0 kaikilla p ∈ P. Todetaan edelleen, että jos n = 1, niin jälkimmäisessä tulomuodossa kyseessä on tyhjä tulo, joka määritellään yhtäsuureksi kuin 1.
Lause 2.2. (Vrt. [7, s. 8].) Olkoon f aritmeettinen funktio. Tällöin f on multiplikatiivinen, jos ja vain jos f ei ole identtisesti nolla ja
f(n) =Y
p∈P
f(pn(p)) kaikilla n ∈Z+. (4)
Todistus. Olkoon f aritmeettinen funktio. Oletetaan, että f on multiplika- tiivinen. Olkoon n ∈ Z+. Koska (p, q) = 1 kaikilla alkuluvuilla p 6= q, niin täten
f(n) =f(Y
p∈P
pn(p)) =Y
p∈P
f(pn(p)).
Siis (4) on voimassa.
Oletetaan sitten, ettäf ei ole identtisesti nolla ja että yhtälö (4) on voimassa.
Olkoot m, n∈Z+ ja olkoon
m=Y
p∈P
pm(p)
luvun m kanoninen esitys. Oletetaan, että (m, n) = 1. Jos siisn(p)6= 0, niin m(p) = 0. Huomataan, että(mn)(p) =m(p) +n(p). Mutta koska(m, n) = 1, niin m(p) +n(p) =m(p) tai m(p) +n(p) = n(p). Täten
f(mn) = f(Y
p∈P
pmn(p)) =Y
p∈P
f(pm(p)+n(p)) = Y
p∈P
f(pm(p))Y
p∈P
f(pn(p)).
Nyt viimeisestä muodosta seuraa yhtälön (4) mukaan, että f(mn) =f(m)f(n).
Siis f on multiplikatiivinen.
Huomautus. Lauseen 2.1 perusteella yhtälö (4) lauseessa 2.2 voidaan esit- tää myös muodossa
f(n) = Y
p|n
f(pn(p)),
missä merkinnälläp|ntarkoitetaan nimenomaan luvunnalkulukutekijöitäp.
Sillä jos p-n, niinn(p) = 0 ja tällöinf(pn(p)) = 1ja täten kyseinen alkuluku
ei vaikuta yhtälön (4) tulolausekkeeseen. Jos siis p|n ainakin yhdellä p ∈P, niin
Y
p|n
f(pn(p)) =Y
p∈P
f(pn(p)).
Lisäksi jos n = 1, niin edellisen yhtälön vasen puoli on tyhjä tulo ja oikea puoli on lauseen 2.1 perusteella yhtäsuuri kuin 1. Siis edellinen yhtälö pitää paikkansa kaikilla n∈Z+.
Lause 2.2 on tärkeä tulos tutkittaessa multiplikatiivisten funktioiden ominai- suuksia. Multiplikatiivisen funktion arvot määräytyvät täysin sen alkuluku- jen potensseilla saamien arvojen mukaan.
Vaikka multiplikatiivisuusominaisuus f(mn) = f(m)f(n) edellyttää, että (m, n) = 1, voidaan tiettyjen hieman vastaavien ominaisuuksien osoittaa pitävän paikkansa luvuista m ja n riippumatta.
Esimerkki 2.4. (Vrt. tehtävä 1.9 McCarthyn teoksessa [7, s. 30].) Osoite- taan, että aritmeettinen funktio f, jolla f(1) = 1, on multiplikatiivinen, jos ja vain jos
f(m)f(n) =f((m, n))f([m, n]) kaikillam, n∈Z+. (5) (Missä siis [m, n]tarkoittaa lukujen m ja n pienintä yhteistä jaettavaa.) Ratkaisu. Todetaan alkuun, että jos m, n ∈ Z+ ja jos niiden kanoniset esitykset ovat
m=Y
p∈P
pm(p) ja n =Y
p∈P
pn(p),
niin vastaavasti lukujen (m, n)ja [m, n] kanoniset esitykset ovat (m, n) = Y
p∈P
p(m,n)(p) ja [m, n] =Y
p∈P
p[m,n](p),
missä
(m, n)(p) = min{m(p), n(p)}ja [m, n](p) = max{m(p), n(p)} kaikilla p∈P. Olkoon f aritmeettinen funktio siten, että f(1) = 1. Oletetaan, että f on multiplikatiivinen. Olkoot m, n∈Z+. Tällöin lauseen 2.2 mukaan
f(m)f(n) =Y
p∈P
f(pm(p))Y
p∈P
f(pn(p)) = Y
p∈P
f(pm(p))f(pn(p)).
Huomataan, että min{m(p), n(p)}=m(p), jos ja vain jos max{m(p), n(p)}=n(p) kaikillap∈P. Täten
f(m)f(n) = Y
p∈P
f(pmin{m(p),n(p)}
)f(pmax{m(p),n(p)}
)
= Y
p∈P
f(p(m,n)(p))f(p[m,n](p))
= Y
p∈P
f(p(m,n)(p))Y
p∈P
f(p[m,n](p))
= f((m, n))f([m, n]).
Siis yhtälö (5) on voimassa.
Oletetaan sitten, että yhtälö (5) on voimassa. Olkoot m, n ∈Z+ siten, että (m, n) = 1. Tällöin [m, n] =mn. Tästä ja oletuksesta f(1) = 1seuraa, että
f(m)f(n) =f((m, n))f([m, n]) =f(1)f(mn) =f(mn).
Siisf on multiplikatiivinen.
Esimerkki 2.5. (Vrt. tehtävä 1.10 McCarthyn teoksessa [7, s. 31].) Olkoon f aritmeettinen funktio siten, että f(1) 6= 0. Osoitetaan, ettäf on multipli- katiivinen, jos ja vain jos
f([m, n]
[d, e] ) =f(m d)f(n
e) (6)
kaikilla m, n ∈ Z+ ja kaikilla luvun m tekijöillä d sekä luvun n tekijöillä e, joilla (d, e) = (m, n).
Ratkaisu. Oletetaan, että f on multiplikatiivinen. Olkoot m, n∈Z+ ja ol- koond luvunm tekijä ja eluvun n tekijä siten, että(d, e) = (m, n). Huoma- taan, että tällöin
f([m, n]
[d, e] ) = f([m, n](m, n)
[d, e](d, e) ) =f(mn de ).
Tässä vaiheessa on hyvä todeta, että (d, e) = (m, n) ⇐⇒ Y
p∈P
pmin{d(p),e(p)}
=Y
p∈P
pmin{m(p),n(p)}
⇐⇒ min{d(p), e(p)}= min{m(p), n(p)} kaikillap∈P. Olkoon p mielivaltainen alkuluku. Osoitetaan, että jos min{m(p), n(p)} = m(p), niin m(p) =d(p). Olkoon min{m(p), n(p)}= m(p). Tällöin oletuksen
(d, e) = (m, n) mukaan myös min{d(p), e(p)} = m(p) ja oletuksen d|m mu- kaand(p)≤m(p). Siisd(p)≤min{d(p), e(p)}, missä selvästikin yhtäsuuruus on ainoa mahdollinen vaihtoehto. Siis d(p) = min{d(p), e(p)} = m(p). Vas- taavasti voidaan osoittaa, että jos min{m(p), n(p)}=n(p), niinn(p) = e(p).
Kun siis m(p) ≤ n(p), niin m(p)− d(p) = 0. Ja kun n(p) ≤ m(p), niin n(p)−e(p) = 0. Koska jompi kumpi ehdoista m(p) ≤ n(p) ja n(p) ≤ m(p) on varmasti voimassa ja koska m(p)−d(p) ≥ 0 ja n(p)− e(p) ≥ 0, niin min{m(p)−d(p), n(p)−e(p)}= 0.
Edellisen tarkastelun perusteella voidaan todeta, että (m
d ,n
e) = Y
p∈P
pmin{m(p)−d(p),n(p)−e(p)}
=Y
p∈P
p0 = 1.
Koska f on multiplikatiivinen, niin f([m, n]
[d, e] ) =f(mn
de ) = f(m d · n
e) = f(m d)f(n
e).
Oletetaan sitten, että väitteen jälkimmäinen puolisko pitää paikkansa ja ol- kootm, n∈Z+ siten, että(m, n) = 1. Tällöin yhtälö (6) on voimassa kaikilla d|m jae|n, joilla (d, e) = (m, n) = 1. Erityisesti yhtälö (6) on voimassa, kun d=e= 1. Koska(m, n) = 1, niin [m, n] =mn. Täten
f(m)f(n) = f(m 1)f(n
1) = f([m, n]
[1,1]) = f([m, n]) =f(mn).
Koska lisäksi oletuksen mukaanf(1)6= 0, niinf ei ole identtisesti nolla. Siisf
on multiplikatiivinen.
2.2.1 Käänteisfunktion multiplikatiivisuus
Todetaan, että lauseen 1.3 mukaan lauseesta 2.1 seuraa, että jokainen mul- tiplikatiivinen funktio on kääntyvä Dirichlet’n konvoluution suhteen.
Huomautus. Lauseen 2.1 perusteella sivulla 8 esitetty käänteisfunktion kaa- va on hieman yksinkertaisempi multiplikatiivisilla funktioilla. Jos f on mul- tiplikatiivinen, niin
f−1(1) = 1 ja f−1(n) =−X
d|n d>1
f(d)f−1(n
d) kaikillan ∈Z+. Kaavasta seuraa välittömästi, että jos p∈P, niin f−1(p) =−f(p).
Kuten multiplikatiivisten funktioiden tulolle ja osamäärälle, multiplikatiivi- suus on periytyvä ominaisuus myös sen käänteisfunktiolle Dirichlet’n konvo- luution suhteen.
Lause 2.3. (Ks. [7, s. 8].) Jos aritmeettinen funktiof on multiplikatiivinen, niin f−1 on myös multiplikatiivinen.
Todistus.Sivuutetaan. Todistus löytyy esimerkiksi McCarthyn teoksesta [7, s. 8].
Esimerkki 2.6. (Vrt. tehtävä 1.13 McCarthyn teoksessa [7, s. 31].) Olkoon f multiplikatiivinen funktio ja n ∈ Z+. Osoitetaan, että jos m|n, m > 1 ja (m,mn) = 1, niin
X
d|m
f(d)f−1(n d) = 0.
Ratkaisu. Oletetaan, että m|n, m > 1 ja (m,mn) = 1. Koska m|n, on ole- massa k ∈ Z+ siten, että n = mk eli k = mn. Tällöin (m, k) = 1 ja edelleen (md, k) = 1 kaikillad|m. Täten
X
d|m
f(d)f−1(n
d) = X
d|m
f(d)f−1(mk
d ) = X
d|m
f(d)f−1(m dk).
Lauseen 2.3 mukaan f−1 on multiplikatiivinen ja täten f−1(m
dk) = f−1(m
d)f−1(k) kaikilla d|m. Siis
X
d|m
f(d)f−1(n
d) = X
d|m
f(d)f−1(m
d)f−1(k)
= f−1(k)X
d|m
f(d)f−1(m d)
= f−1(k)(f∗f−1)(m)
= f−1(k)δ(m).
Koska oletuksen mukaanm >1, niinδ(m) = 0. Siis väite pitää paikkansa.
2.2.2 Möbiuksen funktion multiplikatiivisuus
Koska esimerkin 2.1 mukaan funktio Nk on multiplikatiivinen kaikillak∈Z, niin erityisesti se on multiplikatiivinen silloin, kun k= 0. Siis zeta-funktio on multiplikatiivinen. Koska Möbiuksen funktio määriteltiin siten, ettäµ=ζ−1, niin lauseen 2.3 mukaan µ on multiplikatiivinen [7, s. 9]. Sivuilla 9 ja 10 todetaan, että µ(1) = 1 ja
µ(pα) =
−1, jos α= 1 0, jos α >1, kun p∈Pja α ∈Z+. Täten lauseen 2.2 mukaan
µ(n) =
1, jos n = 1
(−1)t, jos n ont:n erisuuren alkuluvun tulo 0 muulloin.
McCarthyn teoksessa [7, s. 10] µmääritellään kuten edellä ζ-funktion kaut- ta. Funktion µ merkittävyyttä kuvastaa se, että useissa teksteissä (vrt. esi- merkiksi [1, s. 24] tai [2, s. 31]) sen arvot määritellään suoraan. Esitetään seuraavaksi hieman esimerkkejä funktion µominaisuuksista.
Esimerkki 2.7. Olkoon funktiof multiplikatiivinen. Tarkastellaan funktion µf arvoja. Esimerkin 2.3 mukaanµf on multiplikatiivinen. Edellä esitettyjen funktion µarvojen perusteella
(µf)(n) =
1, jos n = 1
(−1)tf(p1)· · ·f(pt), jos n on t:n erisuuren alkuluvun tulo
0 muulloin.
Esimerkki 2.8. (Vrt. tehtävä 1.8 McCarthyn teoksessa [7, s. 30].) Osoite- taan, että jos f on multiplikatiivinen, niin
(µf ∗ζ)(n) = X
d|n
µ(d)f(d) = Y
p|n
(1−f(p)) kaikilla n∈Z+.
Ratkaisu. Selvästi
(µf ∗ζ)(n) =X
d|n
µ(d)f(d)
kaikilla n ∈Z+ ja kaikilla aritmeettisilla funktioilla f. Olkoon f multiplika- tiivinen. Jos n= 1, niin
X
d|n
µ(d)f(d) = µ(1)f(1) = 1 = Y
p|n
(1−f(p)).
Osoitetaan sitten, että väite pätee, kunn >1, soveltamalla induktiota luvun n alkulukutekijöiden lukumäärän suhteen. Olkoonn=pα. Nyt esimerkin 2.7 mukaan
X
d|pα
µ(d)f(d) = µ(1)f(1) +µ(p)f(p) = 1−f(p) = Y
p|pα
(1−f(p)). Olkoon pi ∈ P ja ai ∈ Z+ kaikilla i ∈ Z+. Oletetaan, että väite pätee, kun n =pa11· · ·pakk, missä k ∈Z+. Olkoon n=pa11· · ·pakkqa, missä q ∈P, a∈ Z+
ja q 6= pi kaikilla i ∈ {1, . . . , k}. Huomataan, että jos d|qna, niin (d, q) = 1.
Täten
Y
p|n
(1−f(p)) = (1−f(q)) Y
p|pa11···pakk
(1−f(p))
= (1 +µ(q)f(q))X
d|qan
µ(d)f(d)
= X
d|qan
µ(d)f(d) +X
d|qan
µ(qd)f(qd).
Viimeisen rivin ensimmäisessä summalausekkeessa kaikki tekijät dovat muo- toa d = pb11· · ·pbkk ja jälkimmäinen voidaan kirjoittaa esimerkin 2.7 mukaan uudestaan muodossa
X
d|qan
µ(qd)f(qd) +µ(q2d)f(q2d) +· · ·+µ(qad)f(qad) = X
d|qan 0<c≤a
µ(dqc)f(dqc).
Täten
Y
p|n
(1−f(p)) = X
d|n
qa
c=0
µ(dqc)f(dqc) + X
d|n
qa
0<c≤a
µ(dqc)f(dqc)
= X
d|qan 0≤c≤a
µ(dqc)f(dqc).
Merkitään dqc=e, missä d|qna ja0≤c≤a. Huomataan, että lukue käy läpi kaikki luvun n tekijät ja näin ollen
Y
p|n
(1−f(p)) =X
e|n
µ(e)f(e).
Täten induktioperiaatteen mukaan alkuperäinen väite seuraa.
Jos nyt edellisessä esimerkissäf =µ, niin päädytään mielenkiintoiseen iden- titeettiin
X
d|n
µ2(d) = Y
p|n
(1−µ(p)) = Y
p|n
2 = 2t, missä t on luvunn alkulukutekijöiden lukumäärä.
Möbiuksen funktioµtulee olemaan myös jatkossa erittäin tärkeä väline. Var- sinkin kun tutkitaan täydellisesti multiplikatiivisten funktioiden ja totient- tien ominaisuuksia.
2.2.3 Dirichlet’n konvoluution multiplikatiivisuus
Lause 2.4. (Ks. [1, s. 35].) Jos f ja g ovat multiplikatiivisia funktioita, niin f ∗g on myös multiplikatiivinen.
Todistus. Sivuutetaan. Todistus löytyy esimerkiksi Apostolin teoksesta [1, s. 35].
Huomautus. Lauseesta 2.4 seuraa välittömästi, että josg1, . . . , gk ovat mul- tiplikatiivisia funktioita, niin f =g1∗ · · · ∗gk on multiplikatiivinen funktio.
Huomautus. Esimerkin 2.8 tulos olisi erittäin helppo todistaa käyttämällä hyväksi lausetta 2.4. (Vrt. [1, s. 37].)
Nyt lauseista 2.3 ja 2.4 saadaan välittömästi seuraava tulos.
Lause 2.5. (Ks. [1, s. 35].) Jos funktiot g ja f∗g ovat multiplikatiivisia, niin myös f on multiplikatiivinen.
Todistus. Koska g on multiplikatiivinen, niin lauseen 2.3 mukaan myös g−1 on multiplikatiivinen. Ja koska f ∗g on multiplikatiivinen, niin assosiatiivi- suuden ja lauseen 2.4 mukaan
(f ∗g)∗g−1 =f ∗δ=f
on multiplikatiivinen.
Esimerkki 2.9. (Vrt. [7, s. 10].) Kuten esimerkissä 1.4 todettiin, niin σk= Nk∗ζ. Täten lauseen 2.4 mukaanσk on multiplikatiivinen. Olkootk, α∈Z+ ja olkoon p∈P. Tällöin
σk(pα) = X
d|pα
dk=
α
X
j=0
(pj)k=
α
X
j=0
(pk)j.
Nyt kun sovelletaan viimeiseen summalausekkeeseen geometrisen summan kaavaa, niin todetaan, että
σk(pα) = p(α+1)k−1 pk−1 . Täten funktion σk multiplikatiivisuuden perusteella
σk(n) =Y
p|n
p(n(p)+1)k−1
pk−1 kaikillan ∈Z+. Lisäksi todetaan, että
σ0(pα) =τ(pα) = X
d|pα
1 = α+ 1 ja täten multiplikatiivisuuden perusteella
σ0(n) =Y
p|n
(n(p) + 1) kaikillan ∈Z+.
Lause 2.6. Jos f ja g ovat multiplikatiivisia funktioita, niin (f ∗µg)(n) = Y
p|n
f(pn(p))−f(pn(p)−1)g(p)
kaikilla n∈Z+.
Todistus. Olkoot f ja g multiplikatiivisia funktioita ja olkoon n ∈ Z+. Esimerkin 2.3 ja lauseen 2.4 mukaan f ∗ µg on multiplikatiivinen. Täten lauseen 2.2 perusteella
(f ∗µg)(n) =Y
p|n
(f∗µg)(pn(p)).
Tarkastellaan sitten lauseketta (f∗µg)(pn(p)). Olkoon n(p)≥1. Tällöin esi- merkistä 2.7 seuraa, että
(f ∗µg)(pn(p)) = X
d|pn(p)
f(d)µg(pn(p)
d ) = f(pn(p))−f(pn(p)−1)g(p).
Täten
(f ∗µg)(n) =Y
p|n
f(pn(p))−f(pn(p)−1)g(p)
, josn >1.
Jos n= 1, niin edellisen yhtälön oikea puoli on tyhjä tulo eli yhtäsuuri kuin 1 ja lauseen 2.1 mukaan (f∗µg)(1) = 1. Siis
(f∗µg)(n) = Y
p|n
f(pn(p))−f(pn(p)−1)g(p)
kaikillan ∈Z+.
Huomataan, että esimerkki 2.8 on erikoistapaus lauseesta 2.6, josta saadaan myös muita mielenkiintoisia erikoistapauksia.
Esimerkki 2.10. Olkoon g multiplikatiivinen funktio ja f(n) =X
d|n
g(d) kaikillan ∈Z+.
Siisf =g∗ζ. Tällöin, koskag jaζ ovat multiplikatiivisia, lauseen 2.4 mukaan myös f on multiplikatiivinen. Nyt käyttämällä Möbiuksen käänteiskaavaa todetaan, että g =f∗µ=f ∗µζ. Jos siis g on multiplikatiivinen ja
f(n) =X
d|n
g(d) kaikillan ∈Z+,
niin Möbiuksen käänteiskaavan ja edelleen lauseen 2.6 mukaan g(n) = Y
p|n
f(pn(p))−f(pn(p)−1)
kaikilla n∈Z+.
Esimerkki 2.11. (Vrt. tehtävä 25. Apostolin teoksessa [1, s. 49].) Olkoon f multiplikatiivinen. Osoitetaan, että
a) f−1(n) = µ(n)f(n) = (µf)(n)kaikilla neliövapailla n ∈Z+ ja b) f−1(p2) =f(p)2−f(p2) kaikillap∈P.
Ratkaisu.
a) Olkoon f multiplikatiivinen. Josn= 1, niin
(µf ∗f)(1) =µ(1)f(1)f(1) = 1.
Oletetaan, että n ∈ Z+ on neliövapaa ja n > 1. Tällöin p|n jollain p∈P. Koskaf on multiplikatiivinen, niin lauseen 2.6 mukaan
(f ∗µf)(n) = Y
p|n
(f(pn(p))−f(pn(p)−1)f(p)).
Koska n on neliövapaa, niin n(p) = 1 kaikillap|n. Täten (f ∗µf)(n) =Y
p|n
(f(p)−f(1)f(p)) =Y
p|n
(f(p)−f(p)) = 0.
Siis (µf ∗ f)(n) = δ(n) kaikilla neliövapailla n ∈ Z+ ja näin ollen f−1(n) = µ(n)f(n) kaikilla neliövapailla n∈Z+.
b) Olkoon f multiplikatiivinen ja p∈P. Nyt f−1(p2) = −X
d|p2 d>1
f(d)f−1(p2 d)
= −(f(p)f−1(p) +f(p2)f−1(1)).
Huomataan, että f−1(p) = −f(p). Täten
f−1(p2) = −(−f(p)f(p) +f(p2))
= f(p)2−f(p2).
Huomautus. Esimerkin 2.11 a)-kohdan tulos on itse asiassa voimassa kai- killa n∈Z+, joilla n(p) = 1 ainakin yhdellä alkuluvulla p|n.
2.2.4 Eulerin funktion multiplikatiivisuus
Koska esimerkin 1.9 mukaan φ = N ∗µ, niin Eulerin funktio on myös eri- koistapaus lauseesta 2.6. Nyt saadaan viimein määritettyä yleinen lauseke funktion φ arvoille.
Esimerkki 2.12. (Vrt. [7, s. 11].) Lauseen 2.6 mukaan φ(n) = Y
p|n
N(pn(p))−N(pn(p)−1)
= Y
p|n
pn(p)−pn(p)−1
= Y
p|n
pn(p)(1− 1 p)
= nY
p|n
1− 1
p
kaikilla n∈Z+.
Huomautus. Funktion φ arvot voitaisiin määrittää myös käyttämättä lausetta 2.6. Koska φ = N ∗µ, niin lauseen 2.4 mukaan φ on multiplika- tiivinen. Täten arvot saataisiin määritettyä helposti, kun muistetaan (ks.
esimerkki 1.9), että
φ(pα) =pα
1− 1 p
.
Eulerin funktio toteuttaa lukuisia identiteettejä.
Esimerkki 2.13. (Vrt. [1, s. 28] ja [8, s. 228].) Olkoot m, n ∈ Z+. Eulerin funktio φ toteuttaa seuraavat identiteetit.
a) Eulerin funktion arvo φ(mn) = φ(m)φ(n)φ(d)d , missä d= (m, n).
b) Jos m|n, niinφ(m)|φ(n).
c) Eulerin funktion arvoφ(n)on parillinen, kunn ≥3. Lisäksi jos luvulla n onr erillistä paritonta alkulukutekijää, niin 2r|φ(n).
d) Eulerin funktion arvo φ(nk) =nk−1φ(n) kaikillak ∈Z+
Esimerkin 2.13 kohdat (a),(b) ja (d) todistetaan yleisen totientin tapauksessa luvussa 3 (katso lause 3.12 ja seurauslause 3.4 sekä lause 3.2) ja kohdan (c) todistus löytyy esimerkiksi Apostolin teoksesta [1, s. 28].
Esimerkki 2.14. (Vrt. luvun 7.1 tehtävä 26 Rosenin teoksessa5[8, s. 229].) Osoitetaan, että jos kokonaisluku n >6, niin φ(n)≥√
n.
Ratkaisu. Olkoon n ∈ Z+. Oletetaan, että n > 6. Todetaan alkuun, että
√1 = 1 =φ(1). Todetaan lisäksi, että
n≥4⇐⇒ n
4 ≥1⇐⇒ n2
4 ≥n ⇐⇒ n 2 ≥√
n. (7)
Olkoon p∈Pja α∈Z+. Josn =pα >6, niin luonnollisesti pα≥4 ja tällöin tuloksen (7) perusteella
√pα ≤ pα 2 = 1
2pα ≤pα(1− 1
p) =φ(pα). (8) Olkoon
n=Y
p∈P
pn(p),
5Rosenin teoksen alkuperäisessä tehtävässä väitetään, että√
n≤φ(n)kaikillan∈Z+. Voidaan kuitenkin todeta, että √
2>1 =φ(2)jap
(6)>2 =φ(6).
missä kaikille p ∈ P pätee, että n(p) = 0 tai pn(p) ≥ 4. Jos n(p) = 0, niin ppn(p) = 1 =φ(pn(p)). Täten multiplikatiivisuuden ja tuloksen (8) perusteel-
la √
n= sY
p∈P
pn(p)=Y
p∈P
ppn(p)≤Y
p∈P
φ(pn(p)) =φ(n). (9) Huomataan, että jos n(p)6= 0, niinpn(p)≥4 kaikillap≥5. Täten siis edelli- nen tulos on voimassa kaikilla n, joilla n(2) 6= 1jan(3)6= 1. Tarkasteltavaksi jää siis tapaukset, joissa n(2) = 1, sekä tapaukset, joissa n(3) = 1.
1) Olkoot n(2) = 1 ja n(3) = 0. Jos nyt p|n ja p 6= 2, niin p ≥ 5. Kun n ≥ 4, niin tuloksen (7) mukaan √
2n ≤ √n
2. Olkoon p ≥ 5. Tällöin tietysti myös pα ≥4 ja näin ollen
p2pα ≤ pα
√2 < 4
5pα ≤pα(1−1
p) =pα(1−1
p)2(1− 1
2) = φ(2pα). (10) Koska n >6, niin luku n voidaan kirjoittaa nyt muodossa
n = 2qn(q)m= 2qn(q)Y
p∈P
pm(p),
missä q ∈ P, n(q) ≥ 1, q ≥ 5 ja m(2) = m(3) = m(q) = 0. Nyt m täyttää tuloksen (9) ehdot. Siis √
m ≤ φ(m) ja tuloksen (10) mukaan p2qn(q) ≤φ(2qn(q)). Täten multiplikatiivisuuden perusteella
√n =p
2qn(q)√
m≤φ(2qn(q))φ(m) = φ(n). (11) 2) Olkootn(2) = 1ja n(3) =a≥2. Huomataan, että
√
2·3a=√ 2√
3a <2√
3a = 2·3a2. (12) Koska
a≥2⇐⇒2a−a≥2⇐⇒2a−2≥a⇐⇒a−1≥ a 2, niin tuloksen (12) mukaan
√2·3a<2·3a−1 = 3a·2
3 = 3a(1−1
3) = φ(3a) = φ(2)φ(3a) =φ(2·3a).
Koska n >6, niin luku n voidaan kirjoittaa nyt muodossa n = 2·3αm= 2·3αY
p∈P
pm(p),
missä a≥2 jam(2) =m(3) = 0. Huomataan, että m täyttää tuloksen (9) ehdot ja tällöin edellä esitetyn sekä multiplikatiivisuuden perusteella
√n =√
2·3am =√
2·3a√
m ≤φ(2·3a)φ(m) = φ(n). (13) 3) Olkoot n(3) = 1 ja n(2) 6= 1. Todetaan, että √
3 < 2 = φ(3). Koska n >6, niin luku n voidaan kirjoittaa nyt muodossa
n= 3m= 3Y
p∈P
pm(p),
missä m(3) = 0, m(2) 6= 1 ja m(p)≥ 1 ainakin yhdellä p∈P. Tällöin m täyttää tuloksen (9) ehdot ja täten multiplikatiivisuuden perusteella
√n =√
3m=√ 3√
m≤φ(3)φ(m) = φ(n). (14) 4) Olkoot n(2) = n(3) = 1. Koska n > 6, niin luku n voidaan kirjoittaa
nyt muodossa
n = 2·3m= 2·3Y
p∈P
pm(p),
missä m(2) =m(3) = 0jam(p)≥1ainakin yhdelläp∈P. Täten luku 2m täyttää tuloksen (11) ehdot ja näin ollen √
2m ≤φ(2m). Edelleen multiplikatiivisuuden ja edellisen kohdan mukaan mukaan
√n=√ 3√
2m ≤φ(3)φ(2m) =φ(n). (15) Tuloksista (9), (11), (13), (14) ja (15) seuraa, että väite pitää paikkansa kaikil- lan >6. (Tosiasiassa todistuksessa todetaan myös, että väite pitää paikkan-
sa, kunn= 1,n= 3,n= 4jan= 5.)
Määritelmä 2.2. (Kts. [2, s. 41].) Olkoot k, n ∈ Z+. Jordanin6 funktio Jk määritellään kaavalla
Jk(n) = |{(a1, . . . , ak) : 1≤a1, . . . , ak ≤n,syt(a1, . . . , ak, n) = 1}|.
Huomautus. Todetaan, että J1 =φ.
Lause 2.7. (Ks. [2, s. 41].) Jordanin funktio toteuttaa kaavan Jk=Nk∗µ.
6Marie Ennemond Camille Jordan (1838-1922) oli ranskalainen matemaatikko [12].
Todistus.(Todistuksen rakenne noudattelee Pentti Haukkasen monisteessa [2, s. 41] esitettyä tapauksen k = 1 todistusta.) Olkoot k, n ∈ Z+. Jordanin funktion määritelmästä seuraa, että
Jk(n) =
n
X
a1=1 n
X
a2=1
· · ·
n
X
ak=1
δ(syt(a1, . . . , ak, n)).
Koska µ∗ζ =δ, yhtälö voidaan kirjoittaa uudestaan muodossa Jk(n) =
n
X
a1=1 n
X
a2=1
· · ·
n
X
ak=1
X
d|syt(a1,...,ak,n)
µ(d).
Nyt d|syt(a1, . . . , ak, n), jos ja vain jos d|syt(a1, . . . , ak−1, n) ja d|ak. Täten kahden viimeisen summalausekkeen summausjärjestys voidaan vaihtaa siten, että
Jk(n) =
n
X
a1=1 n
X
a2=1
· · ·
n
X
ak−1=1
X
d|syt(a1,...,ak−1,n)
µ(d)
n
X
ak=1 d|ak
1. (16)
Olkoot m, a ∈ Z+ ja olkoon 1 ≤ a ≤ m. Oletetaan, että d|m eli m = bd, missä b ∈Z+. Tällöin
m
X
a=1 d|a
1 =|{1d,2d, . . . , bd}|=b = m d .
Täten yhtälö (16) saadaan muotoon Jk(n) =
n
X
a1=1 n
X
a2=1
· · ·
n
X
ak−1=1
X
d|syt(a1,...,ak−1,n)
µ(d)n d.
Taas voidaan todeta, että d|syt(a1, . . . , ak−1, n), jos ja vain jos d|syt(a1, . . . , ak−2, n) ja d|ak−1. Kahden viimeisen summalausekkeen summausjärjestys voidaan siis vaihtaa kuten aiemmin ja näin todetaan, että
Jk(n) =
n
X
a1=1 n
X
a2=1
· · ·
n
X
ak−2=1
X
d|syt(a1,...,ak−2,n)
µ(d)n d
n
X
ak−1=1 d|ak−1
1
=
n
X
a1=1 n
X
a2=1
· · ·
n
X
ak−2=1
X
d|syt(a1,...,ak−2,n)
µ(d)n d
2
.
Jatkaen kuten edellä yhtälö saadaan lopulta muotoon Jk(n) =
n
X
a1=1
X
d|(a1,n)
µ(d)n d
k−1
= X
d|n
µ(d)n d
k−1 Xn
a1=1 d|a1
1
= X
d|n
µ(d)n d
k
= (µ∗Nk)(n).
Nytµ∗Nk =Nk∗µja näin ollen väite on todistettu.
Täten siis Jk on multiplikatiivinen funktio kaikilla k ∈Z+. Seuraus 2.1. (Vrt. [7, s. 13-14].) Olkoon k∈Z+. Tällöin
Jk(n) = nkY
p|n
1− 1
pk
kaikilla n ∈Z+.
Todistus. Olkoon k ∈ Z+. Nyt lauseen 2.7 mukaan Jk = Nk∗µ ja täten lauseen 2.6 mukaan
Jk(n) = Y
p|n
Nk(pn(p))−Nk(pn(p)−1)
= Y
p|n
pn(p)k−p(n(p)−1)k
= Y
p|n
pn(p)k(1− 1 pk)
= nkY
p|n
1− 1
pk
kaikillan∈Z+.
Jordanin funktio, kuten Eulerin funktio, toteuttaa lukuisia identiteettejä, joihin päästää helposti käsiksi käyttämällä lausetta 2.7. Voidaan esimerkiksi todeta, että koska Jk = Nk ∗µ, niin Möbiuksen käänteiskaavan mukaan Nk =Jk∗ζ. Eli
nk =X
d|n
Jk(d).
