3. Modulolaskentaa
Kongruenssi
Kongruenssin määritelmä:
Nyt a - b = qn voi tarkoittaa toisaalta jakoyhtälöä a = qn + b (a jaetaan luvulla n), jos 0 ≤ b < n
Esimerkiksi modulossa 7
22≡1 (mod 7) sillä 22-1 = 21 = 3*7
[[$43\equiv15\ \left(mod\ 7\right){,}\ sillä\ 43-15=4\cdot7$]]
[[$Lukujonossa\ olevat\ luvut\ ...{,}-6{,}\ 1{,}\ 8{,}\ 15{,}\ 22{,}\ 29{,}\ 36{,}\ 43{,}\ ...$]]
[[$ovat\ keskenään\ kongruentteja\ modulossa\ 7$]]
[[$jos\ a\equiv b\ \left(mod\ n\right)\ niin\ tämä\ tarkoittaa\ toisaalta\ sitä{,}\ että\ $]]
[[$kun\ a\ ja\ b\ jaetaan\ n:llä{,}\ saadaan\ sama\ jakojäännös$]]
tehtävästä 301 eteenpäin
Kotitehtävät: 305, 306 ja 278
Luku a on kongruentti luvun b kanssa modulo n, jos lukujen a ja b erotus on jaollinen luvulla n
Tätä merkitään
[[$a\equiv b\ \left(mod\ n\right)\ \ \ \Leftrightarrow\ \ a-b=qn\ {,}\ \ a{,}\ b{,}\ q\ ja\ n\in\mathbb{Z}$]]
[[$a\equiv b\ \left(mod\ n\right)\ \ \ \Leftrightarrow\ \ a-b=qn\ {,}\ \ a{,}\ b{,}\ q\ ja\ n\in\mathbb{Z}$]]
Nyt a - b = qn voi tarkoittaa toisaalta jakoyhtälöä a = qn + b (a jaetaan luvulla n), jos 0 ≤ b < n
Esimerkiksi modulossa 7
22≡1 (mod 7) sillä 22-1 = 21 = 3*7
[[$43\equiv15\ \left(mod\ 7\right){,}\ sillä\ 43-15=4\cdot7$]]
[[$Lukujonossa\ olevat\ luvut\ ...{,}-6{,}\ 1{,}\ 8{,}\ 15{,}\ 22{,}\ 29{,}\ 36{,}\ 43{,}\ ...$]]
[[$ovat\ keskenään\ kongruentteja\ modulossa\ 7$]]
[[$jos\ a\equiv b\ \left(mod\ n\right)\ niin\ tämä\ tarkoittaa\ toisaalta\ sitä{,}\ että\ $]]
[[$kun\ a\ ja\ b\ jaetaan\ n:llä{,}\ saadaan\ sama\ jakojäännös$]]
tehtävästä 301 eteenpäin
Kotitehtävät: 305, 306 ja 278
Sinulla ei ole tarvittavia oikeuksia lähettää mitään.
Kongruenssin laskusääntöjä
Perusominaisuuksia
[[$1.\ \ \ a\equiv a\ \left(mod\ n\right){,}\ \ 2.\ \ jos\ a\equiv b\ \left(mod\ n\right)\ niin\ b\equiv a\ \left(mod\ n\right)$]]
[[$3.\ \ \ jos\ a\equiv b\ \left(mod\ n\right)\ ja\ b\equiv c\ \left(nod\ n\right)\ niin\ a\equiv c\ \left(mod\ n\right)$]]
Kun modulo on sama, kongruensseja voidaan laskea yhteen tai kertoa keskenään
[[$jos\ a\equiv b\ \left(mod\ n\right)\ \ ja\ c\equiv d\ \left(mod\ n\right)\ \ \ niin\ a+c\equiv b+d\ \left(mod\ n\right)\ ja\ ac\equiv bd\left(mod\ n\right)$]]
Kongruenssiin voidaan lisätä mikä tahansa luku k tai kongruessi voidaan kertoa luvulla k
[[$jos\ a\equiv b\ \left(mod\ n\right)\ niin\ \ a+k\equiv b+k\ \left(mod\ n\right)\ \ ja\ ak\equiv bk\ \left(mod\ n\right)$]]
Kongruenssi voidaan myös korottaa potenssiin k
[[$jos\ a\equiv b\ \left(mod\ n\right)\ \ niin\ \ \ a^k\equiv b^k\ \left(mod\ n\right){,}\ k\in\mathbb{Z}_+$]]
Esimerkkejä
[[$Tarkastellaan\ moduloa\ 11{,}\ jossa\ 1237\ \equiv5\ \left(mod\ 11\right)\ ja\ 1231\equiv-1\ \left(mod\ 11\right)$]]
[[$\left(\left(perustelua:\ 1237=112\cdot11+5\ ja\ 1231-\left(-1\right)=112\cdot11\right)\right)$]]
[[$Nyt\ 1237+1231\equiv5-1\equiv4\ \left(mod\ 11\right)\ ja$]]
[[$1237\cdot1231\equiv5\cdot\left(-1\right)\equiv-5\ \left(mod\ 11\right)$]]
[[$1231\equiv-1\ \left(mod\ 11\right)\ \ \Rightarrow\ 1231^{2024}\equiv\left(-1\right)^{2024}\equiv1\ \left(mod\ 11\right)$]]
Tämä tarkoittaa sitä, että kun valtavan suuri luku
[[$1231^{2024}\ jaetaan\ luvulla\ 11\ saadaan\ jakojäännökseksi\ 1$]]
[[$Mikä\ on\ jakojäännös{,}\ kun\ luku\ 15^{1000}\ jaetaan\ luvulla\ 7?$]]
Sama kysymys voidaan esittää myös muodossa: Mikä on pienin positiivinen luku x, jolle on voimassa
[[$15^{1000}=x\left(mod\ 7\right)$]]
Lähdetään pienentämään lukua 15^1000 ja aluksi mietitään, voidaanko kantalukua 15 pienentää modulossa 7
[[$Huomataan{,}\ että\ 15\equiv1\ \left(mod\ 7\right)$]]
[[$\Rightarrow\ 15^{1000}\equiv1^{1000}\equiv1\ \left(mod\ 7\right)\ eli\ jakojäännös\ on\ 1$]]
Kotitehtävät: 326 ja 330
Mikä on jakojäännös, kun luku
a)
[[$2^{42}+7\ jaetaan\ luvulla\ 5$]]
Kyseessä on modulo 5, jossa molempia yhteenlaskettavia voidaan pienentää
[[$7\equiv2\ \left(mod\ 5\right)$]]
[[$Minkä\ luvun\ kanssa\ 2^{42}\ on\ kongruentti\ modulossa\ 5?\ \left(2^{42}\equiv x\ \left(mod\ 5\right)\right)$]]
Nyt ei voida kantalukua 2 pienentää modulossa 5. Mietitään, löytyykö joku luvun 2 potenssi, joka on kongruentti 1 tai -1 kanssa modulossa 5?
[[$Huomataan{,}\ että\ 2^4\equiv1\ \left(mod\ 5\right)$]]
[[$2^{42}=\left(2^4\right)^{10}\cdot2^2\equiv1^{10}\cdot4\equiv4\ \left(mod\ 5\right)$]]
[[$\Rightarrow\ 2^{42}+7\ \equiv4+2\equiv6\equiv1\ \left(mod\ 5\right)$]]
[[$Nyt\ jakojäännös\ on\ 1$]]
b)
[[$18^2\cdot2^{100}\ jaetaan\ luvulla\ 11$]]
"pienennetään" molempia luvun tekijöitä
[[$18\equiv7\equiv-4\ \left(mod\ 11\right)$]]
[[$\Rightarrow18^2\equiv\left(-4\right)^2\equiv16\equiv5\ \left(mod\ 11\right)$]]
[[$Mikä\ luvun\ 2\ potenssi\ on\ kongruentti\ 1\ tai\ -1\ kanssa\ modulossa\ 11?$]]
[[$Huomataan{,}\ että\ 2^5\equiv-1\ \left(mod\ 11\right)$]]
[[$2^{100}\equiv\left(2^5\right)^{^{20}}\equiv\left(-1\right)^{20}\equiv1\ \left(mod\ 11\right)$]]
[[$nyt\ 18^2\cdot2^{100}\equiv5\cdot1\equiv5\ \left(mod\ 11\right){,}\ joten\ jakojäännös\ on\ 5$]]
Kotitehtävät: 337, 339 ja 342
[[$1.\ \ \ a\equiv a\ \left(mod\ n\right){,}\ \ 2.\ \ jos\ a\equiv b\ \left(mod\ n\right)\ niin\ b\equiv a\ \left(mod\ n\right)$]]
[[$3.\ \ \ jos\ a\equiv b\ \left(mod\ n\right)\ ja\ b\equiv c\ \left(nod\ n\right)\ niin\ a\equiv c\ \left(mod\ n\right)$]]
Kun modulo on sama, kongruensseja voidaan laskea yhteen tai kertoa keskenään
[[$jos\ a\equiv b\ \left(mod\ n\right)\ \ ja\ c\equiv d\ \left(mod\ n\right)\ \ \ niin\ a+c\equiv b+d\ \left(mod\ n\right)\ ja\ ac\equiv bd\left(mod\ n\right)$]]
Kongruenssiin voidaan lisätä mikä tahansa luku k tai kongruessi voidaan kertoa luvulla k
[[$jos\ a\equiv b\ \left(mod\ n\right)\ niin\ \ a+k\equiv b+k\ \left(mod\ n\right)\ \ ja\ ak\equiv bk\ \left(mod\ n\right)$]]
Kongruenssi voidaan myös korottaa potenssiin k
[[$jos\ a\equiv b\ \left(mod\ n\right)\ \ niin\ \ \ a^k\equiv b^k\ \left(mod\ n\right){,}\ k\in\mathbb{Z}_+$]]
Esimerkkejä
[[$Tarkastellaan\ moduloa\ 11{,}\ jossa\ 1237\ \equiv5\ \left(mod\ 11\right)\ ja\ 1231\equiv-1\ \left(mod\ 11\right)$]]
[[$\left(\left(perustelua:\ 1237=112\cdot11+5\ ja\ 1231-\left(-1\right)=112\cdot11\right)\right)$]]
[[$Nyt\ 1237+1231\equiv5-1\equiv4\ \left(mod\ 11\right)\ ja$]]
[[$1237\cdot1231\equiv5\cdot\left(-1\right)\equiv-5\ \left(mod\ 11\right)$]]
[[$1231\equiv-1\ \left(mod\ 11\right)\ \ \Rightarrow\ 1231^{2024}\equiv\left(-1\right)^{2024}\equiv1\ \left(mod\ 11\right)$]]
Tämä tarkoittaa sitä, että kun valtavan suuri luku
[[$1231^{2024}\ jaetaan\ luvulla\ 11\ saadaan\ jakojäännökseksi\ 1$]]
[[$Mikä\ on\ jakojäännös{,}\ kun\ luku\ 15^{1000}\ jaetaan\ luvulla\ 7?$]]
Sama kysymys voidaan esittää myös muodossa: Mikä on pienin positiivinen luku x, jolle on voimassa
[[$15^{1000}=x\left(mod\ 7\right)$]]
Lähdetään pienentämään lukua 15^1000 ja aluksi mietitään, voidaanko kantalukua 15 pienentää modulossa 7
[[$Huomataan{,}\ että\ 15\equiv1\ \left(mod\ 7\right)$]]
[[$\Rightarrow\ 15^{1000}\equiv1^{1000}\equiv1\ \left(mod\ 7\right)\ eli\ jakojäännös\ on\ 1$]]
Kotitehtävät: 326 ja 330
Mikä on jakojäännös, kun luku
a)
[[$2^{42}+7\ jaetaan\ luvulla\ 5$]]
Kyseessä on modulo 5, jossa molempia yhteenlaskettavia voidaan pienentää
[[$7\equiv2\ \left(mod\ 5\right)$]]
[[$Minkä\ luvun\ kanssa\ 2^{42}\ on\ kongruentti\ modulossa\ 5?\ \left(2^{42}\equiv x\ \left(mod\ 5\right)\right)$]]
Nyt ei voida kantalukua 2 pienentää modulossa 5. Mietitään, löytyykö joku luvun 2 potenssi, joka on kongruentti 1 tai -1 kanssa modulossa 5?
[[$Huomataan{,}\ että\ 2^4\equiv1\ \left(mod\ 5\right)$]]
[[$2^{42}=\left(2^4\right)^{10}\cdot2^2\equiv1^{10}\cdot4\equiv4\ \left(mod\ 5\right)$]]
[[$\Rightarrow\ 2^{42}+7\ \equiv4+2\equiv6\equiv1\ \left(mod\ 5\right)$]]
[[$Nyt\ jakojäännös\ on\ 1$]]
b)
[[$18^2\cdot2^{100}\ jaetaan\ luvulla\ 11$]]
"pienennetään" molempia luvun tekijöitä
[[$18\equiv7\equiv-4\ \left(mod\ 11\right)$]]
[[$\Rightarrow18^2\equiv\left(-4\right)^2\equiv16\equiv5\ \left(mod\ 11\right)$]]
[[$Mikä\ luvun\ 2\ potenssi\ on\ kongruentti\ 1\ tai\ -1\ kanssa\ modulossa\ 11?$]]
[[$Huomataan{,}\ että\ 2^5\equiv-1\ \left(mod\ 11\right)$]]
[[$2^{100}\equiv\left(2^5\right)^{^{20}}\equiv\left(-1\right)^{20}\equiv1\ \left(mod\ 11\right)$]]
[[$nyt\ 18^2\cdot2^{100}\equiv5\cdot1\equiv5\ \left(mod\ 11\right){,}\ joten\ jakojäännös\ on\ 5$]]
Kotitehtävät: 337, 339 ja 342
Sinulla ei ole tarvittavia oikeuksia lähettää mitään.