7  Kongruenssit

Tekijä

Olli Järviniemi

7.1 Johdanto

Kongruenssit ovat kätevä tapa puhua jaollisuuksista ja jako­jäännöksistä. Alla esitetään kongruenssien idea, käydään läpi esimerkki­tehtäviä ja päätetään harjoitus­tehtävillä.

7.2 Kongruenssien idea

Lähdetään liikkeelle seuraavasta tehtävästä. Tehtävä

Tehtävä 7.1 Liitu­taululla on kaksi positiivista kokonais­lukua. Ensimmäisen viimeinen numero on 22 ja toisen 33. Mikä on niiden summan viimeinen numero?

Vaikkei luvuista tiedetä mitään muuta kuin niiden viimeiset numerot, niin voidaan sanoa, että vastaus on 2+3=52 + 3 = 5. Summassa ykkösten paikalla oleviin numeroihin vaikuttaa nimittäin vain summattavien ykkösten paikalla olevat numerot, kuten näkee esimerkiksi allekkain yhteen­laskusta:

Allekkain laskettu yhteenlasku, jossa lukujen kaikki muut numerot ovat kysymysmerkkejä paitsi viimeiset. Ylemmän luvun viimeinen numero on 2 ja alemman 3, ja summaviivan alla olevan tuloksen viimeinen numero on 5.

Kuva 1. Summan viimeinen numero on viimeisten numeroiden summa.

Oli kysymys­merkkien paikalla mitä numeroita tahansa, summan viimeinen numero on 55.

Huomataan, että myös tulolla on sama ominaisuus: jos kahdesta luvusta toisen viimeinen numero on 22 ja toisen 33, on tulon viimeinen numero 2⋅3=62 \cdot 3 = 6. Tämän näkee tutkimalla allekkain kerto­laskua:

Allekkain laskettu kertolasku, jossa kerrottavien muut numerot ovat kysymysmerkkejä. Ylemmän luvun viimeinen numero on 2 ja alemman 3. Osatulojen numerot ovat kysymysmerkkejä lukuun ottamatta viimeisiä numeroita, ja lopullisen tuloksen viimeinen numero on 6.

Kuva 1. Tulon viimeinen numero on kerrottavien viimeisten numeroiden tulo.

Oli kysymys­merkkien paikalla mitä numeroita tahansa, tulon viimeinen numero on 66.

Tietysti nämä samat ominaisuudet pätevät edelleen, vaikka viimeiset numerot olisivat kahden ja kolmen sijasta vaikkapa 66 ja 77. Tällöin summan viimeinen numero on 33, koska 6+7=136+7 = 13, ja tulon viimeinen numero on 22, koska 6⋅7=426 \cdot 7 = 42.

Vaikka tämä voi aluksi tuntua hassulta, luvun viimeisen numeron voi ajatella olevan jako­jäännös, kun luku jaetaan kymmenellä. Olemme siis yllä perustelleet, että summan/tulon jako­jäännös (kymmenellä jaettaessa) on sama kuin jako­jäännöksien summan/tulon jako­jäännös kymmenellä jaettaessa.

Kymmenen ei ole tässä suhteessa mitenkään erityinen luku. Olemme vain tottuneet esittämään lukuja kymmen­järjestelmässä, jossa on 1010 numeroa (0,1,2,3,4,5,6,7,8,90, 1, 2, 3, 4, 5, 6, 7, 8, 9). Samat ominaisuudet pätevät edelleen, vaikka tutkisimme jako­jäännöksiä vaikkapa seitsemällä jaettaessa. Esimerkiksi jos luvun aa jako­jäännös seitsemällä jaettaessa on kaksi ja luvun bb neljä, saadaan lukujen a+ba+b ja abab jako­jäännökset summaamalla tai kertomalla jako­jäännökset 22 ja 44 (ja ottamalla siitä vielä tarvittaessa jako­jäännös).

Jako­jäännöksistä puhumista helpottavat seuraavaksi esiteltävät kongruenssit.

7.3 Kongruenssit

Esitetään ensiksi määritelmä ja avataan sitä sitten esimerkein.

Määritelmä 7.1 Olkoot a,ba, b ja mm kokonais­lukuja (m≥1m \ge 1). Jos luvuilla aa ja bb on sama jako­jäännös luvulla mm jaettaessa (eli toisin sanoen mm jakaa luvun a−ba-b), niin merkitään a≡b(mod⁡m).a \equiv b \pmod{m}. Sanotaan, että aa ja bb ovat kongruentteja modulo mm. Lukua mm kutsutaan moduloksi. Puhekielessä sanotaan usein lyhyesti ”aa on bb modulo mm”.

Esimerkkejä:

  • a≡0(mod⁡2)a \equiv 0 \pmod{2} tarkoittaa, että aa:n jako­jäännös kahdella jaettaessa on 00 eli että aa on parillinen
  • a≡1(mod⁡2)a \equiv 1 \pmod{2} tarkoittaa, että aa:n jako­jäännös kahdella jaettaessa on 11 eli että aa on pariton
  • a≡b(mod⁡2)a \equiv b \pmod{2} tarkoittaa, että aa:lla ja bb:llä on samat jako­jäännökset kahdella jaettaessa eli että aa ja bb ovat joko molemmat parillisia tai molemmat parittomia
  • a≡3(mod⁡10)a \equiv 3 \pmod{10} tarkoittaa, että aa:n jako­jäännös kymmenellä jaettaessa on 33 eli että luvun aa viimeinen numero on 33

Lisää esimerkkejä konkreettisilla luvuilla:

  • 5≡1(mod⁡2)5 \equiv 1 \pmod{2}
  • 8≡2(mod⁡3)8 \equiv 2 \pmod{3}
  • 53≡23(mod⁡10)53 \equiv 23 \pmod{10}
  • 4≡−1(mod⁡5)4 \equiv -1 \pmod{5}

Suomen kielessä on erikseen sana ”pariton” luvuille, joiden jako­jäännös kahdella jaettaessa on yksi ja ”parillinen” luvuille, joiden jako­jäännös kahdella jaettaessa on nolla. Ehkäpä tästä syystä on helppoa hahmottaa parillisia ja parittomia lukuja ja olla samaa mieltä esimerkiksi väitteestä ”parillisen ja parittoman luvun summa on pariton”. Ikävä kyllä vastaavia sanoja ei ole esimerkiksi modulolle 33: suomen kielessä ei ole sanaa sille, että luvun jako­jäännös kolmella jaettaessa on kaksi. Tämä tekee kongruenssien sisäistämisestä vaikeampaa, vaikka kyse on loppu­kädessä tutusta ideasta.

7.4 Kongruenssien perus­ominaisuudet

Kongruenssien idea -osion esimerkit voidaan kirjoittaa kongruenssien avulla seuraavasti:

  • Jos a≡2(mod⁡10)a \equiv 2 \pmod{10} ja a≡3(mod⁡10)a \equiv 3 \pmod{10}, niin a+b≡5(mod⁡10)a + b \equiv 5 \pmod{10}
  • Jos a≡2(mod⁡10)a \equiv 2 \pmod{10} ja a≡3(mod⁡10)a \equiv 3 \pmod{10}, niin a⋅b≡6(mod⁡10)a \cdot b \equiv 6 \pmod{10}
  • Jos a≡6(mod⁡10)a \equiv 6 \pmod{10} ja a≡7(mod⁡10)a \equiv 7 \pmod{10}, niin a+b≡3(mod⁡10)a + b \equiv 3 \pmod{10}
  • Jos a≡6(mod⁡10)a \equiv 6 \pmod{10} ja a≡7(mod⁡10)a \equiv 7 \pmod{10}, niin a⋅b≡2(mod⁡10)a \cdot b \equiv 2 \pmod{10}

Idea on siis, että kongruenssi­yhtälöitä voi summata ja kertoa keskenään. Alla oleva lause kertoo tästä.

Lause 7.1 (Kongruenssien perus­lasku­toimitukset) Olkoot a,b,c,da, b, c, d ja mm kokonais­lukuja (m≥1m \ge 1). Oletetaan, että pätee a≡b(mod⁡m)jac≡d(mod⁡m).a \equiv b \pmod{m} \qquad \text{ja} \qquad c \equiv d \pmod{m}. Tällöin pätee a+c≡b+d(mod⁡m),a−c≡b−d(mod⁡m)jaac≡bd(mod⁡m).a + c \equiv b + d \pmod{m}, \qquad a - c \equiv b - d \pmod{m} \qquad \text{ja} \qquad ac \equiv bd \pmod{m}.

Käytännössä lauseesta seuraa, että kongruenssi­yhtälöitä voi käsitellä pitkälti kuten tavallisia yhtälöitä. Tätä ajatusta demonstroidaan alla parin esimerkin kautta ja myöhemmin tehtävissä.

Tarkkoihin todistuksiin palataan myöhemmissä teksteissä sen jälkeen, kun on saatu enemmän tuntumaa kongruensseista. Tulosten pitäisi kuitenkin käydä järkeen, olemmehan pitkälti perustelleet lasku­säännöt tapauksessa m=10m = 10.

7.5 Esimerkki­sovelluksia

7.5.1 Esimerkki 1: Viimeinen numero

Tehtävä 7.2 Mikä on luvun 1710017^{100} viimeinen numero?

Luku on tietysti aivan liian suuri laskettavaksi ilman laskinta. Käytetään siis kongruensseja apuna.

Viimeinen numero vastaa jako­jäännöstä kymmenellä jaettaessa, joten haluamme laskea, mitä 1710017^{100} on modulo kymmenen. Ensinnäkin tulos riippuu vain kanta­luvun ykkösten paikalla olevasta numerosta: 17100≡7100(mod⁡10).17^{100} \equiv 7^{100} \pmod{10}. (Tarkka perustelu: Tiedämme, että 17≡7(mod⁡10)17 \equiv 7 \pmod{10}. Kongruenssi­yhtälöitä saa kertoa keskenään. Kerrotaan tämä yhtälö itsensä kanssa. Saamme 172≡72(mod⁡10)17^2 \equiv 7^2 \pmod{10}. Kerrotaan uudestaan yhtälön 17≡7(mod⁡10)17 \equiv 7 \pmod{10} kanssa. Saamme 173≡73(mod⁡10)17^3 \equiv 7^3 \pmod{10}. Jatketaan näin.)

Huomataan siis, että kongruenssi­yhtälön saa korottaa puolittain johonkin potenssiin.

Luvun 71007^{100} viimeisen numeron laskeminen ei tosin ole sekään helppoa. Avain­idea on laskea muutama ensimmäinen arvo ja huomata säännön­mukaisuus: 71≡7(mod⁡10),7^1 \equiv 7 \pmod{10},

72≡7⋅7≡49≡9_(mod⁡10),73≡7⋅72≡7⋅9_≡63≡3_(mod⁡10),74≡7⋅73≡7⋅3_≡21≡1_(mod⁡10),75≡7⋅74≡7⋅1_≡7_(mod⁡10),76≡7⋅75≡7⋅7_≡49≡9(mod⁡10). \begin{aligned} & 7^2 \equiv 7 \cdot 7 \equiv 49 \equiv \underline{9} \pmod{10}, \\ & 7^3 \equiv 7 \cdot 7^2 \equiv 7 \cdot \underline{9} \equiv 63 \equiv \underline{3} \pmod{10}, \\ & 7^4 \equiv 7 \cdot 7^3 \equiv 7 \cdot \underline{3} \equiv 21 \equiv \underline{1} \pmod{10}, \\ & 7^5 \equiv 7 \cdot 7^4 \equiv 7 \cdot \underline{1} \equiv \underline{7} \qquad \ \pmod{10}, \\ & 7^6 \equiv 7 \cdot 7^5 \equiv 7 \cdot \underline{7} \equiv 49 \equiv 9 \pmod{10}. \end{aligned}

(Käytämme tässä ahkerasti kongruenssien lasku­sääntöjä.) Säännön­mukaisuus on selvä: viimeinen numero on vuorotellen 7,9,3,17, 9, 3, 1, ja sitten jono alkaa taas alusta. Aina neljällä jaollisilla eksponenteilla viimeinen numero on 11, ja koska 100100 on jaollinen neljällä, on luvun 71007^{100} viimeinen numero 11.

Täten myös luvun 1710017^{100} viimeinen numero on 11.

7.5.2 Esimerkki 2: Kolmen jaollisuus­sääntö

Tehtävä 7.3 Osoita, että luku on jaollinen kolmella täsmälleen silloin, kun sen numeroiden summa on jaollinen kolmella.

Esimerkiksi jos valitaan luku 816816, on sen numeroiden summa 8+1+6=158 + 1 + 6 = 15, joka on jaollinen kolmella. Siis alkuperäinen luku on myös jaollinen kolmella. (Tosiaan: 816=3⋅272816 = 3 \cdot 272.)

Tehtävän ratkaisua varten todetaan ensin, että 10≡1(mod⁡3).10 \equiv 1 \pmod{3}. Edellisessä esimerkissä todettiin, että kongruenssi­yhtälön saa korottaa puolittain potenssiin. Todetaan siis, että mikä tahansa kymmenen potenssi on 1(mod⁡3)1 \pmod{3}: 10k≡1(mod⁡3)10^k \equiv 1 \pmod{3} kaikilla k=1,2,3,…k = 1, 2, 3, \ldots.

Todistetaan sitten itse väite. Otetaan jokin positiivinen kokonais­luku, ja olkoot sen numerot merkitsevimmästä epämerkitsevimpään an,an−1,…,a2,a1,a0a_n, a_{n-1}, \ldots , a_2, a_1, a_0. Luku on siis an⋅10n+an−1⋅10n−1+…+a2⋅102+a1⋅10+a0.a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + \ldots + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0. Kongruenssien lasku­säännöillä ja edellisen aputuloksen nojalla kymmenen potenssit voidaan korvata ykkösellä, joten an⋅10n+an−1⋅10n−1+…+a2⋅102+a1⋅10+a0≡an⋅1+an−1⋅1+…+a2⋅1+a1⋅1+a0(mod⁡3). \begin{aligned} & \ a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + \ldots + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0 \\ \equiv & \ a_n \cdot 1 \ \ \ + a_{n-1} \cdot 1 \ \ \ \ \ \ + \ldots + a_2 \cdot 1 \ \ + a_1 \cdot 1 \ \ + a_0 \pmod{3}. \end{aligned} Täten luvulla ja sen numeroiden summalla on sama jako­jäännös kolmella jaettaessa. Erityisesti toinen on jaollinen kolmella täsmälleen silloin kuin toinen on. Tämä on haluttu väite.

Kommentti. Todistus toimii samalla tavalla jos luvun 33 korvaa luvulla 99. Oleellista on vain, että 10≡1(mod⁡9)10 \equiv 1 \pmod{9}. Tämä yhtälö voidaan taas korottaa johonkin potenssiin, mistä viimeistely tehdään samalla tavalla kuin kolmosen kohdalla.

7.6 Tehtäviä

Tehtävä 1. Määritellään luku­jono a1,a2,…a_1, a_2, \ldots niin, että sen ensimmäinen luku on 11 ja seuraava luku on aina kaksi kertaa edellinen plus yksi: a1=1a_1 = 1 ja an+1=2an+1a_{n+1} = 2a_n + 1 kaikilla n≥1n \ge 1. (Ensimmäiset luvut ovat siis 1,3,7,15,…1, 3, 7, 15, \ldots) Mikä on jako­jäännös, kun a100a_{100} jaetaan viidellä?

Tehtävä 2.

  1. Liitu­taululla on kolme kokonais­lukua. Osoita, että niistä voidaan valita kaksi, joiden erotus on jaollinen kahdella.
  2. Liitu­taululla on neljä kokonais­lukua. Osoita, että niistä voidaan valita kaksi, joiden erotus on jaollinen kolmella.
  3. Liitu­taululla on kolme kokonais­lukua. Osoita, että niistä voidaan valita yksi tai useampi, joiden summa on jaollinen kolmella.

Tehtävä 3. Onko olemassa kokonais­lukua xx, jolla 12x+612x + 6 on jaollinen

  1. neljällä?
  2. viidellä?

Tehtävä 4. Onko olemassa kokonais­lukua xx, jolla x2+1x^2 + 1 on jaollinen kolmella? Entä viidellä tai seitsemällä?

Tehtävä 5. Montako alku­lukua pp, joilla myös p+2p+2 ja p+4p+4 ovat alku­lukuja, on olemassa?

Tehtävä 6. Tutkitaan seuraavaa muunnelmaa numeroiden summasta: sen sijaan että lasketaan yhteen luvun kaikki numerot, niin vähennetäänkin aina joka toinen numero. Esimerkiksi aloittamalla luvusta 123456123456 saadaan 1−2+3−4+5−6=−31 - 2 + 3 - 4 + 5 - 6 = -3. Osoita seuraava sääntö yhdellätoista jaollisuudelle: luku on jaollinen yhdellätoista täsmälleen silloin, kun sen muunneltu numeroiden summa on jaollinen yhdellätoista.

Tehtävä 7. Liitu­taululla on aluksi kokonais­luku 11. Jos liitu­taulun nykyinen luku on xx, sen voi korvata yhdellä seuraavista luvuista: x−5,x+10x-5, x+10 tai 3x+13x+1. Onko näitä operaatioita toistamalla mahdollista päästä lukuun 22?