Lenka Zalabová. Ústav matematiky a biomatematiky, Přírodovědecká fakulta, Jihočeská univerzita. zima 2012

Deˇlitelnost

Grupy zbytkovyćh trˇ´ıd

Jedna z mnoha aplikacı´ zbytkovyćh trˇ´ıd

Algebra - trˇetı´ dı´l Lenka Zalabova´ ´ stav matematiky a biomatematiky, Prˇ´ırodoveˇdecka´ fakulta, Jihocˇeska´ univerzita U ˇ eskyćh Budeˇjovicıćh vC

zima 2012

Deˇlitelnost


Obsah

1

Deˇlitelnost

2


3

Jedna z mnoha aplikacı´ zbytkovyćh trˇ´ıd Hammingovy ko´dy


Deˇlitelnost


1

Deˇlitelnost

2


3



Deˇlitelnost



Deˇlitelnost celyćh cˇı´sel

Definition ˇ ekneme, zˇe cele´ cˇı´slo a deˇlı´ cele´ cˇı´slo b, jestlizˇe existuje cele´ R cˇı´slo q takove´, zˇe b = a · q. V takove´m prˇ´ıpadeˇ pı´sˇeme a | b. V opacˇne´m prˇ´ıpadeˇ ˇr´ıka´me, zˇe a nedeˇlı´ b, a pı´sˇeme a - b.

Deˇlitelnost




Definition ˇ ekneme, zˇe cele´ cˇı´slo a deˇlı´ cele´ cˇı´slo b, jestlizˇe existuje cele´ R cˇı´slo q takove´, zˇe b = a · q. V takove´m prˇ´ıpadeˇ pı´sˇeme a | b. V opacˇne´m prˇ´ıpadeˇ ˇr´ıka´me, zˇe a nedeˇlı´ b, a pı´sˇeme a - b. Example Platı´: 7 | 35 protozˇe 35 = 7 · 5,

Deˇlitelnost




Definition ˇ ekneme, zˇe cele´ cˇı´slo a deˇlı´ cele´ cˇı´slo b, jestlizˇe existuje cele´ R cˇı´slo q takove´, zˇe b = a · q. V takove´m prˇ´ıpadeˇ pı´sˇeme a | b. V opacˇne´m prˇ´ıpadeˇ ˇr´ıka´me, zˇe a nedeˇlı´ b, a pı´sˇeme a - b. Example Platı´: 7 | 35 protozˇe 35 = 7 · 5, 8 - 60,

Deˇlitelnost




Definition ˇ ekneme, zˇe cele´ cˇı´slo a deˇlı´ cele´ cˇı´slo b, jestlizˇe existuje cele´ R cˇı´slo q takove´, zˇe b = a · q. V takove´m prˇ´ıpadeˇ pı´sˇeme a | b. V opacˇne´m prˇ´ıpadeˇ ˇr´ıka´me, zˇe a nedeˇlı´ b, a pı´sˇeme a - b. Example Platı´: 7 | 35 protozˇe 35 = 7 · 5, 8 - 60, −2 | 6,

Deˇlitelnost




Definition ˇ ekneme, zˇe cele´ cˇı´slo a deˇlı´ cele´ cˇı´slo b, jestlizˇe existuje cele´ R cˇı´slo q takove´, zˇe b = a · q. V takove´m prˇ´ıpadeˇ pı´sˇeme a | b. V opacˇne´m prˇ´ıpadeˇ ˇr´ıka´me, zˇe a nedeˇlı´ b, a pı´sˇeme a - b. Example Platı´: 7 | 35 protozˇe 35 = 7 · 5, 8 - 60, −2 | 6, 5 - −71, ...

Deˇlitelnost


Neˇjake´ vlastnosti

1

Platı´ a | a pro kazˇde´ a 6= 0, a ∈ Z.


Deˇlitelnost




1


2

Pokud a | b a za´rovenˇ b | c pro neˇjaka´ a, b, c ∈ Z, pak take´ a | c.

Deˇlitelnost




1


2


3

Pokud a | b a za´rovenˇ a | c pro neˇjaka´ a, b, c ∈ Z, pak take´ a | (bx + cy) pro kazˇde´ x, y ∈ Z.

Deˇlitelnost




1


2


3


4

Pokud a | b pro neˇjaka´ a ∈ Z a b 6= 0, b ∈ Z, pak take´ |a| ≤ |b|.

Deˇlitelnost




1


2


3


4


5

Pokud a | b, pak take´ an | b n pro kazˇde´ n ∈ N,

Deˇlitelnost




1


2


3


4


5 6

Pokud a | b, pak take´ an | b n pro kazˇde´ n ∈ N, Pokud a | b a za´rovenˇ b | a pro neˇjaka´ a 6= 0, b 6= 0, a, b ∈ Z, pak |a| = |b|.

Deˇlitelnost



Deˇlenı´ se zbytkem Theorem Meˇjme cela´ cˇı´sla a > 0 a b ≥ 0. Pak existuje jedina´ dvojice celyćh cˇı´sel q, r takovyćh, zˇe q ≥ 0,

Deˇlitelnost



Deˇlenı´ se zbytkem Theorem Meˇjme cela´ cˇı´sla a > 0 a b ≥ 0. Pak existuje jedina´ dvojice celyćh cˇı´sel q, r takovyćh, zˇe q ≥ 0, 0 ≤ r < a,

Deˇlitelnost



Deˇlenı´ se zbytkem Theorem Meˇjme cela´ cˇı´sla a > 0 a b ≥ 0. Pak existuje jedina´ dvojice celyćh cˇı´sel q, r takovyćh, zˇe q ≥ 0, 0 ≤ r < a, b = a · q + r. Proof: ...

Deˇlitelnost



Deˇlenı´ se zbytkem Theorem Meˇjme cela´ cˇı´sla a > 0 a b ≥ 0. Pak existuje jedina´ dvojice celyćh cˇı´sel q, r takovyćh, zˇe q ≥ 0, 0 ≤ r < a, b = a · q + r. Proof: ... q ... podı´l po deˇlenı´ cˇı´sla b cˇı´slem a r ... zbytek po deˇlenı´ cˇı´sla b cˇı´slem a

Deˇlitelnost



Deˇlenı´ se zbytkem Theorem Meˇjme cela´ cˇı´sla a > 0 a b ≥ 0. Pak existuje jedina´ dvojice celyćh cˇı´sel q, r takovyćh, zˇe q ≥ 0, 0 ≤ r < a, b = a · q + r. Proof: ... q ... podı´l po deˇlenı´ cˇı´sla b cˇı´slem a r ... zbytek po deˇlenı´ cˇı´sla b cˇı´slem a Example Pro a = 7 a b = 36 dostaneme q = 5 a r = 1, t.j. 36 = 7 · 5 + 1.

Deˇlitelnost



Nejveˇtsˇ´ı spolecˇny´ deˇlitel

Definition Spolecˇny´ deˇlitel celyćh cˇı´sel a, b je cele´ cˇı´slo c takove´, zˇe c | b a za´rovenˇ c | a. Nejveˇtsˇ´ı cˇı´slo s touto vlastnostı´ se nazy´va´ nejveˇtsˇ´ı spolecˇny´ deˇlitel cˇı´sel a, b. Oznacˇujeme jej NSD(a, b). ˇ ´ısla a, b se nazy´vajı´ nesoudeˇlna´, jestlizˇe NSD(a, b) = 1. C

Deˇlitelnost



Eukleidu˚v algoritmus

Jedna´ se o algoritmus pro nalezenı´ nejveˇtsˇ´ıho spolecˇne´ho deˇlitele dvou prˇirozenyćh cˇı´sel. Protozˇe platı´: NSD(0, 0) neexistuje, NSD(0, b) = |b| pro b 6= 0,b ∈ Z, NSD(a, b) = NSD(|a|, |b|) pro a 6= 0, b 6= 0; a, b ∈ Z,

mu˚zˇeme pouzˇ´ıt Eukleidu˚v algoritmus k nalezenı´ nejveˇtsˇ´ıho spolecˇne´ho deˇlitele dvou celyćh cˇı´sel.

Deˇlitelnost



Eukleidu˚v algoritmus Meˇjme prˇirozena´ cˇı´sla a, b a prova´deˇjme postupneˇ deˇlenı´ se zbytkem : a = b · q0 + r0 b = r0 · q1 + r1 r0 = r1 · q2 + r2 r1 = r2 · q3 + r3 .. . rn−3 = rn−2 · qn−1 + rn−1 rn−2 = rn−1 · qn + rn rn−1 = rn · qn+1 Poneˇvadzˇ b > r0 > r1 > r2 . . . , skutecˇneˇ existuje n takove´, zˇe rn | rn−1 , tedy rn+1 = 0.

Deˇlitelnost


Eukleidu˚v algoritmus

Theorem NSD(a, b) = rn . Proof: ...


Deˇlitelnost


Neˇjake´ prˇ´ıklady

Najdeˇte nejveˇtsˇ´ıho spolecˇne´ho deˇlitele cˇı´sel: 1

125, 36

2

121, 4593

3

−9, 279

4

315, 427


Deˇlitelnost



Bezoutova rovnost

Theorem Pro libovolna´ cela´ cˇı´sla a, b existujı´ cela´ cˇı´sla u, v takova´, zˇe a · u + b · v = NSD(a, b). Proof: ...

Deˇlitelnost



Bezoutova rovnost

Theorem Pro libovolna´ cela´ cˇı´sla a, b existujı´ cela´ cˇı´sla u, v takova´, zˇe a · u + b · v = NSD(a, b). Proof: ... Example Pro a = 6 a b = 4 dostaneme NSD(a, b) = 2 a platı´ 2 = 6 · 3 + 4 · (−4).

Deˇlitelnost



Neˇjake´ dalsˇ´ı prˇ´ıklady

Najdeˇte nejveˇtsˇ´ı spolecˇny´ deˇlitel cˇı´sel a koeficienty v prˇ´ıslusˇne´ Bezoutovy rovnosti. 1

168, 90

2

675, 1107

3

4597, 2

Deˇlitelnost



Du˚lezˇite´ du˚sledky

Corollary Cela´ cˇı´sla a, b jsou nesoudeˇlna´, pra´veˇ kdyzˇ existujı´ cela´ cˇı´sla u, v takova´, zˇe a · u + b · v = 1. Proof: ...

Deˇlitelnost



Du˚lezˇite´ du˚sledky

Corollary Cela´ cˇı´sla a, b jsou nesoudeˇlna´, pra´veˇ kdyzˇ existujı´ cela´ cˇı´sla u, v takova´, zˇe a · u + b · v = 1. Proof: ... Corollary Jestlizˇe pro cela´ cˇı´sla a, b, c platı´ a | b · c a NSD(a, b) = 1, pak a | c. Proof: ...

Deˇlitelnost



Prvocˇı´sla

Definition Prˇirozene´ cˇı´slo p > 1 se nazy´va´ prvocˇı´slo, jestlizˇe jeho jediny´m deˇlitelem veˇtsˇ´ım nezˇ 1 je p samotne´.

Deˇlitelnost



Prvocˇı´sla

Definition Prˇirozene´ cˇı´slo p > 1 se nazy´va´ prvocˇı´slo, jestlizˇe jeho jediny´m deˇlitelem veˇtsˇ´ım nezˇ 1 je p samotne´. Theorem 1

Libovolne´ prˇirozene´ cˇı´slo a > 1 je bud’ prvocˇı´slo, nebo jej lze pra´veˇ jednı´m zpu˚sobem rozlozˇit na soucˇin prvocˇı´sel.

2

Prvocˇı´sel je nekonecˇneˇ mnoho.

Proof: ...

Deˇlitelnost


1

Deˇlitelnost

2


3



Deˇlitelnost



Kongruence

Definition Bud’ n prˇirozene´ cˇı´slo. Dveˇ cela´ cˇı´sla a, b se nazy´vajı´ kongruentnı´ podle modulu n, jestlizˇe n | a − b. Pı´sˇeme a≡b

mod n.

Deˇlitelnost



Kongruence

Definition Bud’ n prˇirozene´ cˇı´slo. Dveˇ cela´ cˇı´sla a, b se nazy´vajı´ kongruentnı´ podle modulu n, jestlizˇe n | a − b. Pı´sˇeme a≡b

mod n.

25 ≡ 7

mod 6,

Example Platı´ protozˇe 6 | 25 − 7 = 18.

Deˇlitelnost



Zbytkove´ trˇ´ıdy Definition Bud’ n prˇirozene´ cˇı´slo. Mnozˇiny [a]n = {a + k · n : k ∈ Z}, kde a ∈ Z, se nazy´vajı´ zbytkove´ trˇ´ıdy podle modulu n.

Deˇlitelnost



Zbytkove´ trˇ´ıdy Definition Bud’ n prˇirozene´ cˇı´slo. Mnozˇiny [a]n = {a + k · n : k ∈ Z}, kde a ∈ Z, se nazy´vajı´ zbytkove´ trˇ´ıdy podle modulu n. Example [7]6 = {7 + k · 6 : k ∈ Z} = {. . . , −11, −5, 1, 7, 13, 19, 25, 31, . . . }

Deˇlitelnost



Zbytkove´ trˇ´ıdy Definition Bud’ n prˇirozene´ cˇı´slo. Mnozˇiny [a]n = {a + k · n : k ∈ Z}, kde a ∈ Z, se nazy´vajı´ zbytkove´ trˇ´ıdy podle modulu n. Example [7]6 = {7 + k · 6 : k ∈ Z} = {. . . , −11, −5, 1, 7, 13, 19, 25, 31, . . . } Mnozˇinu vsˇech zbytkovyćh trˇ´ıd podle modulu n oznacˇujeme symbolem Zn .

Deˇlitelnost



Jaky´ je vztah kongruencı´ a zbytkovyćh trˇ´ıd?

Theorem [a]n = [b]n Proof: ...

pra´veˇ kdyzˇ

a≡b

mod n.

Deˇlitelnost



Du˚sledky Zbytkove´ trˇ´ıdy podle modulu n nejsou navza´jem ru˚zne´. Neboli: Ru˚zna´ cˇı´sla mohou zada´vat stejnou zbytkovou trˇ´ıdu modulo n.

Deˇlitelnost



Du˚sledky Zbytkove´ trˇ´ıdy podle modulu n nejsou navza´jem ru˚zne´. Neboli: Ru˚zna´ cˇı´sla mohou zada´vat stejnou zbytkovou trˇ´ıdu modulo n. Example Protozˇe platı´, 25 ≡ 7 mod 6, pak platı´ i [7]6 = [25]6 . Tedy 25 a 7 zada´vajı´ stejnou zbytkovou trˇ´ıdu podle modulu 6.

Deˇlitelnost



Du˚sledky Zbytkove´ trˇ´ıdy podle modulu n nejsou navza´jem ru˚zne´. Neboli: Ru˚zna´ cˇı´sla mohou zada´vat stejnou zbytkovou trˇ´ıdu modulo n. Example Protozˇe platı´, 25 ≡ 7 mod 6, pak platı´ i [7]6 = [25]6 . Tedy 25 a 7 zada´vajı´ stejnou zbytkovou trˇ´ıdu podle modulu 6. Zbytkova´ trˇ´ıda [a]n se rovna´ zbytkove´ trˇ´ıdeˇ [r ]n , kde r je zbytek po deˇlenı´ cˇı´sla a cˇı´slem n.

Deˇlitelnost



Du˚sledky Zbytkove´ trˇ´ıdy podle modulu n nejsou navza´jem ru˚zne´. Neboli: Ru˚zna´ cˇı´sla mohou zada´vat stejnou zbytkovou trˇ´ıdu modulo n. Example Protozˇe platı´, 25 ≡ 7 mod 6, pak platı´ i [7]6 = [25]6 . Tedy 25 a 7 zada´vajı´ stejnou zbytkovou trˇ´ıdu podle modulu 6. Zbytkova´ trˇ´ıda [a]n se rovna´ zbytkove´ trˇ´ıdeˇ [r ]n , kde r je zbytek po deˇlenı´ cˇı´sla a cˇı´slem n. Example Protozˇe platı´ 25 = 6 · 4 + 1, dostaneme [25]6 = [1]6 . Analogicky, protozˇe 7 = 6 · 1 + 1, dostaneme [7]6 = [1]6 .

Deˇlitelnost



Du˚sledky Tedy [rn ] se skla´da´ ze vsˇech cˇı´sel, jejichzˇ zbytek po deˇlenı´ cˇı´slem n je roven cˇı´slu r .

Deˇlitelnost



Du˚sledky Tedy [rn ] se skla´da´ ze vsˇech cˇı´sel, jejichzˇ zbytek po deˇlenı´ cˇı´slem n je roven cˇı´slu r . Example [1]6 = {1 + k · 6 : k ∈ Z} = {. . . , −11, −5, 1, 7, 13, 19, 25, 31, . . . }

Deˇlitelnost



Du˚sledky Tedy [rn ] se skla´da´ ze vsˇech cˇı´sel, jejichzˇ zbytek po deˇlenı´ cˇı´slem n je roven cˇı´slu r . Example [1]6 = {1 + k · 6 : k ∈ Z} = {. . . , −11, −5, 1, 7, 13, 19, 25, 31, . . . } Platı´ Zn = {[0]n , [1]n , [2]n , . . . , [n − 2]n , [n − 1]n }.

Deˇlitelnost



Du˚sledky Tedy [rn ] se skla´da´ ze vsˇech cˇı´sel, jejichzˇ zbytek po deˇlenı´ cˇı´slem n je roven cˇı´slu r . Example [1]6 = {1 + k · 6 : k ∈ Z} = {. . . , −11, −5, 1, 7, 13, 19, 25, 31, . . . } Platı´ Zn = {[0]n , [1]n , [2]n , . . . , [n − 2]n , [n − 1]n }. Example Z6 = {[0]6 , [1]6 , [2]6 , [3]6 , [4]6 , [5]6 }.

Deˇlitelnost



Motivace ze Z2

Ma´me Z2 = {[0]2 , [1]2 }, kde [0]2 = {. . . , −4, −2, 0, 2, 4, . . . } je mnozˇina sudyćh cˇı´sel, [1]2 = {. . . , −3, −1, 1, 3, 5, . . . } je mnozˇina lichyćh cˇı´sel.

Deˇlitelnost



Motivace ze Z2

Ma´me Z2 = {[0]2 , [1]2 }, kde [0]2 = {. . . , −4, −2, 0, 2, 4, . . . } je mnozˇina sudyćh cˇı´sel, [1]2 = {. . . , −3, −1, 1, 3, 5, . . . } je mnozˇina lichyćh cˇı´sel. Prˇi pocˇı´tańı´ se sudy´mi s lichy´mi cˇı´sly platı´ na´sledujıćı´ pravidla: sude´ + sude´ =

Deˇlitelnost



Motivace ze Z2

Ma´me Z2 = {[0]2 , [1]2 }, kde [0]2 = {. . . , −4, −2, 0, 2, 4, . . . } je mnozˇina sudyćh cˇı´sel, [1]2 = {. . . , −3, −1, 1, 3, 5, . . . } je mnozˇina lichyćh cˇı´sel. Prˇi pocˇı´tańı´ se sudy´mi s lichy´mi cˇı´sly platı´ na´sledujıćı´ pravidla: sude´ + sude´ = sude´,

Deˇlitelnost



Motivace ze Z2

Ma´me Z2 = {[0]2 , [1]2 }, kde [0]2 = {. . . , −4, −2, 0, 2, 4, . . . } je mnozˇina sudyćh cˇı´sel, [1]2 = {. . . , −3, −1, 1, 3, 5, . . . } je mnozˇina lichyćh cˇı´sel. Prˇi pocˇı´tańı´ se sudy´mi s lichy´mi cˇı´sly platı´ na´sledujıćı´ pravidla: sude´ + sude´ = sude´, sude´ + liche´ =

Deˇlitelnost



Motivace ze Z2

Ma´me Z2 = {[0]2 , [1]2 }, kde [0]2 = {. . . , −4, −2, 0, 2, 4, . . . } je mnozˇina sudyćh cˇı´sel, [1]2 = {. . . , −3, −1, 1, 3, 5, . . . } je mnozˇina lichyćh cˇı´sel. Prˇi pocˇı´tańı´ se sudy´mi s lichy´mi cˇı´sly platı´ na´sledujıćı´ pravidla: sude´ + sude´ = sude´, sude´ + liche´ = liche´,

Deˇlitelnost



Motivace ze Z2

Ma´me Z2 = {[0]2 , [1]2 }, kde [0]2 = {. . . , −4, −2, 0, 2, 4, . . . } je mnozˇina sudyćh cˇı´sel, [1]2 = {. . . , −3, −1, 1, 3, 5, . . . } je mnozˇina lichyćh cˇı´sel. Prˇi pocˇı´tańı´ se sudy´mi s lichy´mi cˇı´sly platı´ na´sledujıćı´ pravidla: sude´ + sude´ = sude´, sude´ + liche´ = liche´, liche´ + liche´ =

Deˇlitelnost



Motivace ze Z2

Ma´me Z2 = {[0]2 , [1]2 }, kde [0]2 = {. . . , −4, −2, 0, 2, 4, . . . } je mnozˇina sudyćh cˇı´sel, [1]2 = {. . . , −3, −1, 1, 3, 5, . . . } je mnozˇina lichyćh cˇı´sel. Prˇi pocˇı´tańı´ se sudy´mi s lichy´mi cˇı´sly platı´ na´sledujıćı´ pravidla: sude´ + sude´ = sude´, sude´ + liche´ = liche´, liche´ + liche´ = sude´,

Deˇlitelnost



Motivace ze Z2


sude´ · sude´ =

Deˇlitelnost



Motivace ze Z2


sude´ · sude´ = sude´,

Deˇlitelnost



Motivace ze Z2


sude´ · sude´ = sude´, sude´ · liche´ =

Deˇlitelnost



Motivace ze Z2


sude´ · sude´ = sude´, sude´ · liche´ = sude´,

Deˇlitelnost



Motivace ze Z2


sude´ · sude´ = sude´, sude´ · liche´ = sude´, liche´ · liche´ =

Deˇlitelnost



Motivace ze Z2


sude´ · sude´ = sude´, sude´ · liche´ = sude´, liche´ · liche´ = liche´.

Deˇlitelnost



Motivace ze Z2

Toto lze realizovat pomocı´ scˇı´tańı´ a na´sobenı´ na Z2 na´sledujıćı´m zpu˚sobem: + [0]2 [1]2

[0]2 [0]2 [1]2

[1]2 [1]2 [0]2

· [0]2 [1]2

[0]2 [0]2 [0]2

[1]2 [0]2 [1]2

Deˇlitelnost



Motivace ze Z2

Toto lze realizovat pomocı´ scˇı´tańı´ a na´sobenı´ na Z2 na´sledujıćı´m zpu˚sobem: + [0]2 [1]2

[0]2 [0]2 [1]2

[1]2 [1]2 [0]2

· [0]2 [1]2

[0]2 [0]2 [0]2

[1]2 [0]2 [1]2

Neboli: Soucˇet libovolnyćh dvou prvku˚ z [0]2 je vzˇdycky prvek [0]2 , soucˇet libovolne´ho prvku [0]2 s libovolny´m prvkem [1]2 je vzˇdy prvek [1]2 , atd.

Deˇlitelnost



Operace na zbytkovyćh trˇ´ıdaćh

Toto lze zobecnit na zbytkove´ trˇ´ıdy podle libovolne´ho modulu: Theorem Bud’ n prˇirozene´ cˇı´slo. Vztahy [a]n + [b]n = [a + b]n , [a]n · [b]n = [a · b]n definujı´ korektneˇ operace + a · na mnozˇineˇ Zn . Proof:

Deˇlitelnost



Operace na zbytkovyćh trˇ´ıdaćh

Toto lze zobecnit na zbytkove´ trˇ´ıdy podle libovolne´ho modulu: Theorem Bud’ n prˇirozene´ cˇı´slo. Vztahy [a]n + [b]n = [a + b]n , [a]n · [b]n = [a · b]n definujı´ korektneˇ operace + a · na mnozˇineˇ Zn . Proof: Uka´zˇeme, zˇe kdyzˇ [a]n = [c]n a [b]n = [d]n , pak [a + b]n = [c + d]n , [a · b]n = [c · d]n .

Deˇlitelnost



Grupa zbytkovyćh trˇ´ıd

Theorem Dvojice (Zn , +) tvorˇ´ı komutativnı´ grupu pro libovolne´ prˇirozene´ cˇı´slo n. Proof: ...

Deˇlitelnost



Pologrupa zbytkovyćh trˇ´ıd

Theorem Dvojice (Zn , ·) tvorˇ´ı komutativnı´ pologrupu s jednotkovy´m prvkem pro libovolne´ prˇirozene´ cˇı´slo n. Proof: ...

Deˇlitelnost



Inverze v (Zn , ·)

Theorem Bud’ n prˇirozene´ cˇı´slo a a cele´ cˇı´slo. Zbytkova´ trˇ´ıda [a]n ∈ Zn ma´ inverzi v (Zn , ·) pra´veˇ tehdy kdyzˇ cˇı´sla a, n jsou nesoudeˇlna´. Proof: ...

Deˇlitelnost




Rozhodneˇte, zda prvek [35]37 ma´ inverzi v (Z37 , ·). Pokud ano, najdeˇte ji.

Deˇlitelnost




Rozhodneˇte, zda prvek [35]37 ma´ inverzi v (Z37 , ·). Pokud ano, najdeˇte ji. Rozhodneˇte, zda prvek [12]52 ma´ inverzi v (Z52 , ·). Pokud ano, najdeˇte ji.

Deˇlitelnost



Grupa zbytkovyćh trˇ´ıd

Theorem Bud’ n prvocˇı´slo a symbolem Z∗n oznacˇme mnozˇinu vsˇech nenulovyćh zbytkovyćh trˇ´ıd podle modulu n, t.j. Zn = {[1]n , [2]n , . . . , [n − 2]n , [n − 1]n }. Pak (Z∗n , ·) je grupa. Proof: ...

Deˇlitelnost


1

Deˇlitelnost

2


3



Deˇlitelnost



Ko´dovańı´

Prˇena´sˇ´ıme-li zpra´vu neˇjaky´m kana´lem, v neˇmzˇ je sˇum, mu˚zˇe dojı´t ke zkreslenı´ zpra´vy. Ko´dovańı´ umozˇnˇuje odhalit, zda ke zkreslenı´ dosˇlo nebo dokonce opravit chyby. Efektivnı´ ko´d by meˇl umeˇt opravovat chyby (s urcˇitou pravdeˇpodobnostı´), nemeˇl by´t na´rocˇny´ (naprˇ´ıklad by nemeˇl vy´razneˇ prodluzˇovat vysı´lanou zpra´vu).

Efektivnı´ ko´dy opravujıćı´ chyby lze zı´skat pomocı´ konecˇnyćh grup.

Deˇlitelnost



Hammingovy ko´dy

Uvedeme dva prˇ´ıklady, ktere´ vyuzˇ´ıvajı´ Z2 . Budeme prˇedpokla´dat, zˇe zpra´va se skla´da´ ze cˇtyrˇcifernyćh cˇı´sel slozˇenyćh pouze z cifer 1 a 0. Jedna´ se o specia´lnı´ prˇ´ıpady ko´du˚, ktere´ vymyslel americky´ matematik Richard Hamming v roce 1950. Jedna´ se o tzv. linea´rnı´ ko´dy.

Deˇlitelnost



Prvnı´ prˇ´ıklad Uvazˇujme matici   1 0 1 0 1 0 1 H = 0 1 1 0 0 1 1 . 0 0 0 1 1 1 1 Meˇjme a, b, c, d ∈ Z2 a necht’ abcd je slovo, ktere´ chceme prˇene´st. Vytvorˇme vektor T C= x y a z b c d , kde x, y, z ∈ Z2 jsou takove´, zˇe x +a+b+d =0 y +a+c+d =0 z + b + c + d = 0. Tedy platı´ H · C = 0, kde soucˇin matic uvazˇujeme nad Z2 , t.j. scˇı´ta´me a na´sobı´me v Z2 .

Deˇlitelnost



Prvnı´ prˇ´ıklad Mı´sto abcd prˇenesme xyazbcd. Prˇedpokla´dejme, zˇe prˇ´ıjemce dostane vektor R. Mohou nastat tyto mozˇnosti:

Deˇlitelnost



Prvnı´ prˇ´ıklad Mı´sto abcd prˇenesme xyazbcd. Prˇedpokla´dejme, zˇe prˇ´ıjemce dostane vektor R. Mohou nastat tyto mozˇnosti: R = C ... Pak H · R = 0.

Deˇlitelnost



Prvnı´ prˇ´ıklad Mı´sto abcd prˇenesme xyazbcd. Prˇedpokla´dejme, zˇe prˇ´ıjemce dostane vektor R. Mohou nastat tyto mozˇnosti: R = C ... Pak H · R = 0. R se lisˇ´ı od C v jedne´ cifrˇe ... Pak H · R = neˇktery´ sloupec matice H. Navıć poloha sloupce urcˇuje pozici, ve ktere´ nastala chyba. Protozˇe sloupce H jsou navza´jem ru˚zne´, prˇ´ıjemce to zjistı´ jednoznacˇneˇ.

Deˇlitelnost



Prvnı´ prˇ´ıklad Mı´sto abcd prˇenesme xyazbcd. Prˇedpokla´dejme, zˇe prˇ´ıjemce dostane vektor R. Mohou nastat tyto mozˇnosti: R = C ... Pak H · R = 0. R se lisˇ´ı od C v jedne´ cifrˇe ... Pak H · R = neˇktery´ sloupec matice H. Navıć poloha sloupce urcˇuje pozici, ve ktere´ nastala chyba. Protozˇe sloupce H jsou navza´jem ru˚zne´, prˇ´ıjemce to zjistı´ jednoznacˇneˇ. R se lisˇ´ı od C ve vıće cifraćh ... Pak H · R = soucˇet neˇkolika sloupcu˚ matice H. Ten mu˚zˇe by´t nulovy´, nebo roven neˇjake´mu sloupci z H. Prˇ´ıjemce nezjistı´ nic.

Deˇlitelnost



Jak to funguje? Oznacˇme E := R − C rozdı´l mezi prˇijatou a vyslanou zpra´vou. Pro R = C + E pak platı´ H · R = H · C + H · E = 0 + H · E = H · E.

Deˇlitelnost



Jak to funguje? Oznacˇme E := R − C rozdı´l mezi prˇijatou a vyslanou zpra´vou. Pro R = C + E pak platı´ H · R = H · C + H · E = 0 + H · E = H · E. Pokud R = C, pak E je nulovy´ vektor a H · R = H · E = 0.

Deˇlitelnost



Jak to funguje? Oznacˇme E := R − C rozdı´l mezi prˇijatou a vyslanou zpra´vou. Pro R = C + E pak platı´ H · R = H · C + H · E = 0 + H · E = H · E. Pokud R = C, pak E je nulovy´ vektor a H · R = H · E = 0. Pokud R se lisˇ´ı od C v jedne´ cifrˇe, pak E je vektor, ktery´ ma´ jednicˇku na mı´steˇ, kde se stala chyba, jinak same´ nuly. Pak z vlastnostı´ na´sobenı´ matic plyne, zˇe H · R = H · E se rovna´ sloupci, ve ktere´m nastala chyba.

Deˇlitelnost



Jak to funguje? Oznacˇme E := R − C rozdı´l mezi prˇijatou a vyslanou zpra´vou. Pro R = C + E pak platı´ H · R = H · C + H · E = 0 + H · E = H · E. Pokud R = C, pak E je nulovy´ vektor a H · R = H · E = 0. Pokud R se lisˇ´ı od C v jedne´ cifrˇe, pak E je vektor, ktery´ ma´ jednicˇku na mı´steˇ, kde se stala chyba, jinak same´ nuly. Pak z vlastnostı´ na´sobenı´ matic plyne, zˇe H · R = H · E se rovna´ sloupci, ve ktere´m nastala chyba. Pokud R se lisˇ´ı od C ve vıće cifraćh, pak E je vektor, ktery´ ma´ jednicˇku na vsˇech mı´stech kde se stala chyba, jinak same´ nuly. Pak z vlastnostı´ na´sobenı´ matic plyne, zˇe H · R = H · E je rovno soucˇtu sloupcu˚ z H, jejichzˇ poloha odpovı´da´ poloze jednicˇek v E, t.j. poloze chyb. Ten mu˚zˇe by´t nulovy´, nebo roven sloupci z H.

Deˇlitelnost



Prvnı´ prˇ´ıklad

Prˇ´ıjemce deko´duje na´sledujıćı´m zpu˚sobem: Vypocˇı´ta´ H · R. Je-li vy´sledek nulovy´, cifra je prˇedańa spra´vneˇ. Je-li nenulovy´, zmeˇnı´ cifru na indikovane´m mı´steˇ. Pokud nenı´ vıć nezˇ jedna chyba v cifrˇe, pak prˇ´ıjemce dostal spra´vnou zpra´vu.

Deˇlitelnost



Druhy´ prˇ´ıklad Uvazˇujme matici  1 0 H= 0 0

1 1 0 0

1 0 1 0

1 1 1 0

1 0 0 1

1 1 0 1

1 0 1 1

 1 1 . 1 1

Meˇjme a, b, c, d ∈ Z2 a necht’ abcd je slovo, ktere´ chceme prˇene´st. Vytvorˇme vektor C= w tak, aby H · C = 0.

x y

a z b c d

T

,

Deˇlitelnost



Druhy´ prˇ´ıklad

Oznacˇme R vektor, ktery´ dostal prˇ´ıjemce. Nastanou tyto mozˇnosti:

Deˇlitelnost




Oznacˇme R vektor, ktery´ dostal prˇ´ıjemce. Nastanou tyto mozˇnosti: R = C ... Pak H · R = 0.

Deˇlitelnost




Oznacˇme R vektor, ktery´ dostal prˇ´ıjemce. Nastanou tyto mozˇnosti: R = C ... Pak H · R = 0. R se lisˇ´ı od C v jedne´ cifrˇe ... Opravı´me ji jako v prvnı´m prˇ´ıkladeˇ.

Deˇlitelnost




Oznacˇme R vektor, ktery´ dostal prˇ´ıjemce. Nastanou tyto mozˇnosti: R = C ... Pak H · R = 0. R se lisˇ´ı od C v jedne´ cifrˇe ... Opravı´me ji jako v prvnı´m prˇ´ıkladeˇ. R se lisˇ´ı od C ve dvou cifraćh ... Pak H · R = soucˇet dvou sloupcu˚ z H. Ten na prvnı´m mı´steˇ ma´ 1 + 1 = 0 a nenı´ to tedy sloupec z H. Prˇ´ıjemce pozna´ chyby, ale nevı´, kde se nacha´zejı´.

Lenka Zalabová. Ústav matematiky a biomatematiky, Přírodovědecká fakulta, Jihočeská univerzita. zima 2012

Recommend Documents