2.2 Jaollisuustarkasteluja

Teoria ja esimerkit

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

Esimerkit

ESIM 3. Määritä pienin ei-negatiivinen kokonaisluku, jonka kanssa luku $16^{10}+82$ on kongruentti modulo 7.

$16^{10}+82\equiv2^{10}+5\ \left(\text{mod}\ 7\right)$

$=\left(2^5\right)^2+5=\left(32\right)^2+5$
$\equiv4^2+5\ \left(\text{mod}\ 7\right)=21\equiv0\ \left(\text{mod}\ 7\right)$

V: Pienin luku ... on 0.

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

Viikonpäivät ovat kongruentteja modulo 7.

Päiviä välissä: 14 * 365 + 3

(Joka neljäs vuosi on karkausvuosi. Tasavuosisata on, jos se on jaollinen 400:lla. Siis: 2000, 2004, 2008...)

$14\cdot365+3\equiv0\cdot365+3\ \equiv3\ \left(\text{mod}\ 7\right)$

Siis tämän vuoden jouluaatto on perjantai + 3 päivää:

maanantai.

ESIM 4b. Aleksanterin (nimi muutettu) synttärit on 7.10.2000 (vuonna 2018 se on sunnuntai). Minä viikonpäivänä A syntyi?

$18\cdot365+4\equiv4\cdot1+4\equiv8\equiv1\ \left(\text{mod}\ 7\right)$

1 päivä taaksepäin: lauantai

ESIM 5. Määritä jakojäännös, kun $753+6^{1201}$ jaetaan 7:llä.
(Korvataan luvut yksinkertaisimmilla kongruenteilla luvuilla mod 7)

$753+6^{1201}\equiv53+\left(-1\right)^{1201}\equiv4-1\equiv3\ \left(\text{mod}\ 7\right)$

ESIM 6. Osoita, että luku asdf on jaollinen luvulla 7.

$81+703\cdot22^{18}\equiv4+3\cdot1^{18}\equiv7\equiv0\ \left(\text{mod}\ 7\right)$

ESIM 7. Osoita, että $7^{200}\equiv1\ \left(\text{mod}\ 5\right)$

$7^{200}\equiv2^{200}\equiv\left(2^2\right)^{100}$
$\equiv4^{100}\equiv\left(-1\right)^{100}\equiv1\ \left(mod\ 5\right)$

ESIM 8. Mikä on luvun viimeinen numero?

$3^{2007}\equiv3^1\cdot3^{2006}\equiv3^1\cdot\left(3^2\right)^{1003}$

$\equiv3\cdot9^{1003}\equiv3\cdot\left(-1\right)^{1003}\equiv-3\ \equiv7\left(mod\ 10\right)$