33  Primitiivi­juurten olemassa­olon todistus

33.1 Johdanto

Tässä tekstissä todistetaan, että jokaisella alku­luvulla $p$ on olemassa primitiivi­juuri modulo $p$. Aloitamme parin työkalun esittelyllä ennen kuin pääsemme varsinaisen todistuksen kimppuun.

Todistus on vaikea. Lopussa olevat tehtävät tukevat ideoiden ymmärtämistä. Niitä kannattaa tehdä samalla, kun yrittää sisäistää todistuksen ideoita.

33.2 Lagrangen lause

Todistus tulee hyödyntämään seuraavaa tulosta.

Tilanne on siis sama kuin tavallisessa modulottomassa tapauksessa: polynomilla on enintään asteensa verran nolla­kohtia. Tulos ei siis ole kovin epäintuitiivinen. Huomaa kuitenkin, että ratkaisuja voi olla alle asteen verran. Esimerkiksi yhtälöllä $x^2 + 1 \equiv 0 \pmod{3}$ ei ole yhtäkään ratkaisua.

”Tavallisilla luvuilla” vastaavan väitteen voi todistaa käyttämällä polynomien jako­yhtälöä: Jos astetta $n$ olevalla polynomilla $P(x)$ on nolla­kohta $\alpha$, niin voidaan kirjoittaa $P(x) = (x - \alpha)Q(x)$ jollain polynomilla $Q(x)$. Täten jos polynomilla $P$ olisi vähintään $n+1$ nolla­kohtaa $\alpha_1, \ldots , \alpha_{n+1}$, voitaisiin kirjoittaa $$P(x) = (x - \alpha_1)(x - \alpha_2) \cdots (x - \alpha_n)(x - \alpha_{n+1})R(x)$$ jollain polynomilla $R(x)$. Oikean puolen aste on vähintään $n+1$ (koska $R$ ei ole nolla­polynomi), kun taas vasemman puolen aste on $n$. Tämä ei käy.

Sama todistus toimii myös kokonais­luvuilla modulo $p$. Ainoa epävarma tekijä on, toimiiko polynomien jako­yhtälö. Kuitenkin käymällä läpi polynomien jako­yhtälön todistuksen vaiheet huomataan, että kaikki vaiheista voidaan tehdä myös modulo $p$. Tämä todistaa väitteen. (Yksityis­kohdat sivuutetaan.)

33.4 Eräs fii-funktion ominaisuus

Fii-funktiosta voisi sanoa paljonkin, mutta tarvitsemme vain pari ominaisuutta. Ensimmäinen on helppo.

Todistus: Voidaan valita $x = 1$: tällöin $1 \le x \le n$ ja $\text{syt}(x, n) = 1$.

Sitten vaikeampi ominaisuus.

Siis esimerkiksi tapauksessa $n = 12$ lause väittää, että $$\phi(1) + \phi(2) + \phi(3) + \phi(4) + \phi(6) + \phi(12) = 12.$$ Tämä tapaus on helppo tarkistaa laskemalla.

Todistus. Kuinka monta on niitä kokonais­lukuja $x$, joilla $1 \le x \le n$? Vastaus on tietysti $n$.

Määrän voi kuitenkin laskea toisellakin tavalla. Ideana on laskea kullekin positiiviselle kokonais­luvulle $m$, monellako kokonais­luvulla $x$ pätee $1 \le x \le n$ ja $\text{syt}(x, n) = m$. Kun summataan nämä määrät kaikilla $m$, tulee vastaukseksi $n$.

Montako näitä lukuja sitten on? Jos $m$ ei jaa lukua $n$, niin vastaus on tietysti nolla. Kysymys on siis kiinnostava vain jos $m \mid n$. Tapauksessa $m = 1$ määrä on määritelmän nojalla $\phi(n)$. Käy niin, että määrä voidaan muissakin tapauksissa esittää fii-funktion avulla.

Jotta voi olla $\text{syt}(x, n) = m$, tulee lukujen $x$ ja $n$ olla jaollisia luvulla $m$. Kirjoitetaan siis $x = my$ ja $n = mk$. Nyt $$\text{syt}(x, n) = \text{syt}(my, mk) = m \cdot \text{syt}(y, k).$$ Tulee siis päteä $\text{syt}(y, k) = 1$.

Huomataan, että kun $x$ käy läpi luvulla $m$ jaolliset luvut välillä $1 \le x \le n$, luku $y$ käy läpi kaikki luvut välillä $1 \le y \le n/m = k$. Täten niitä lukuja $1 \le y \le k$, joilla $\text{syt}(y, k) = 1$, on määritelmän nojalla $\phi(k)$.

Eli ehdot $1 \le x \le n, \text{syt}(x, n) = m$ toteuttavia $x$ on $\phi(n/m)$ (kun $m \mid n$), joten yhteensä lukuja $1 \le x \le n$ on toisaalta $$\sum_{m \mid n} \phi(n/m)$$ ja toisaalta $n$. Enää pitää huomata, että kun $m$ käy läpi luvun $n$ tekijät, niin myös $m/n$ käy läpi luvun $n$ tekijät. Jos vaikka $n = 12$ ja $m$ käy tekijät läpi järjestyksessä $$1, 2, 3, 4, 6, 12,$$ niin $n/m$ käy tekijät läpi järjestyksessä $$12, 6, 4, 3, 2, 1.$$ Täten $$\sum_{m \mid n} \phi(m) = n.$$

33.6 Tehtäviä

Ensimmäisissä tehtävissä tutustutaan tarkemmin fii-funktion ominaisuuksiin, ja viimeiset tehtävät ovat soveltavampia.

Tehtävä 1.

1. Osoita, että jos $p$ on alku­luku, niin $\phi(p) = p-1$.
2. Osoita, että jos $p$ on alku­luku ja $k$ on positiivinen kokonais­luku, niin $\phi(p^k) = p^k - p^{k-1}$.

Tehtävä 2. Todista tehtävän 1 avulla, että jos $n = p^k$ on jonkin alku­luvun potenssi, niin $$\sum_{d \mid n} \phi(d) = n.$$

Tehtävä 3. Tämän tehtävän tavoite on osoittaa, että jos $\text{syt}(n, m) = 1$, niin $\phi(nm) = \phi(n)\phi(m)$.

1. Olkoon $1 \le x \le mn$ kokonais­luku, ja olkoot $1 \le y \le m$ ja $1 \le z \le n$ luvun $x$ jako­jäännökset luvuilla $m$ ja $n$ jaettaessa. Osoita, että $\text{syt}(x, mn) = 1$, jos ja vain jos $\text{syt}(y, m) = 1$ ja $\text{syt}(z, n) = 1$.
2. Viimeistele todistus kiinalaisella jäännös­lauseella.

Tehtävä 4. Laske $\phi(360)$.

Tehtävä 5. Olkoon $m > 1$ kokonais­luku, joka ei ole alku­luku. Osoita, että on olemassa polynomi $P(x)$, jonka kertoimet ovat kokonais­lukuja ja jonka kaikki kertoimet eivät ole jaollisia $m$:llä ja jolla yhtälöllä $P(x) \equiv 0 \pmod{m}$ on yli $P$:n asteen verran ratkaisuja.

Tehtävä 6. Olkoon $p$ alku­luku. Osoita, että $$1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-1) \equiv -1 \pmod{p}.$$

Tehtävä 7. Olkoon $p$ alku­luku, jolla $p \equiv 3 \pmod{4}$. Oletetaan, että $x$ ja $y$ ovat kokonais­lukuja, joilla $x^2 + y^2 \equiv 0 \pmod{p}$. Osoita, että $x \equiv 0 \pmod{p}$ ja $y \equiv 0 \pmod{p}$.

Tehtävä 8. (Eulerin lause) Olkoon $m$ positiivinen kokonais­luku ja olkoon $a$ kokonais­luku, jolla $\text{syt}(a, m) = 1$. Osoita, että $a^{\phi(m)} = 1 \pmod{m}$.