Diskrétní matematika 1, 2

Věta o Bezoutových koeficientech

Věta (o Bezoutových koeficientech).

\forall a, b \in ℕ, a \neq 0 \lor b \neq 0, \exists x_{0}, y_{0} \in ℤ : a x_{0} + b y_{0} = \gcd (a, b)

Důkaz. Nechť

M_{a, b} = {a x + b y | x, y \in ℤ}

. Taková množina je uzavřená na sčítání a násobení (důkaz triviální). Nechť

u = \min (M_{a, b} \cap ℕ)

u

musí být dělitelné

\gcd (a, b)

, jelikož je součtem dvou čísel, která jsou jím dělitelná. Předpokládejme sporem, že

u ∤ a

. Potom ale

a - (a mod u) \in M_{a, b}

, což je spor s minimalitou

u

. Tedy

u | a

a analogicky

u | b

, z čehož plyne

u \leq \gcd (a, b)

. Jelikož zároveň

\gcd (a, b) | u

, musí být

u = \gcd (a, b)

, čímž je důkaz hotov.

Věta.

\forall a, b, c \in ℕ, a ⟂ b : a | c \land b | c ⟹ (a \cdot b) | c

Věta.

\gcd (a, b) = \gcd (a - b, b)

Důkaz.

M_{a, b} = {a x + b y | x, y \in ℤ} = {(a - b) x + b (x + y) | x, y \in ℤ} = {(a - b) x + b z | x, z \in ℤ} = M_{a - b, b}

Z této věty plyne správnost Euklidova algoritmu pro hledání $\gcd (a, b)$

Počet kroků Euklidova algoritmu

Pro $a > b$ platí $b \cdot (a mod b) < \frac{a \cdot b}{2}$ . Tudíž součin čísel, jejichž $\gcd$ hledáme, se pokaždé sníží alespoň dvakrát. Tedy časová složitost je $𝒪 (\log (a \cdot b)) = 𝒪 (\log (a) + \log (b))$ .

Nejmenší $b$ , které potřebuje $n$ kroků, je $F_{n + 1}$ .

Diofantická rovnice

Věta. Řešení rovnice

a x + b y = c

ℤ

existuje právě tehdy, pokud

\gcd (a, b) | c

Důkaz.

( $\Rightarrow$ ) $\gcd (a, b) | a \land \gcd (a, b) | b ∴ \gcd (a, b) | c$

( $\Leftarrow$ ) Nechť $c^{'} = c \div \gcd (a, b)$ . Podle věty o Bezoutových koeficientech $a x_{0} + b y_{0} = \gcd (a, b)$ . Zvolme $x = c^{'} \cdot x_{0}, y = c^{'} \cdot y_{0}$ , poté přenásobením rovnice $c^{'}$ získáme $a x + b y = c$ .

Věta. Jestliže rovnice

a x + b y = c

má řešení

x_{0}, y_{0}

. Označme

a^{'} = a \div g c d (a, b), b^{'} = b \div g c d (a, b)

, pak všechna řešení jsou ve tvaru

x = x_{0} + k \cdot b^{'}, y = y_{0} - k \cdot a^{'}

Prvočísla

Definice. Nechť

p \in ℕ, p \geq 2

p

je prvočíslo, je-li dělitelné pouze

1

a sebou samým.

Věta.

\forall p \in ℕ, p \geq 2 : p \in ℙ ⟺ (\forall a, b \in ℕ : p | a b ⟹ p | a \lor p | b

Důkaz.

$(\Rightarrow)$ $p | a b ⟹ {\begin{matrix} \gcd (p, a) > 1 ⟹ p | a \\ \gcd (p, b) = 1 ⟹ p | b \end{matrix}$

$(\Leftarrow)$ $p = d_{1} d_{2}, 1 < d_{1}, d_{2} < p ⟹ p | d_{1} d_{2} \land \neg (p | d_{1} \lor p | d_{2}) ⟹ SPOR s (\Rightarrow)$

Věta (základní věta aritmetiky). Nechť

n \in ℕ^{+}

. Pak existuje právě jeden (až na pořadí) rozklad

n

na součin prvočísel.

Důkaz.

Existence: $n = 1 \lor n \in ℙ \lor n = a b, 2 \leq a, b < n$

Jednoznačnost: Vezměme nejmenší $n$ , pro které věta neplatí, tedy $n = \prod_{i} p_{i} = \prod_{i} q_{i}$ . $p_{1} | \prod_{i} q_{i} ⟹ \exists i : p_{1} | q_{i} ⟹ p_{1} = q_{i}$ . Potom však věta neplatí také pro $n \div p_{1}$ , což je spor s minimalitou $n$ .

Věta. Nechť

n = \prod_{i} p_{i}^{k_{i}}

. Pak počet dělitelů

n

(

τ (n)

) je

\prod_{i} (k_{i} + 1)

Důkaz.

d = \prod_{i} p_{i} j_{i} | n ⟺ \forall i : j_{i} \leq k_{i}

. Tedy počet možností, jak zvolit každé

j_{i}

, je

k_{i} + 1

Věta. Nechť

a = \prod_{i} p_{i}^{k_{i}}, b = \prod_{i} p_{i}^{l_{i}}

. Pak

\gcd (a, b) = \prod_{i} p_{i}^{\min (k_{i}, l_{i})}

Věta. Prvočísel existuje nekonečně mnoho.

Důkaz (Euklidův; první důkaz sporem v historii matematiky). Předpokládejme, že existuje konečně mnoho prvočísel

p_{i}

. Nechť

n = (\prod_{i} p_{i}) + 1

n

nemůže být dělitelné žádným prvočíslem, tudíž jde o prvočíslo, což je spor.

Věta. Pro každé

n \in ℕ

existuje

n

po sobě jdoucích složených čísel.

Důkaz. Vezměme čísla od

(n + 1)! + 2

(n + 1)! + n + 1

; každé musí být složené.

Relace

Definice. Relace

R

na množině

A

je podmnožina

A^{2}

. Značení

a R b

znamená

(a, b) \in R

Definice. Relace

\sim

na množině A je ekvivalence, pokud je

reflexivní: $\forall a \in A : a \sim a$
symetrická: $\forall a, b \in A : a \sim b ⟹ b \sim a$
tranzitivní: $\forall a, b, c \in A : a \sim b \land b \sim c ⟹ a \sim c$

Definice. Třídy ekvivalence

\sim

jsou množiny

{[a] = {b \in A | b \sim a} | a \in A}

Kongruence

Definice. Nechť

m \in ℕ^{+}

a, b

jsou kongruentní modulo

m

, pokud

m | a - b

. Značení

a \equiv b (m o d m)

Věta. Kongruence mod

m

je ekvivalence na

ℤ .

Důkaz.

Kongruence: $m | a - a = 0$
Symetrie: $m | a - b ⟹ m | b - a = - (a - b)$
Tranzitivita: $m | a - b \land m | b - c ⟹ m | a - c = (a - b) + (b - c)$

Věta. Třídy ekvivalence kongruence modulo

m

jsou

{[y] = {y + k m | k \in ℤ} | y \in {0, \dots, m - 1}}

Příklad. Pro

m = 3

$[0] = {\dots, - 12, - 9, - 6, - 3,0,3,6,9,12, \dots}$
$[1] = {\dots, - 11, - 8, - 5, - 2,1,4,7,10,13, \dots}$
$[2] = {\dots, - 10, - 7, - 4, - 1,2,5,8,11,14, \dots}$

Věta.

$a \equiv b (m o d m) ⟹ a + c \equiv b + c (m o d m)$
$a \equiv b (m o d m) ⟹ a c \equiv b c (m o d m)$
$a \equiv b (m o d m) \land c \equiv d (m o d m) ⟹ a + c \equiv b + d (m o d m)$
$a \equiv b (m o d m) \land c \equiv d (m o d m) ⟹ a c \equiv b d (m o d m)$
$a \equiv b (m o d m) ⟹ a^{k} \equiv b^{k} (m o d m)$
$a \equiv b (m o d m) \land c > 0 ⟺ a c \equiv b c (m o d m c)$
$a c \equiv b c (m o d m) \land c ⟂ m ⟹ a \equiv b (m o d m)$

Cvičení. Ukažte, že

13 | 16^{15} + 29^{14} + 42^{13}

Řešení

16^{15} + 29^{14} + 42^{13} \equiv 3^{15} + 3^{14} + 3^{13} = 3^{13} (9 + 3 + 1) = 3^{13} \cdot 13 \equiv 0

Cvičení. Najděte

2^{30} mod 5

Řešení

2^{30} = 4^{15} \equiv (- 1)^{15} = - 1 \equiv 4

Cvičení. Najděte

72^{11} mod 17

Řešení

72^{11} \equiv 4^{11} = 4 \cdot 16^{5} \equiv 4 \cdot (- 1)^{5} = - 4 \equiv 13

Řešení lineární kongruence s jednou neznámou

a x = b (m o d m)

Věta. Řešení existuje právě tehdy, pokud

\gcd (a, m) | b

Číselné soustavy

Věta. Mějme přirozené číslo

q \geq 2

. Potom každé

n \in ℕ^{+}

lze zapsat jednoznačně ve tvaru

n = \sum_{i = 0}^{k} a_{i} q^{i}

, kde

k \in ℕ_{0}, a_{k} \neq 0, a_{i} \in {0,1, \dots, q - 1}

Důkaz.

(jednoznačnost) Předpokládejme, že by existovalo $n \in ℕ^{+}$ se dvěma různými zápisy $n = \sum_{i = 0}^{k} a_{i} q^{i} = \sum_{i = 0}^{l} b_{i} q^{i}$ . Vezměme nejmenší takové $n$ . Pokud $k = l$ , potom $n - q^{k}$ má také dva různé zápisy, což je spor s minimalitou $n$ . Pokud by bez újmy na obecnosti bylo $k > l$ , pak $n \geq q^{k}$ a zároveň $n \leq \sum_{i = 0}^{k} (q - 1) q^{i} = q^{l + 1} - 1 < q^{k}$ , což je spor. Předpoklad tedy nemůže platit.

(existence) Zápis čísla lze nalézt pomocí modulárního nebo hladového algoritmu.

Věta. Nechť

p

je polynom s celočíselnými koeficienty, pak

\forall a, b \in ℤ, m \in ℕ^{+} : a \equiv b (m o d m) ⟹ p (a) \equiv p (b) (m o d m)

Důkaz. Triviální.

Věta. Nechť

q, n \in ℕ^{+}, q \geq 2

. Pak

n

má stejný zbytek modulo

q - 1

jako jeho ciferný součet v soustavě

q

Důkaz. Vyjádřeme

n

v soustavě

q

jako polynom

p

, potom

n = p (q) \equiv p (1) (m o d q)

Věta. Nechť

q, n \in ℕ^{+}, q \geq 2

. Pak

n

má stejný zbytek modulo

q + 1

jako jeho ciferný součet se střídavými znaménky v soustavě

q

Důkaz. Vyjádřeme

n

v soustavě

q

jako polynom

p

, potom

n = p (q) \equiv p (- 1) (m o d q)

Čínská zbytková věta

Věta (čínská zbytková). Mějme soustavu

k

rovnic ve tvaru

x \equiv r_{i} (m o d m_{i})

, kde jednotlivá

m_{i}

jsou po dvou nesoudělná. Tato soustava má řešení a pro každé řešení platí

x \equiv \sum_{i} c_{i} \frac{m}{m_{i}} r_{i} (m o d m)

. kde

m = \prod_{i} m_{i}

c_{i} \frac{m}{m_{i}} \equiv 1 (m o d m_{i})

Cvičení. Řešme soustavu rovnic

\begin{aligned} x & \equiv 2 (m o d 3) \\ x & \equiv 1 (m o d 5) \\ x & \equiv 6 (m o d 7) \end{aligned}

Máme

m = 3 \cdot 5 \cdot 7 = 105

. Má platit

x \equiv c_{1} \cdot 5 \cdot 7 \cdot 2 + c_{2} \cdot 3 \cdot 7 \cdot 1 + c_{3} \cdot 3 \cdot 5 \cdot 6 (m o d 105) \land c_{1} \cdot 5 \cdot 7 \equiv 1 (m o d 3) \land c_{2} \cdot 3 \cdot 7 \equiv 1 (m o d 5) \land c_{3} \cdot 3 \cdot 5 \equiv 1 (m o d 7)

Důkaz.

(existence) Mějme $x = \sum_{i} c_{i} \frac{m}{m_{i}} r_{i}$ . Pro každé $i$ potom platí, že všechny sčítance kromě $i$ -tého jsou dělitelné $m_{i}$ a podle podmínky pro ten $i$ -tý platí $x \equiv r_{i} (m o d m_{i})$ , tedy původní soustava rovnic je vyřešena.

(všechna řešení) $(\forall i : z \equiv x (m o d m_{i})) ⟺ z \equiv x (m o d m)$ .

Věta. Soustava

x \equiv r_{1} (m o d m_{1}), x \equiv r_{2} (m o d m_{2})

má řešení právě tehdy, pokud

\gcd (m_{1}, m_{2}) | r_{2} - r_{1}

Důkaz (Golombův). Máme

p

korálků a

a

barev. Zajímá nás počet náhrdelníků, které nejsou jednobarevné (záleží na pořadí). To je počet všech mínus počet jednobarevných, tedy

a^{p} - a

. Pokud náhrdelník, který není jednobarevný, otočíme tak, aby se barvy nezměnily, musí počet pootočení dělit počet korálků. Tudíž náhrdelníky s prvočíselným počtem korálků jsou s ohledem na otočení unikátní, tedy otáčením jednoho vyrobíme vždy

p

různých. Z toho plyne

p | a^{p} - a

. Jednoduchou manipulací dostaneme

a^{p - 1} \equiv 1 (m o d p)

Eulerova funkce

Definice. Eulerova funkce

φ : ℕ^{+} \to ℕ^{+}

φ (n) = | {k \in \hat{n} | k ⟂ n} |

$(\forall p \in ℙ) (φ (p) = p - 1)$
$(\forall p \in ℙ) (\forall l \in ℕ^{+}) (φ (p^{l}) = p^{l} - p^{l - 1})$
$(\forall p, q \in ℙ) (φ (p q) = (p - 1) (q - 1))$

Věta. Nechť

\prod_{i} p_{i}^{k_{i}}

je prvočíselný rozklad čísla

n

. Pak

φ (n) = \prod_{i} p_{i}^{k_{i} - 1} (p_{i} - 1) = \prod_{i} p_{i}^{k_{i}} (1 - \frac{1}{p_{i}}) = n \prod_{i} (1 - \frac{1}{p_{i}})

Věta.

(\forall n \in ℕ^{+}) (n = \sum_{d | n} φ (d))

Důkaz. Uvažujme základní tvary všech zlomků

\frac{i}{n}, i \in \hat{n}

. Pro každé

d | n

bude platit, že počet zlomků, které mají ve jmenovateli

d

, bude právě

φ (d)

Věta (Eulerova-Fermatova).

(\forall a, n \in ℕ, a ⟂ n) (a^{φ (n)} \equiv 1 (m o d n))

Důkaz. Nechť

b_{i}, i \in \hat{φ (n)}

jsou všechna čísla do

n

nesoudělná s

n

. Nechť

r_{i} = a b_{i} mod n

, pak i všechna

r_{i}

budou nesoudělná s

n

a navzájem různá (důkaz triviální). To znamená, že

r_{i}

tvoří permutaci

b_{i}

, tedy

\prod_{i} b_{i} = \prod_{i} r_{i} \equiv \prod_{i} a b_{i} = a^{φ_{n}} \prod_{i} b_{i} (m o d n)

. Jelikož součin

b_{i}

je nesoudělný s

n

, můžeme podělit obě strany kongruence, čímž je důkaz hotov.

Cvičení. Najděte mocninu

3

, jejíž dekadický zápis končí na

0001

Řešení

3^{m} \equiv 1 (m o d 10^{4})

, podle Eulerovy-Fermatovy věty

m = φ (10^{4}) = φ (2^{4} \cdot 5^{4}) = 2^{3} (2 - 1) \cdot 5^{3} (5 - 1) = 4000

Cvičení. Existuje

a \in ℕ

takové, že

a^{13} = 21982145917308330487013369

. Jaké?

Prvočíselné testy

Věta (prvočíselná).

\lim_{n \to \infty} \frac{π (n)}{\frac{n}{\ln (n)}} = 1

Předpoklad: zkoumáme pouze lichá čísla vyšší než $1$

Fermatův test prvočíselnosti

Věta.

(\forall n \in ℕ) (n \in ℙ ⟺ (\forall a \in \hat{n - 1}) (a^{n - 1} \equiv 1 m o d n))

Důkaz.

$(\Rightarrow)$ Přímo vyplývá z malé Fermatovy věty.

$(\Leftarrow)$ Předpokládejme pro spor, že platí pravá strana implikace a $n = c \cdot d; c, d \geq 2$ . Poté $c^{n - 1} \equiv 1 m o d n$ , tedy $(\exists k \in ℤ) (1 = c^{n - 1} + k \cdot n = c^{n - 1} + k \cdot c \cdot d)$ . Z toho plyne $c | 1$ , což je spor.

Definice. Nechť

n

je složené číslo a

a \in \hat{n - 1}

. Poté

$a$ je svědek složenosti, pokud $a^{n - 1} \equiv̸ 1 m o d n$ .
$a$ je lhář, pokud $a^{n - 1} \equiv 1 m o d n$ . Také je říká, že $n$ je pseudoprvočíslo vůči základu $a$ .

Věta. Nechť

n

je liché složené číslo. Potom

$1$ a $n - 1$ jsou lháři
každé číslo soudělné s $n$ je svědek složenosti

Definice. Složené

n

se nazývá Carmichaelovo číslo, pokud

(\forall a \in \hat{n - 1}) (a ⟂ n ⟹ a^{n - 1} \equiv 1 m o d n)

Nejmenší Carmichaelovo číslo je $561$ .
Pro každé $k \in ℕ$ je $(6 k + 1) (12 k + 1) (18 k + 1)$ Carmichaelovo číslo, pokud všichni tři činitelé jsou prvočísla.
Existuje nekonečně mnoho Carmichaelových čísel.

Věta (Fermatův test prvočíselnosti). Nechť

n \in ℕ, n > 1,2 ∤ n

n

není Carmichaelovo číslo. Zvolíme náhodně

N

čísel

a_{i}

\hat{n - 1}

, potom

$(\exists a_{i}) (a_{i}^{n - 1} \equiv̸ 1 m o d n) ⟹ n \notin ℙ$
$(\forall a_{i}) (a_{i}^{n - 1} \equiv 1 m o d n) ⟹ n \in ℙ s p r a v d \overset{ˇ}{e} p o d o b n o s t \overset{ˊ}{ı} \geq 1 - 2^{- N}$

Obecný postup na řešení lineárních rekurencí

Definice. Nechť

k \in ℕ

α_{0}, \dots, α_{k - 1}, f : ℂ^{ω}

. Rovnice

a_{n + k} + \sum_{i = 0}^{k - 1} α_{i} (n) a_{n + i} = f (n)

se nazývá lineární rekurentní vztah (diferenční rovnice) řádu

k

pro posloupnost

a

s pravou stranou

f

. Je-li

f (n) = 0

, potom se rovnice nazývá homogenní, jinak nehomogenní.

Věta. Množina posloupností

ℂ^{ω} = (ℕ \to ℂ)

tvoří lineární prostor nad tělesem

ℂ

Důkaz. Triviální.

Věta. Množina

M = {a \in ℂ^{ω} | a_{n + k} + \sum_{i = 0}^{k - 1} α_{i} (n) a_{n + i} = 0}

tvoří podprostor

ℂ^{ω}

Důkaz.

$\vec{0} = (n \mapsto 0) \in M$ .
Nechť $a, b \in M$ a $γ \in ℂ$ . Potom $γ a + b \in M$ , neboť pro všechna $n \in ℕ$ $a_{n + k} + \sum_{i = 0}^{k - 1} α_{i} (n) (γ a_{n + i} + b_{n + i}) = γ (a_{n + k} + \sum_{i = 0}^{k - 1} α_{i} (n) a_{n + i}) + (a_{n + k} + \sum_{i = 0}^{k - 1} α_{i} (n) a_{n + i}) = 0$

Věta.

\dim M = k

Důkaz. Pro

i \in {0, \dots, k - 1}

definujme posloupnosti

e_{i}

takové, aby

e_{i} (i) = 1

\forall j \in {0, \dots, k - 1} ∖ {i}, e_{i} (j) = 0

. Zbytek členů dopočítáme tak, aby každé

e_{i}

patřilo do

M

. Tyto posloupnosti zřejmě tvoří bázi

M

Definice. Rovnice

λ^{k} + \sum_{i = 0}^{k - 1} α_{i} λ^{i} = 0

se nazývá charakteristická rovnice lineární rekurence.

Věta. Nechť

α_{i}

jsou konstanty a

λ \in ℂ ∖ {0}

. Potom

(n \mapsto λ^{n}) \in M

právě tehdy, pokud řeší charakteristickou rovnici.

Řešení lineární rekurence — pokračování

P (λ) = λ^{k} + \sum_{i = 0}^{k - 1} α_{i} λ^{i}

Věta. Má-li charakteristický polynom

k

různých kořenů, potom posloupnosti

n \mapsto λ_{i}^{n}

jsou lineárně nezávislé.

Důkaz. Sestavme matici soustavy pro prvních

k

členů a ur4eme její determinant:

| \begin{array}{cccc} 1 & 1 & \dots & 1 \\ λ_{1} & λ_{2} & \dots & λ_{k} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ λ_{1}^{k - 1} & λ_{2}^{k - 1} & \dots & λ_{k}^{k - 1} \end{array} | = \prod_{1 \leq i < j \leq k} (λ_{i} - λ_{j}) \neq 0

Věta. Jestliže má charakteristický polynom

l \leq k

různých kořenů s násobnostmi

γ_{i}

. Potom soubor lineárně nezávislých posloupností je

n \mapsto n^{j} \cdot λ_{i}^{n}

pro každé

i \in 1, \dots, l

j \in 0, \dots, γ_{i} - 1

Diskrétní matematika 1, 2

Organizace

Magická čísla

Dělitelnost

Celá část

Největší společný dělitel

Z minula

Věta o Bezoutových koeficientech

Hledání Bezoutových koeficientů podle Euklidova algoritmu

Počet kroků Euklidova algoritmu

Diofantická rovnice

Prvočísla

Relace

Kongruence

Řešení lineární kongruence s jednou neznámou

Číselné soustavy

Čínská zbytková věta

Eulerova funkce

Prvočíselné testy

Fermatův test prvočíselnosti

Obecný postup na řešení lineárních rekurencí

Řešení lineární rekurence — pokračování