Diszkr´ et matematika I. k¨ oz´ epszint
Diszkr´et matematika I. k¨oz´epszint 10. el˝ oad´as
M´erai L´aszl´ o di´ai alapj´an Komputeralgebra Tansz´ ek
2014. ˝ osz
2014. ˝ osz
1.
Diszkr´ et matematika I. k¨ oz´ epszint
Felh´ıv´as
Szakir´anyv´alaszt´o f´orum december 4-´en. Jelentkez´es november 26-ig: http://goo.gl/forms/dYlHA8SQOZ B˝ovebb inform´aci´o: http://compalg.inf.elte.hu/∼nagy
2014. ˝ osz
2.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Line´aris diofantikus egyenletek Diofantikus egyenletek: egyenletek eg´esz megold´asait keress¨ uk. Line´aris diofantikus egyenletek: ax + by = c, ahol a, b, c eg´eszek. Ez ekvivalens az ax ≡ c (modb), by ≡ c (moda) kongruenci´akkal. Az ax + by = c pontosan akkor oldhat´ o meg, ha (a, b) | c, ´es ekkor a ov´ıtett euklideszi algoritmussal. megold´asok megkaphat´ok a b˝ Tov´abbi diofantikus egyenletek: x 2 + y 2 = −4: nincs val´ os megold´as. x 2 − 4y 2 = 3: nincs megold´as, u.i. 4-gyel val´ o oszt´asi marad´ekok: x 2 ≡ 3 (mod 4). De ez nem lehet, a n´egyzetsz´am marad´eka 0 vagy 1: x 4k 4k + 1 4k + 2 4k + 3
x 2 mod 4 0 1 0 1
3.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
Szimult´an kongruenci´ak Szeretn´enk olyan x eg´eszet, mely egyszerre el´eg´ıti ki a k¨ovetkez˝o kongruenci´akat: 2x≡1 (mod 3) 4x≡3 (mod 5) A kongruenci´akat k¨ ul¨on megoldva: x≡2 (mod 3) x≡2 (mod 5)
L´atszik, hogy x = 2 megold´as lesz! Vannak-e m´as megold´asok? 2, 17, 32,. . . ,2 + 15`; tov´abbi megold´asok? hogyan oldjuk meg az ´altal´anos esetben: x≡2 (mod 3) x≡3 (mod 5)
2014. ˝ osz
4.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Szimult´an kongruenci´ak Feladat: Oldjuk meg a k¨ ovetkez˝ o kongruenciarendszert: a1 x ≡ b1 (modm1 ) a2 x ≡ b2 (modm2 ) .. . an x ≡ bn (modmn )
Az egyes ai x ≡ bi (modmi ) line´aris kongruenci´ak k¨ ul¨ on megoldhat´oak: x ≡ c1 (modm1 ) x ≡ c2 (modm2 ) .. . x ≡ cn (modmn )
5.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Szimult´an kongruenci´ak Feladat: Oldjuk meg a k¨ ovetkez˝ o kongruenciarendszert: x ≡ c1 (modm1 ) x ≡ c2 (modm2 ) .. . x ≡ cn (modmn )
Feltehet˝o, hogy az m1 , m2 , . . . , mn modulusok relat´ıv pr´ımek: ha pl. m1 = m10 d, m2 = m20 d, akkor az els˝ o k´et sor helyettes´ıthet˝o (biz.: k´es˝obb) x x x x
≡ c1 ≡ c1 ≡ c2 ≡ c2
(modm10 ) (modd) (modm20 ) (modd)
Ha itt c1 6≡ c2 (modd), akkor nincs megold´as, k¨ ul¨ onben az egyik sor t¨or¨olhet˝o.
6.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
K´ınai marad´ekt´etel T´etel Legyenek 1 < m1 , m2 , . . . , mn relat´ıv pr´ım sz´amok, c1 , c2 , . . . , cn eg´eszek. Ekkor az x ≡ c1 (modm1 ) x ≡ c2 (modm2 ) .. . x ≡ cn (modmn )
kongruenciarendszer megoldhat´ o, ´es b´armely k´et megold´as kongruens egym´assal modulo m1 · m2 · · · mn .
7.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
K´ınai marad´ekt´etel x ≡ c1 (modm1 ), x ≡ c2 (modm2 ), . . . , x ≡ cn (modmn ). x =?
Bizony´ıt´as A bizony´ıt´as konstrukt´ıv! ov´ıtett euklideszi algoritmussal oldjuk meg az Legyen m = m1 m2 . A b˝ m1 x1 + m2 x2 = 1 egyenletet. Legyen c1,2 = m1 x1 c2 + m2 x2 c1 . Ekkor c1,2 ≡ cj (modmj ) (j = 1, 2). Ha x ≡ c1,2 (modm), akkor x megold´asa az els˝o k´et kongruenci´anak. Megford´ıtva: ha x megold´asa az els˝o k´et kongruenci´anak, akkor x − c1,2 oszthat´ o m1 -gyel, m2 -vel, ´ıgy a szorzatukkal is: x ≡ c1,2 (modm). Az eredeti kongruenciarendszer ekvivalens az x ≡ c1,2 (modm1 m2 ) x ≡ c3 (modm3 ) .. . x ≡ cn (modmn )
kongruenciarendszerrel. n szerinti indukci´ oval ad´ odik az ´all´ıt´as.
8.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Szimult´an kongruenci´ak P´elda x≡2 (mod 3) x≡3 (mod 5)
Oldjuk meg az 3x1 + 5x2 = 1 egyenletet! Megold´asok: x1 = −3, x2 = 2. ⇒ ⇒ c1,2 = 3 · (−3) · 3 + 5 · 2 · 2 = −27 + 20 = −7. ¨ Osszes megold´as: {−7 + 15` : ` ∈ Z}={8 + 15` : ` ∈ Z}.
P´elda x≡2 (mod 3) x≡3 (mod 5) x≡4 (mod 7)
c1,2 =8
=⇒
x≡8 (mod 15) x≡4 (mod 7)
Oldjuk meg a 15x1,2 + 7x3 = 1 egyenletet! Megold´asok: x1,2 = 1, x3 = −2. ⇒ ⇒ c1,2,3 = 15 · 1 · 4 + 7 · (−2) · 8 = 60 − 112 = −52. ¨ Osszes megold´as: {−52 + 105` : ` ∈ Z}={53 + 105` : ` ∈ Z}.
9.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Marad´ekoszt´alyok Sokszor egy adott probl´ema megold´asa nem egy konkr´et sz´am (sz´amok csal´adja), hanem egy eg´esz halmaz (halmazok csal´adja): 2x ≡ 5 (mod 7), megold´asok: {6 + 7` : ` ∈ Z} 10x ≡ 8 (mod 22), megold´asok: {14 + 22` : ` ∈ Z}, 10x ≡ 8 mod 22, megold´asok: {3 + 22` : ` ∈ Z}.
Defin´ıci´o Egy r¨ogz´ıtett m modulus ´es a eg´esz eset´en, az a-val kongruens elemek halmaz´at az a ´altal reprezent´alt marad´ekoszt´alynak nevezz¨ uk: a = {x ∈ Z : x ≡ a (modm)}={a + `m : ` ∈ Z}.
P´elda A 2x ≡ 5 (mod 7) megold´asa: 6 A 10x ≡ 8 (mod 22), megold´asai: 14, 3. m = 7 modulussal 2 = 23 = {. . . , −5, 2, 9, 16, 23, 30, . . . } ´ Altal´ aban: a = b ⇔ a ≡ b (modm).
10.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Marad´ekoszt´alyok Defin´ıci´o Egy r¨ogz´ıtett m modulus eset´en, ha minden marad´ekoszt´alyb´ol pontosan egy elemet kivesz¨ unk, akkor az ´ıgy kapott sz´amok teljes marad´ekrendszert alkotnak modulo m.
P´elda {33, −5, 11, −11, −8} teljes marad´ekrendszer modulo 5. Gyakori v´alaszt´as teljes marad´ekrendszerekre Legkisebb nemnegat´ıv marad´ekok: {0, 1, . . . , m − 1}; Legkisebb abszol´ ut ´ert´ek˝ u marad´ekok: m−1 0, ±1, . . . , ± , ha 2 2 - m; m 0, ±1, . . . , ± m−2 , 2 2 , ha 2 | m.
11.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Marad´ekoszt´alyok Megjegyz´ es: ha egy marad´ekoszt´aly valamely eleme relat´ıv pr´ım a modulushoz, akkor az ¨osszes eleme az: (a + `m, m) = (a, m) = 1. Ezeket uk. a marad´ekoszt´alyokat reduk´alt marad´ekoszt´alyoknak nevezz¨
Defin´ıci´o Egy r¨ogz´ıtett m modulus eset´en, ha mindazon marad´ekoszt´alyb´ol, melyek elemei relat´ıv pr´ımek a modulushoz kivesz¨ unk pontosan egy elemet, akkor az ´ıgy kapott sz´amok reduk´alt marad´ekrendszert alkotnak modulo m.
P´elda {1, 2, 3, 4} reduk´alt marad´ekrendszer modulo 5. {1, −1} reduk´alt marad´ekrendszer modulo 3. {1, 19, 29, 7} reduk´alt marad´ekrendszer modulo 8. {0, 1, 2, 3, 4} nem reduk´alt marad´ekrendszer modulo 5.
12.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Marad´ekoszt´alyok A marad´ekoszt´alyok k¨oz¨ ott term´eszetes m´ odon m˝ uveleteket defini´alhatunk:
Defin´ıci´o R¨ogz´ıtett m modulus, ´es a, b eg´eszek eset´en legyen: def
a + b = a + b;
def
a · b = a · b.
´ ıt´as All´ Ez ´ertelmes defin´ıci´o, azaz ,ha a = a∗ , b = b ∗ , akkor a + b = a∗ + b ∗ , illetve a · b = a∗ · b ∗ .
Bizony´ıt´as Mivel a = a∗ , b = b ∗ ⇒ a ≡ a∗ (modm), b ≡ b ∗ (modm) ⇒ ⇒ a + b ≡ a∗ + b ∗ (modm) ⇒ a + b = a∗ + b ∗ ⇒ a + b = a∗ + b ∗ . Szorz´as hasonl´oan.
13.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Marad´ekoszt´alyok A marad´ekoszt´alyok k¨oz¨ ott term´eszetes m´ odon m˝ uveleteket defini´alhatunk: a + b = a + b; a · b = a · b.
Defin´ıci´o R¨ogz´ıtett m modulus eset´en legyen Zm a marad´ekoszt´alyok halmaza. Ekkor a halmaz elemei k¨ oz¨ ott defini´alhatunk ¨ osszead´ast, illetve szorz´ast.
P´elda Z3 = {0, 1, 2}.
Z4 = {0, 1, 2, 3}.
+
0
1
2
·
0
1
2
0
0
1
2
0
0
0
0
1
1
2
0
1
0
1
2
2
2
0
1
2
0
2
1
+
0
1
2
3
·
0
1
2
3
0
0
1
2
3
0
0
0
0
0
1
1
2
3
0
1
0
1
2
3
2
2
3
0
1
2
0
2
0
2
3
3
0
1
2
3
0
3
2
1
14.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Marad´ekoszt´alyok T´etel Legyen m > 1 eg´esz. Ha 1 < (a, m) < m, akkor a nulloszt´o Zm -ben: a-hoz van olyan b, hogy a · b = 0 Ha (a, m) = 1, akkor a-nak van reciproka (multiplikat´ıv inverze) Zm -ben: a-hoz van olyan x, hogy a · x = 1. Speci´alisan, ha m pr´ım, minden nem-nulla marad´ekoszt´allyal lehet osztani.
P´elda Legyen m = 9. 6 · 3 = 18 = 0. Legyen m = 8. (2, 9) = 1, ´ıgy 2 · 5 = 10 = 1.
Bizony´ıt´as a Legyen d = (a, m). Ekkor a · m d = d · m ≡ 0 (modm), ahonnan b = m/d jel¨ol´essel a · b = 0. Ha (a, m) = 1, akkor a b˝ ov´ıtett euklideszi algoritmussal megadhat´oak x, y eg´eszek, hogy ax + my = 1. Ekkor ax ≡ 1 (modm) azaz a · x = 1.
15.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Euler-f´ele ϕ f¨uggv´eny Defin´ıci´o Egy m > 0 eg´esz sz´am eset´en legyen ϕ(m) az m-n´el kisebb, hozz´a relat´ıv pr´ım pozit´ıv eg´eszek sz´ama: ϕ(m) = |{i : 0 < i < m, (m, i) = 1}|.
P´elda ϕ(5) = 4: 5-h¨oz relat´ıv pr´ım pozit´ıv eg´eszek 1, 2, 3, 4; ϕ(6) = 2: 6-hoz relat´ıv pr´ım pozit´ıv eg´eszek 1, 5; ϕ(12) = 4: 12-h¨oz relat´ıv pr´ım pozit´ıv eg´eszek 1, 5, 7, 11; ϕ(15) = 8: 15-h¨oz relat´ıv pr´ım pozit´ıv eg´eszek 1, 2, 4, 7, 8, 11, 13, 14. Megjegyz´ es: ϕ(m) a reduk´alt marad´ekoszt´alyok sz´ama modulo m.
16.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
Euler-f´ele ϕ f¨uggv´eny ϕ(m) = |{i : 0 < i < m, (m, i) = 1}|
T´etel (NB) Legyen m kanonikus alakja = p1α1 p2α2 · · · p`α` . Ekkor mQ Q` ` ϕ(m) = m · i=1 1 − p1i = i=1 (piαi − piαi −1 ).
P´elda ϕ(5) = 5 1 − 15 = 51 − 50 = 4; 1 0 1 ϕ(6) = 6 1 − 12 1 − 13 = − 30 ) = 2; (2 −2 2 )(3 1 1 1 ϕ(12) = 12 1 − 2 1 − 3 = (2 − 2 )(31 − 30 ) = 4; ϕ(15) = 15 1 − 13 1 − 15 = (31 − 30 )(51 − 50 ) = 8.
2014. ˝ osz
17.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
Euler-Fermat t´etel T´etel Legyen m > 1 eg´esz sz´am, a olyan eg´esz, melyre (a, m) = 1. Ekkor aϕ(m) ≡ 1 (modm).
K¨ovetkezm´eny (Fermat t´etel) Legyen p pr´ımsz´am, p - a. Ekkor ap−1 ≡ 1 (modp), illetve tetsz˝oleges a eset´en ap ≡ a (modp).
P´elda ϕ(6) = 2 ⇒ 52 = 25 ≡ 1 (mod 6); ϕ(12) = 4 ⇒ 54 = 625 ≡ 1 (mod 12); 74 = 2401 ≡ 1 (mod 12). Figyelem! 24 = 16 ≡ 4 6≡ 1 (mod 12), mert (2, 12) = 2 6= 1.
2014. ˝ osz
18.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Euler-Fermat t´etel bizony´ıt´asa Lemma Legyen m > 1 eg´esz, a1 , a2 , . . . , am teljes marad´ekrendszer modulo m. Ekkor minden a, b eg´eszre, melyre (a, m) = 1, a · a1 + b, a · a2 + b,. . . , a · am + b szint´en teljes marad´ekrendszer. Tov´abb´a, ha a1 , a2 , . . . , aϕ(m) reduk´alt marad´ekrendszer modulo m, akkor a · a1 , a · a2 ,. . . , a · aϕ(m) szint´en reduk´alt marad´ekrendszer.
Bizony´ıt´as Tudjuk, hogy aai + b ≡ aaj + b (modm) ⇔ aai ≡ aaj (modm). Mivel (a, m) = 1, egyszer˝ us´ıthet¨ unk a-val: ai ≡ aj (modm). Teh´at a · a1 + b, a · a2 + b,. . . , a · am + b p´aronk´ent inkongruensek. Mivel sz´amuk m, ´ıgy teljes marad´ekrendszert alkotnak. (ai , m) = 1 ∧ (a, m) = 1 ⇒ (a · ai , m) = 1. Tov´abb´a a · a1 , a · a2 ,. . . , a · aϕ(m) p´aronk´ent inkongruensek, sz´amuk ϕ(m) ⇔ reduk´alt marad´ekrendszert alkotnak.
19.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Euler-Fermat t´etel bizony´ıt´asa T´ etel (Euler-Fermat) (a, m) = 1 ⇒ aϕ(m) ≡ 1 (modm).
Bizony´ıt´as Legyen a1 , a2 , . . . , aϕ(m) egy reduk´alt marad´ekrendszer modulo m. Mivel (a, m) = 1 ⇒ a · a1 , a · a2 ,. . . , a · aϕ(m) szint´en reduk´alt marad´ekrendszer. Innen ϕ(m)
ϕ(m)
aϕ(m)
Y
aj =
j=1
Y j=1
ϕ(m)
a · aj ≡
Y
aj (modm).
j=1
ϕ(m)
Mivel
Y
aj relat´ıv pr´ım m-hez, ´ıgy egyszer˝ us´ıthet¨ unk vele:
j=1
aϕ(m) ≡ 1 (modm).
20.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Euler-Fermat t´etel T´ etel (Euler-Fermat) (a, m) = 1 ⇒ aϕ(m) ≡ 1 (modm)
P´elda Mi lesz a 3111 utols´o sz´amjegye tizes sz´amrendszerben? Mi lesz 3111 mod 10? ϕ(10) = 4 ⇒ 27 3 · 3 ≡ 127 · 33 = 33 = 27 ≡ 7 (mod 10) 3111 = 34·27+3 = 34 Oldjuk meg a 2x ≡ 5 (mod 7) kongruenci´at! ϕ(7) = 6. Szorozzuk be mindk´et oldalt 25 -nel. Ekkor ´ itt 5 · 25 = 5 · 32 ≡ 5 · 4 = 20 ≡ 6 ( mod 7). 5 · 25 ≡ 26 x ≡ x ( mod 7). Es Oldjuk meg a 23x ≡ 4 (mod 211) kongruenci´at! ϕ(211) = 210. Szorozzuk be mindk´et oldalt 23209 -nel. Ekkor ´ itt 4 · 23209 ≡ . . . (mod 211). 4 · 23209 ≡ 23210 x ≡ x (mod211). Es
21.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
Gyors hatv´anyoz´as Legyenek m, a, n pozit´ıv eg´eszek, m > 1. Szeretn´enk kisz´amolni an mod m marad´ekot hat´ekonyan. ´ azoljuk n-et 2-es sz´amrendszerben: Abr´ k X n= εi 2i = (εk εk−1 . . . ε1 ε0 )(2) , ahol ε0 , ε1 , . . . , εk ∈ {0, 1}. i=0
o j + 1 jegy ´altal meghat´arozott sz´am: Legyen nj (0 ≤ j ≤ k) az els˝ k−j nj = bn/2 c = (εk εk−1 . . . εk−j )(2) Ekkor meghat´arozzuk minden j-re az xj ≡ anj (modm) marad´ekot: n0 = εk = 1, x0 = a. nj = 2 · nj−1 + εk−j ⇒ 2 xj−1 mod m, ha εk−j = 0 2 xj = aεk−j xj−1 ⇒ mod m = 2 axj−1 mod m, ha εk−j = 1 xk = an mod m. Az algoritmus helyess´ege az al´abbi formul´abol k¨ ovetkezik (Biz.: HF): an = a
Pk
i=0
εi 2i
=
k Y i=0
a2
i
εi
2014. ˝ osz
22.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
Gyors hatv´anyoz´as P´elda Mi lesz 3111 mod 10? (Euler-Fermat ⇒ 7) 111(10) = 1101111(2) itt k = 6, a = 3, m = 10. j
nj
2 xj =aεk−j · xj−1
xj mod 10
0
1
–
3
1
11
x1 =3 · 32
7
2
2
110
x2 =7
9
3
1101
x3 =3 · 92
3
4
11011
x4 =3 · 32
7
2
5
110111
x5 =3 · 7
7
6
1101111
x6 =3 · 72
7
2014. ˝ osz
23.
Kongruenci´ ak
Diszkr´ et matematika I. k¨ oz´ epszint
Gyors hatv´anyoz´as P´elda Oldjuk meg a 23x ≡ 4 (mod 211) kongruenci´at! Euler-Fermat ⇒ x ≡ 4 · 23209 ≡ . . . (mod 211). Mi lesz 23209 mod 211? 209(10) = 11010001(2) itt k = 7, a = 23. j
nj
2 xj =aεk−j · xj−1
–
xj mod 211
0
1
1
11
x1 =23 · 232
140
23
2
110
x2 =1402
188
3
1101
x3 =23 · 1882
140
4
11010
x4 =1402
188
2
107
5
110100
x5 =188
6
1101000
x6 =1072
7
11010001
55 2
x6 =23 · 55
x ≡ 4 · 23209 ≡ 4 · 156 ≡ 202 (mod 211).
156
2014. ˝ osz
24.
