Kongruenssin perusominaisuuksia 2

• Kongruenttien lukujen summa ja tulo:
  • Jos a ≡ b (mod n) ja c ≡ d (mod n), niin
    a + c ≡ b + d (mod n) ja
    ac ≡ bd (mod n)
• Kertolaskusäännöstä seuraa potenssien kongruenssi:
  Jos a ≡ b (mod n), niin a^k ≡ b^k (mod n), k ∈ ℤ

HUOM! Jokainen luku on kongruentti jakojäännöksen kanssa:
Olkoon r jakojäännös, kun luku a jaetaan luvulla n. Nyt a ≡ r (mod n).

Siis kun määritetään jakojäännöksiä tai tutkitaan jaollisuutta, niin yhteenlaskettavat, tulon tekijät ja potenssien kantaluvut voidaan korvata yksinkertaisimmilla kongruenteilla luvuilla eli jakojäännöksillä, jotka jäävät, kun luvut jaetaan luvulla n. 

HUOM! Jaksollisesti toistuvia ilmiöitä kuten kellonajat (mod 24) ja viikonpäivät (mod 7) voidaan tutkia kongruenssien avulla.

 

ESIM 3. Määritä pienin ei-negatiivinen kokonaisluku, jonka kanssa luku 16¹⁰ + 82 on kongruentti modulo 7. 

*** 

ESIM 4. Jouluaatto 2004 oli perjantai. Mikä se on vuonna 2015?

***

ESIM 5. Määritä jakojäännös, kun 753 + 6¹²⁰¹ jaetaan 7:llä.
(Korvataan luvut yksinkertaisimmilla kongruenteilla luvuilla mod 7)

***

ESIM 6. Osoita, että luku 81 + 703 ⋅ 22¹⁸ on jaollinen 7:llä.

***

ESIM 7. Osoita, että 7²⁰⁰ ≡ 1 (mod 5).

*** 

ESIM 8. Mikä on luvun 3²⁰⁰⁷ viimeinen numero?
(Tutkitaan 10:llä jaollisuutta eli mikä jää jakojäännökseksi, kun luku jaetaan 10:llä: esim. 1352 = 135 ⋅ 10 + 2)

*** 

ESIM 9. Osoita, että kokonaisluku on jaollinen 3:lla, jos ja vain jos sen numeroiden summa on jaollinen kolmella.

*** 

Tehtäviä

• Määritä jakojäännös, kun luku 17 + 7 ⋅ 25⁷ jaetaan 6:lla.
• Osoita, että luku 17ⁿ + 13 ⋅ 25ⁿ + 2 on jaollinen luvulla 8. (n ∈ ℤ₊)
• Määritä luvun 3²²⁴ viimeinen numero.
• Määritä luvun 101²⁰⁰⁷ kaksi viimeistä ja kaksi ensimmäistä numeroa.
• Tutki, onko luku 46⁷⁸ + 89⁶⁷ jaollinen viidellä? (YO K11)

 

(1) r = 0
(2) on se
(3) 1
(4) viimeiset 01 ja ensimmäiset 47
(5) on