Základy teorie čísel. Základy diskrétní matematiky, BI-ZDM

Základy teorie čísel doc. RNDr. Josef Kolář, CSc. Katedra teoretické informatiky FIT České vysoké učení technické v Praze c

Josef Kolar, 2012

Základy diskrétní matematiky, BI-ZDM ZS 2012/13, Lekce 11 https://edux.fit.cvut.cz/courses/BI-ZDM/

Evropský sociální fond. Praha & EU: Investujeme do vaší budoucnosti doc. Josef Kolář (FIT ČVUT)

Základy teorie čísel

ZDM, ZS 20112/13, Lekce 11

1 / 32

Dělitelnost

Začneme v antice . . . Teorie čísel je odvětví matematiky, které se zabývá vlastnostmi čísel. Jedná se o jedno z nejstarších odvětví matematiky - lidé řešili číselně-teoretické problémy již před naším letopočtem. Ukázka některých klasických tvrzení z TČ: 1

Prvočísel je nekonečně mnoho.

2

Odmocnina ze dvou je iracionální.

Teorie čísel se vyznačuje tím, že otázku lze velice jednoduše a srozumitelně formulovat a o odpovědi platí většinou pravý opak. Podle používaných metod většinou rozlišujeme algrebraickou, analytickou, geometrickou a kombinatorickou teorii čísel. doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

2 / 32

Dělitelnost

Ukázky aplikace Teorie čísel dlouho neměla velké aplikace v jiných odvětvích. Významné aplikace byly objeveny až ve 20. století, patří mezi ně kryptografie - RSA . . . teorie kódování - komprese, oprava chyb, . . . statistická mechanika - Riemannova zeta funkce, Möbiova funkce . . . diofantické rovnice - polynomiální rovnice, která dovoluje proměnným nabývat pouze hodnot z oboru celých čísel generátory náhodných čísel - lineární kongruentní generátor nestandardní numerační systémy - radix 4 SRT algorithm v procesoru Pentium ...

doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

3 / 32

Dělitelnost

Dělitelnost Mezi základní vlastnosti celých čísel patří to, že některá čísla dělí (beze zbytku) jiná čísla.

Definice 1 (Dělitelnost) Nechť a, b ∈ Z. Řekneme, že a dělí b, značíme a|b, jestliže existuje k ∈ Z takové, že b = k.a. V takovem případě říkáme, že a je faktor b a b je násobek a, také říkáme, že b je dělitelné a. Pokud a nedělí b, píšeme a ∤ b. Co víme o (relaci) dělitelnosti? Pro každé n ∈ Z platí 1|n, n|n a n|0. Je to relace (částečného) uspořádání na N a N+ (ale ne na Z). (RE): platí n|n (TR): když a|b a b|c, pak a|c (ANS): když a|b a b|a, pak a = b (neplatí pro Z) doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

4 / 32

Dělitelnost

Dělitelnost Věta 2 Nechť a, b, c ∈ Z. 1

Jestliže a|b a a|c, pak a|(b + c).

2

Jestliže a|b, pak a|(nb) pro všechna n ∈ Z.

3

a|b právě tehdy, když |a| | |b|.

4

Jestliže a|b a b 6= 0, tak |a| ≤ |b|.

Důkaz: 1

(a|b)∧(a|c) ⇔ (b = k.a)∧(c = l.a) ⇒ b+c = (k +l).a ⇔ a|(b+c)

2

a|b ⇔ b = k.a ⇒ n.b = n.k.a ⇒ a|(nb) pro n ∈ Z

3

a|b ⇔ b = k.a ⇒ |b| = |k|.|a| ⇔ |a| | |b| (nazpět podobně)

4

a|b ⇔ b = k.a ⇒ (pro b 6= 0) k 6= 0, celé ⇒ |k| ≥ 1 ⇒ ⇒ |b| = |k|.|a| ≥ |a|



ZDM, ZS 20112/13, Lekce 11

5 / 32

Dělitelnost

Dělitelnost - další vlastnosti Věta 3 Nechť a, b, c ∈ Z. 1

Platí, že a|b a a|c právě tehdy, když a|(mb + nc) pro všechna m, n ∈ Z.

2

Jestliže a|(b + c) a současně a|b, pak a|c.

Důkaz: 1

⇒ : a|b ∧ a|c ⇔ b = ka ∧ c = la ⇒ mb + nc = mka + nla = (mk + nl)a ⇒ a|(mb + nc) ⇐ : a|(mb + nc) ⇒ a|b ∧ a|c (pro m = 1, n = 0, resp. m = 0, n = 1)

2

a|(b + c) ∧ a|b ⇔ (použitím části 1) a|(m(b + c) + nb) ⇒ ⇒ a|((1.(b + c) + (−1)b) ⇒ a|c



ZDM, ZS 20112/13, Lekce 11

6 / 32

Dělitelnost

Dělení se zbytkem Věta 4 (O dělení se zbytkem) Nechť a ∈ Z a d ∈ N+ . Pak existují q ∈ Z a r ∈ N taková, že a = qd + r a 0 ≤ r < d. Čísla q ( celočíselný podíl) a r ( zbytek po dělení a číslem d) jsou jednoznačně určena. Důkaz: Uvažujme množinu M = {a − qd; q ∈ Z, a − qd ≥ 0}. Tato množina je neprázdná - jestliže je a ≥ 0, stačí vzít q = 0, jestliže je a < 0, pak stačí zvolit q = −a a dostaneme a − qd = a(1 − d) ≥ 0, neboť d ≥ 1, takže (1 − d) ≤ 0. Všechny prvky M jsou nezáporná celá čísla, takže M má nejmenší prvek r. Evidentně r ≥ 0 a a = q0 d + r pro nějaké q0 ∈ Z. Dále platí r < d, neboť kdyby bylo r = a − q0 d ≥ d, pak r1 = r − d = a − (q0 + 1)d ≥ 0, tedy r1 ∈ M a současně r1 < r, což je spor s tím, že r je nejmenší prvek M . Proto r ≥ d nemůže nastat. Jednoznačnost se dokáže podobně. doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

7 / 32

Dělitelnost

Společný dělitel, společný násobek Definice 5 (Společný dělitel, společný násobek) Nechť a, b ∈ Z. 1

Číslo d ∈ N+ je společný dělitel čísel a, b, jestliže d|a a d|b.

2

Pokud je aspoň jedno z čísel a, b nenulové, nazýváme největším společným dělitelem čísel a, b takové číslo d ∈ N+ , které je největší z jejich společných dělitelů (píšeme d = gcd(a, b)). Pro nulová a, b definujeme gcd(0, 0) = 0.

3

Čísla a, b nazýváme nesoudělná, jestliže gcd(a, b) = 1.

4

Číslo n ∈ N+ je společný násobek čísel a, b, jestliže a|n a b|n.

5

Pokud je aspoň jedno z čísel a, b nenulové, nazýváme nejmenším společným násobkem čísel a, b takové číslo n ∈ N+ , které je nejmenší z jejich společných násobků (píšeme n = lcm(a, b)). Pro nulová a, b definujeme lcm(0, 0) = 0.



ZDM, ZS 20112/13, Lekce 11

8 / 32

Dělitelnost

Společný dělitel, společný násobek POZOR: Největší společný dělitel i nejmenší společný násobek jsou vždy přirozená (tj. nezáporná) čísla.

Příklad 6 Příklady na gcd a lcm: gcd(8, 12) = gcd(−8, 12) = gcd(8, −12) = gcd(−8, −12) = 4 gcd(8, 0) = gcd(−8, 0) = 8,

gcd(0, −12) = gcd(0, 12) = 12

lcm(8, 12) = lcm(−8, 12) = lcm(8, −12) = lcm(−8, −12) = 24 lcm(8, 0) = lcm(−8, 0) = 8,

lcm(0, −12) = lcm(0, 12) = 12

gcd(8, 12). lcm(8, 12) = 4.24 = 96 (= 8.12) gcd(0, 0) = lcm(0, 0) = 0 Zjištění: Nadále můžeme v operacích gcd a lcm uvažovat pouze přirozená čísla. doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

9 / 32

Dělitelnost

Vlastnosti gcd a lcm Věta 7 (Vlastnosti gcd a lcm) Nechť a, b, n ∈ Z. 1

Jestliže je n společný násobek a, b, pak lcm(a, b) dělí n.

2

Jestliže a|n a b|n, pak lcm(a, b)|n.

3

Platí, že gcd(a, b) = gcd(|a|, |b|) a lcm(a, b) = lcm(|a|, |b|)

Důkaz: 1

Nechť m = lcm(a, b) je nejmenší společný násobek, musí tedy platit n ≥ m. Podle věty o dělení máme n = qm + r. Protože a dělí m, tak dělí i qm. Dělí rovněž n, proto podle části 2 Věty 3 o dělení musí a také dělit r. Totéž platí pro b, navíc r ∈ N , takže buď r = 0 nebo je r společným násobkem a, b, což není možné, neboť m je nejmenší společný násobek a r < m. Takže r = 0 a n = qm pro nějaké q ∈ Z.

2

a|n ∧ b|n ⇒ a| |n| ∧ b| |n| ⇒ lcm(a, b)| |n| ⇒ lcm(a, b)|n

3

Plyne z faktu, že čísla a, b i |a|, |b| mají stejnou množinu společných dělitelů i společných násobků.



ZDM, ZS 20112/13, Lekce 11

10 / 32

Dělitelnost

Vlastnosti gcd Věta 8 Nechť a, b ∈ Z a označme d = gcd (a, b). Potom platí: 1

gcd (a/d, b/d) = 1

2

gcd (a + cb, b) = gcd (a, b) pro libovolné c ∈ Z

Důkaz: 1 Nechť d = gcd (a, b) = d, ukážeme, že a/d a b/d nemají jiný společný kladný dělitel než 1. Nechť je e ∈ N+ a platí e|(a/d) a e|(b/d), potom existují taková k, l ∈ Z, pro která platí a/d = ke a b/d = le a tedy a = dek a b = del, takže de je společným dělitelem a a b. d je ale největší společný dělitel a a b, takže de ≤ d, tím pádem e = 1, což znamená gcd (a/d, b/d) = 1. 2 Když nějaké celé číslo e dělí a i b, potom e|(a + cb). Společní dělitelé b a (a + cb) jsou stejná čísla jako společní dělitelé a a b - tedy i gcd (a + cb, b) = gcd (a, b). doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

11 / 32

Dělitelnost

Vyjádření gcd Ukážeme, že největší společný dělitel celých nenulových čísel a a b je vyjádřen součtem ma + nb, kde m a n jsou celá čísla.

Věta 9 Největší společný dělitel celých nenulových čísel a a b je nejmenší kladné celé číslo, které je lineární kombinací a a b. Důkaz: Nechť d je nejmenší kladné číslo, které lze vyjádřit jako lineární kombinací a a b. (Minimálně jedno takové kladné číslo existuje, protože jedna ze dvou lineárních kombinací 1a + 0b = a a (−1)a + 0b = −a, kde a 6= 0, je kladná.) Mějme tedy d = ma + nb, kde m a n jsou celá čísla. Ukážeme, že d|a a d|b. Z algoritmu pro dělení plyne a = dq + r, 0 ≤ r < d. doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

12 / 32

Dělitelnost

Pokračování důkazu Z předchozích dvou rovnic pro r (tj. d = ma + nb, a = dq + r, kde 0 ≤ r < d) odvodíme vztah r = a − dq = a − q(ma + nb) = (1 − qm)a − qnb. Z toho plyne, že r je lineární kombinací a a b. Protože 0 ≤ r < d a d je nejmenší kladná lineární kombinace a a b, musí být r = 0, a tedy d|a. Podobným způsobem lze ukázat, že platí d|b, takže d je společným dělitelem a a b. Dále dokážeme, že d je největším společným dělitelem a a b. Toto tvrzení platí, pokud každý společný dělitel c čísel a a b dělí také d. Nechť tedy c|a a c|b, potom podle vlastností dělitelnosti c dělí libovolnou lineární kombinaci hodnot a a b, tedy platí c|d.



ZDM, ZS 20112/13, Lekce 11

13 / 32

Dělitelnost

Eukleidův algoritmus Vývojem algoritmu pro nalezení gcd dvou kladných celých čísel se zabýval řecký matematik Eukleides (narozen cca 350 let pnl.). Jeho metoda je známa jako Eukleidův algoritmus (EA).

Věta 10 Eukleidův algoritmus Nechť a, b jsou celá čísla, pro která platí a ≥ b > 0. Nechť {rn }k+1 n=0 je klesající posloupnost zbytků definovaná rekurentním vztahem rn+2 = rn mod rn+1 s počátečními podmínkami r0 = a, r1 = b. kde rk+1 = 0 pro (k > 0) je její první nulový člen. Potom její poslední nenulový člen (tj. poslední nenulový zbytek) je největším společným dělitelem a a b, tedy gcd (a, b) = rk . Symbol mod vyjadřuje operaci zbytku po dělení dvou přirozených čísel (viz Věta 4 o dělení se zbytkem). doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

14 / 32

Dělitelnost

Eukleidův algoritmus Důkaz: Podle Věty o dělení se zbytkem je posloupnost zbytků {rn } od svého členu r1 klesající a platí r0 = r1 q1 + r2 (r2 = r0 mod r1 ) 0 ≤ r 2 < r1 r1 = r2 q2 + r3 (r3 = r1 mod r2 ) 0 ≤ r 3 < r2 .. . rk−2 = rk−1 qk−1 + rk (rk = rk−2 mod rk−1 ) 0 ≤ rk < rk−1 rk−1 = rk qk + 0 (rk+1 = rk−1 mod rk ) 0 = rk+1 < rk Po konečném počtu kroků dosáhne posloupnost nulové hodnoty rk+1 = 0. Potom podle Věty 8, část 2 (gcd (a + cb, b) = gcd (a, b)) platí gcd (a, b) = gcd (r0 , r1 ) = gcd (r1 q1 + r2 , r1 ) = gcd (r1 , r2 ) = gcd (r2 q2 + r3 , r2 ) = gcd (r2 , r3 ) = . . . = gcd (rk , 0) = rk ⇒ ⇒ gcd (a, b) = rk , kde rk je poslední nenulový zbytek. doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

15 / 32

Dělitelnost

Eukleidův algoritmus - příklad Příklad 11 Počítáme gcd (254, 158) : 254 = 1 · 158 + 96 158 = 1 · 96 + 62 96 = 1 · 62 + 34 62 = 1 · 34 + 28 34 = 1 · 28 + 6 28 = 4 · 6 + 4 6 = 1·4+2 4 = 2·2+0 . gcd (254, 158) = 2.



ZDM, ZS 20112/13, Lekce 11

16 / 32

Dělitelnost

Eukleidův algoritmus - složitost Jak dlouho to trvá, než Eukleidův algoritmus skončí?

Věta 12 (Lamého věta) Nechť a > b ∈ N. Pak Eukleidův algoritmus pro gcd(a, b) vyžaduje nejvýše tolik kroků, kolik je pětkrát počet číslic v desítkovém zápisu čísla b. Důkaz: viz Habala. Už víme, že gcd(a, b) = m.a + n.b pro jistá m, n ∈ Z. Uměli bychom tato m, n nalézt? Zkusíme využít Eukleidův algoritmus . . .



ZDM, ZS 20112/13, Lekce 11

17 / 32

Dělitelnost

Eukleidův algoritmus jinak 254 158 96 62 34 28 6

= = = = = = =

1 · 158 + 96 1 · 96 + 62 1 · 62 + 34 1 · 34 + 28 1 · 28 + 6 4·6+4 1·4+2

⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒

96 = 254 − 1 · 158 62 = 158 − 1 · 96 34 = 96 − 1 · 62 28 = 62 − 1 · 34 6 = 34 − 1 · 28 4 = 28 − 4 · 6 2=6−1·4

Budeme postupně odspodu dosazovat: 2 = 6 − 1 · 4 = 6 − 1 · (28 − 4 · 6) = −1 · 28 + 5 · 6 = −1 · 28 + 5 · (34 − 1 · 28) = 5 · 34 − 6 · 28 = 5 · 34 − 6 · (62 − 1 · 34) = −6 · 62 + 11 · 34 = −6 · 62 + 11 · (96 − 1 · 62) = 11 · 96 − 17 · 62 = 11 · 96 − 17 · (158 − 1 · 96) = −17 · 158 + 28 · 96 = −17 · 158 + 28 · (254 − 1 · 158) = 28 · 254 − 45 · 158 Dostali jsme výsledek: gcd(254, 158) = 28 · 254 − 45 · 158 = 7112 − 7110 = 2 doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

18 / 32

Dělitelnost

Prvočísla Množinu kladných přirozených čísel N+ lze s ohledem na dělitelnost rozdělit do tří podmnožin: 1

Číslo 1, které kromě sebe není dělitelné žádným jiným číslem.

2

Prvočísla, které kromě sebe jsou dělitelná jen číslem 1.

3

A ostatní čísla, která se nazývají složená.

Věta 13 Nechť a, b, c ∈ Z. Jestliže a|bc a čísla a a b jsou nesoudělná (tj. gcd (a, b) = 1), potom a|c. Důkaz: Z podmínky gcd (a, b) = 1 plyne podle Věty 9, že existují taková celá čísla x a y, že 1 = ax + by. Po vynásobení číslem c dostaneme c = cax + cby. Podle předpokladu a|bc a samozřejmě i a|cax, takže výraz na pravé straně je dělitelný číslem a, proto musí platit i a|c. doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

19 / 32

Dělitelnost

Vlastnosti prvočísel Věta 14 Nechť p je prvočíslo a nechť p|(a1 · a2 · · · · · ak ), kde ai , i = 1, . . . , k jsou přirozená čísla. Potom existuje 1 ≤ j ≤ k tak, že platí p|aj . Důkaz: Postupujeme indukcí s využitím předchozí věty.

Věta 15 Každé složené číslo můžeme psát ve tvaru součinu prvočísel. Důkaz: Postupujeme indukcí: 1 Nejmenší složené číslo je 4, pro které platí 4 = 2 · 2, a tedy tvrzení je správné. 2 Předpokládejme, že tvrzení je pravdivé pro všechna složená čísla menší než složené číslo n = a · b, kde 1 < a < n, 1 < b < n. Číslo a je buď prvočíslo, nebo složené číslo menší než n, takže podle indukčního předpokladu lze zapsat ve tvaru součinu prvočísel. Totéž platí pro b, takže i n můžeme zapsat ve tvaru součinu prvočísel. doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

20 / 32

Dělitelnost

Základní věta aritmetiky Věta 16 (Základní věta aritmetiky) Každé kladné celé číslo n se dá vyjádřit jediným způsobem ve tvaru n = pα1 1 · pα2 2 · · · pαk k , kde p1 < p2 < · · · < pk jsou prvočísla a α1 , . . . , αk jsou přirozená čísla. Tento zápis se nazývá kanonickým rozkladem čísla n nebo prvočíselnou mocninnou faktorizací čísla n.

Příklad 17 Kladná čísla 240, 289 a 1001 můžeme vyjádřit následovně: 240 = 2 · 2 · 2 · 2 · 3 · 5 = 24 · 3 · 5 289 = 17 · 17 = 172 1001 = 7 · 11 · 13 doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

21 / 32

Dělitelnost

Základní věta aritmetiky - využití Prvočíselnou faktorizaci lze využít pro vyjádření největšího společného dělitele gcd (a, b) a nejmenšího společného násobku lcm(a, b) dvou přirozených čísel a a b. Vytvoříme prvočíselné faktorizace čísel a a b ve tvaru b = q1β1 · q2β2 · · · qkβk ,

a = pα1 1 · pα2 2 · · · pαk k ,

tak, aby všechna prvočísla vyskytující se v prvočíselné faktorizaci a a b byla obsažena v obou součinech (případně s nulovým exponentem). Potom je min (α1 ,β1 )

gcd (a, b) = p1

min (α2 ,β2 )

· p2

min(αk ,βk )

· · · pk

,

protože čísla a a b sdílejí právě min (αi , βi ) násobků prvočísla pi . Podobně platí max(αk ,βk ) max (α2 ,β2 ) max (α1 ,β1 ) · · · pk , · p2 lcm(a, b) = p1 doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

22 / 32

Dělitelnost

Stručné shrnutí

Prvočíselný rozklad velkých celých čísel je časově náročná operace. K nalezení nejmenšího společného násobku dvou celých čísel využívame gcd daných čísel. gcd lze lehce nalezt podle Eukleidova algoritmu.



ZDM, ZS 20112/13, Lekce 11

23 / 32

Modulární aritmetika

Základy modulární aritmetiky Definice 18 (Kongruence) Nechť a, b, m ∈ Z, přičemž m > 1. Pokud m|(a − b), říkáme, že a je kongruentní s b modulo m a píšeme a ≡ b (mod m). Pokud m ∤ (a − b), říkáme, že a není kongruentní s b modulo m a píšeme a 6≡ b (mod m). Relace kongruence ≡ (mod m) představuje ekvivalenci na množině celých čísel Z. (RE): a ≡ a (mod m) (SY): a ≡ b (mod m) ⇔ b ≡ a (mod m) (TR): a ≡ b (mod m) ∧ b ≡ c (mod m) ⇒ a ≡ c (mod m)



ZDM, ZS 20112/13, Lekce 11

24 / 32


Vlastnosti kongruencí Nechť a, b, c, d, x, y, m ∈ Z, kde m > 1. 1

Následující tři vztahy jsou ekvivalentní: a ≡ b (mod m), b ≡ a (mod m), a − b ≡ 0 (mod m).

2

Pokud a ≡ b (mod m) a c ≡ d (mod m) potom ax + cy ≡ bx + dy (mod m) (specielně a + c ≡ b + d (mod m) a a − c ≡ b − d (mod m)).

3

Pokud a ≡ b (mod m) a c ≡ d (mod m), potom ac ≡ bd (mod m).



ZDM, ZS 20112/13, Lekce 11

25 / 32


Modulární aritmetika V jedno-modulární reziduální aritmetice je každé celé číslo b ∈ Z zobrazeno na přirozené číslo r ∈ Zm = {0, 1, 2, . . . , m − 1} . Číslo r je nejmenším nezáporným reziduem b modulo m.

Definice 19 Zobrazení | · |m : Z → Zm je definováno předpisem |b|m = r, kde 0 ≤ r < m a b ≡ r (mod m). Ekvivalence ≡ (mod m) definuje na množině Z rozklad do zbytkových tříd R0 , R1 , . . . , Rm−1 , kde Rk = {b ∈ Z : |b|m = k}. Příklad: Když m = 7, potom 58 ∈ R2 protože |58|7 = 2. Říkáme, že 2 je nejmenší nezáporné reziduum čísla 58 modulo 7.



ZDM, ZS 20112/13, Lekce 11

26 / 32


Vlastnosti zobrazení | · |m Nechť a, b, m ∈ Z, kde m > 1. Potom |a|m = |b|m ⇔ a ≡ b (mod m) |km|m = 0 pro všechna k ∈ Z |a + b|m = |a|m + |b|m = |a|m + b = a + |b|m m m m |ab|m = |a|m |b|m = |a|m b = a|b|m . m

m

m

Z předcházejícího je zřejmé, že nezáleží na tom, kdy se provede redukce modulo m. Zavedeme tedy operace sčítání ⊕ a násobení ⊙ modulo m: a ⊕ b = |a + b|m ,


a ⊙ b = |ab|m


ZDM, ZS 20112/13, Lekce 11

27 / 32


Modulární aritmetika Věta 20 Množina (Zm , ⊕, ⊙), kde ⊕, resp. ⊙ označují sčítání, resp. násobení modulo m, tvoří konečný komutativní okruh s jednotkou. Důkaz: Snadno lze ověřit platnost následujících vlastností pro každé a, b, c, ∈ Zm . uzavřenost a ⊕ b ∈ Zm a ⊙ b ∈ Zm , komutativita a⊕b=b⊕a a ⊙ b = b ⊙ a, asociativita a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c a ⊙ (b ⊙ c) = (a ⊙ b) ⊙ c, neutrální prvek a ⊕ 0 = |a|m a · 1 = |a|m , ··· , inv. prvek k ⊕ a ⊕ a = 0 distributivita a ⊙ (b ⊕ c) = a ⊙ b ⊕ a ⊙ c, kde aditivní inverze modulo m je definována vztahem a = | − a|m = m − a.



ZDM, ZS 20112/13, Lekce 11

28 / 32


Odčítání (mod m) Na okruhu (Z, ⊕, ⊙) můžeme definovat operaci odčítání ⊖ jako sčítání s aditivní inverzí modulo m: a ⊖ b = a ⊕ b. Modulární multiplikativní inverze určitého prvku (Zm , ⊕, ⊙) umožňuje provádět dělení tímto prvkem jako násobení jeho inverzí modulo m. Problém: existence modulární multiplikativní inverze prvku z (Zm , ⊕, ⊙).

Věta 21 Komutativní okruh (Z, ⊕, ⊙) je tělesem tehdy a jen tehdy, pokud m je prvočíslo.



ZDM, ZS 20112/13, Lekce 11

29 / 32


Modulární inverze Pokud m je prvočíslo, potom má každý nenulový prvek a ∈ Zm multiplikativní inverzi modulo m:

Věta 22 Když m je prvočíslo, a 6= 0 a a ∈ Zm , pak existuje jediné celé číslo b ∈ Zm , které vyhovuje rovnici a ⊙ b = 1. Číslu b říkáme multiplikativní inverze a modulo m a píšeme b = a−1 (m) nebo jednoduše a−1 pokud je modul znám. Důkaz: Tvrzení je důsledkem toho, že řešení diofantické rovnice ax + by = c pro a, b, c, x, y ∈ Z právě tehdy, když c je násobkem gcd(a, b). Rovnice a ⊙ b = 1 znamená ab ≡ 1 (mod m) ⇔ ⇔ ab − 1 = km ⇔ ab − km = 1, tedy požadujeme gcd(a, m) = 1, což pro prvočíselné m platí. doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

30 / 32


Inverze v modulární aritmetice Pokud m není prvočíslo, (Zm , ⊕, ⊙) není těleso a nenulové prvky nemusí mít multiplikativní inverzi.

Věta 23 (o existenci inverze) Nechť a ∈ Zm . Potom existuje jediné celé číslo b ∈ Zm , které vyhovuje rovnici a⊙b=b⊙a=1 právě tehdy, když gcd(a, m) = 1. Příklady: m = 10 a Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, takže jen čísla 1,3,7 a 9 mají multiplikativní inverzi modulo 10. m = 5 (prvočíslo) a Z5 = {0, 1, 2, 3, 4} takže všechny nenulové prvky (tj. 1,2,3,4) mají multiplikativní inverzi modulo 5. Když m je prvočíslo, pak je (Zm , ⊕, ⊙) (konečné) těleso. doc. Josef Kolář (FIT ČVUT)


ZDM, ZS 20112/13, Lekce 11

31 / 32


Dělení v modulární aritmetice Dělení na konečném tělese Když b−1 existuje ⇒ definujeme dělení modulo m jako a ⊘ b = a ⊙ b−1 . Pozor! Podíl dvou celých čísel v jedno-modulární aritmetice, pokud existuje, je vždy celé číslo a to i v případě, že a nedělí b v běžné aritmetice. Příklad: |7 ⊘ 9|11 = |7 ⊙ 9−1 |11 = |7 ⊙ 5|11 = 2.



ZDM, ZS 20112/13, Lekce 11

32 / 32

Základy teorie čísel. Základy diskrétní matematiky, BI-ZDM

Recommend Documents