ELEMENTY TEORII LICZB (1) Matematyka Dyskretna
ELEMENTY TEORII LICZB
ELEMENTY TEORII LICZB
Dla dowolnych liczb całkowitych a, b " Z, b `" 0, istnieją
jednoznacznie określone liczby q, r " Z takie, że a = qb + r i 0 d" r <
|b|.
Zapisujemy:
q = a div b
r = a mod b
a | b Ô! "c"Z(b = ac)
a | b Ô! a mod b = 0
a | b '" c | d Ò! ac | bd
a | b '" a | c Ò! a | bx + cy
a | b '" b | a Ò! a = b (" a =  b
d = NWD(a, b) Ô! d | a '" d | b '" "c"Z(c | a '" c | b c d" d)
ELEMENTY TEORII LICZB (2) Matematyka Dyskretna
Dla dowolnych liczb a, b " Z istnieją liczby x, y " Z takie, że
NWD(a, b) = ax + by.
Dowód
Niech d = min {ax + by : x, y " Z} )" N.
Czyli istnieją x', y' " Z takie, że d = ax' + by'.
Przypuśćmy, że ~ (d | a).
Wówczas istnieją q, r " Z takie, że a = dq + r, gdzie 0 < r < d.
Czyli mamy:
r =
a  dq =
a  (ax' + by)q =
a(1  qx') + b( qy').
A zatem r " S. Sprzeczność!
A zatem d | a. Analogicznie pokazujemy d | b.
A więc z definicji NWD mamy NWD(a, b) e" d. (*)
śamy a = NWD(a, b)c1 oraz b = NWD(a, b)c2 dla pewnych c1, c2 "
Z. StÄ…d:
d =
ax' + by' =
NWD(a, b)c1x' + NWD(a, b)c2y' =
NWD(a, b)( c1x' + c2y')
A zatem NWD(a, b) | d.
śamy więc NWD(a, b) d" d. (**)
ELEMENTY TEORII LICZB (3) Matematyka Dyskretna
d | a '" d | b Ò! d | NWD(a, b)
Dowód wynika bezpośrednio z poprzedniego twierdzenia.
Liczby a i b " Z, nazywamy względnie pierwszymi, gdy
NWD(a, b) = 1
NWD(a, b) = 1 Ô! "x,y"Z(ax + by = 1)
Dowód
Ò! wynika z wczeÅ›niejszego twierdzenia
Ð! Å›amy ax + by = 1. Niech d = NWD(a, b). A zatem d | a '" d | b.
StÄ…d d | 1. Czyli d = 1.
a | c '" b | c '" NWD(a, b) = 1 Ò! ab | c
Dowód.
Istnieją x, y " Z takie, że `ax + by = 1
Niech c = ax' oraz c = by'.
śamy
c =
c(ax + by) =
cax + cby =
by'ax + ax'by =
ab(y'x + x'y)
ELEMENTY TEORII LICZB (4) Matematyka Dyskretna
Twierdzenie Euklidesa III w.p.n.e
a | bc '" NWD(a, b) = 1 Ò! a | c
Dowód.
Istnieją x, y " Z takie, że `ax + by = 1
StÄ…d c = axc + byc.
a | axc '" a | byc Ò! a | axc + byc.
a = qb + r Ò! NWD(a, b) = NWD(b, r)
Oznaczmy c = NWD(b, r) oraz d = NWD(a, b).
A więc d | a '" d | b.
StÄ…d d | a  qb
Ò! d | r
(*) A zatem d | c.
śamy c | b '" c | r.
StÄ…d c | qb + r (= a)
Czyli c | a '" c | b
(**) A zatem c | d.
Z (*) i (**) mamy c = d.
NWD(a, b) = NWD(b, a mod b)
ELEMENTY TEORII LICZB (5) Matematyka Dyskretna
Algorytm Euklidesa
NWD(x, y) = ?
r0 = max{x, y}, r1 = min{x, y}
r2 = r0 mod r1
...
ri = ri 2 mod ri 1
... dopóki ri 2 mod ri 1 > 0
Niech rm będzie ostatnim wyrazem, dla którego rm 2 mod rm 1 > 0.
NWD(x, y) = NWD(r0, r1) = NWD(r1, r2) = ... = NWD(rm 1, rm) =
NWD(rm, 0) = rm.
Przykład:
NWD(2004, 1968) = NWD(1968, 36) = NWD(36, 24) = NWD( 24,
12) = NWD(12, 0) = 12
LiczbÄ™ p nazywamy pierwszÄ…, gdy p > 1 i jedynymi dodatnimi jej
dzielnikami są 1 oraz p. Zbiór liczb pierwszych oznaczamy przez P.
p " P '" a, b " Z '" p | ab Ò! p | a (" p | b
Dowód.
Załóżmy, że p " P '" a, b " Z '" p | ab.
Przypuśćmy ~ p | a.
A zatem NWD(p, a) = 1.
ELEMENTY TEORII LICZB (6) Matematyka Dyskretna
Z twierdzenia Euklidesa otrzymujemy p | b.
p " P '" n " N, "1 d" i d" n (ai " Z) '" p | a1a2Å"...Å"an Ò! "1 d" i d" n (p | ai)
Dowód (Indukcja względem n)
Dla n = 1oczywiste.
Załóżmy, że n e" 2 i twierdzenie jest spełnione dla liczb mniejszych
niż n.
p | a1a2Å"...Å"an Ò!
p | a1a2Å"...Å"an 1 (" p | an Ò!
"1 d" i d" n (p | ai).
p " P '" n " N, "1 d" i d" n (pi " P) '" p | p1p2Å"...Å"pn Ò! "1 d" i d" n (p = pi)
Dowód.
Załóżmy p " P '" n " N, "1 d" i d" n (pi " P) '" p | p1p2Å"...Å"pn.
Z poprzedniego lematu mamy"1 d" i d" n (p | pi).
Ponieważ p, pi " P, więc p = pi.
Zasadnicze twierdzenie arytmetyki
Każda liczba naturalna n > 1posiada jednoznaczny (z dokładnością do
kolejności czynników) rozkład na iloczyn liczb pierwszych.
(1) Istnienie rozkładu. (indukcja względem n)
Niech n > 1.
Dla n = 2 twierdzenie jest oczywiste.
ELEMENTY TEORII LICZB (7) Matematyka Dyskretna
Załóżmy, że n > 2 i każda liczba naturalna mniejszej niż n posiada
rozkład na iloczyn liczb pierwszych.
Jeżeli n " P, to istnienie rozkładu jest oczywiste.
Jeśli nie, to niech d będzie najmniejszym dodatnim dzielnikiem n.
Oczywiście d " P (w przeciwnym przypadku istniałby mniejszy niż
d dzielknik n).
A zatem n = dn', gdzie d " P i na mocy założenia indukcyjnego n'
posiada rozkład na iloczyn liczb pierwszych.
(2) Jednoznaczność rozkładu.
Niech n = p1p2Å"...Å"pr = q1q2Å"...Å"qs, gdzie pi, qj sÄ… niemalejÄ…cymi
ciÄ…gami liczb pierwszych dla 1 d" i d" r, 1 d" j d" s oraz r d" s.
Å›amy wiÄ™c p1 | q1q2Å"...Å"qs.
StÄ…d "1 d" i d" s (p1 = qi).
A zatem p1 e" q1.
Analogicznie q1 e" p1, wiÄ™c p1 = q1 i p2Å"...Å"pr = q2Å"...Å"qs.
Powtarzając powyższy krok r  1 krotnie otrzymujemy
pi = qi dla 1 d" i d" r oraz 1 = qr+1qr+2Å"...Å"qs.
Ostatnia równość świadczy, że r = s.
ELEMENTY TEORII LICZB (8) Matematyka Dyskretna
Kongruencje
Kongruencje
a a" b (mod n) Ô! n | a  b
Relacja kongruencji jest relacją równoważności w Z
Jeżeli a a" b (mod n) oraz c a" d (mod n), to
a + c a" b + d (mod n)
a  c a" b  d (mod n)
ac a" bd (mod n)
Jeżeli ab a" ac (mod n) i NWD(a, n) = 1, to b a" c (mod n)
Jeżeli k `" 0, to a a" b (mod n) Ô! ak a" bk (mod nk)
Jeżeli a a" b (mod n) oraz a a" b (mod m), to a a" b (mod NWW(n, m))
Jeżeli a a" b (mod n), to NWD(a, n) = NWD(b, n)
ELEMENTY TEORII LICZB (9) Matematyka Dyskretna
Chińskie twierdzenie o resztach
Chińskie twierdzenie o resztach
Jeżeli NWD(a, n) = 1, to istnieje dokładnie jedna liczba 0 d" b < n taka,
że ab a" 1 (mod n).
Dowód
(1) Isnienie
śamy liczby x, y takie ax + ny = 1. Stąd ax a" 1 (mod n). Wystarczy
przyjąć b = x mod n.
Wówczas mamy x = qn + b.
Czyli (qn + b)x a" 1 (mod n)
A zatem bx a" 1 (mod n).
(2) Jednoznaczność
Przypuśćmy, że 0 d" b d" c < n, ab a" 1 (mod n) i ac a" 1 (mod n).
StÄ…d ac  ab a" 0 (mod n).
Czyli mamy n | a(c  b) oraz NWD(a, n) = 1.
Stąd n | (c  b), a więc c = b.
Niech n " N, a " Z i NWD(a, n) = 1. Liczbę 0 d" b < n taką, że ab a" 1
(mod n) oznaczać będziemy przez b 1 (mod n).
ELEMENTY TEORII LICZB (10) Matematyka Dyskretna
Niech m1, m2, ..., mr " N będą parami względnie pierwsze. Niech a1,
a2, ..., ar " N.
Układ równań x a" ai (mod mi), dla 1 d" i d" r posiada unikalne
rozwiÄ…zanie modulo M = m1m2Å"Å"Å"mr:
r
x= Mi yi mod M ,
"a
i
i=1
gdzie Mi = M / mi oraz yi = Mi 1 (mod mi).
Dowód.
Poprawność:
Miyi a" 1 (mod mi) Ò! aiMiyi a" ai (mod mi)
Miyi a" 0 (mod mj) dla j `" i Ò! aiMiyi a" 0 (mod mj)
A zatem:
aiMiyi a" ai (mod mi)
ajMjyj a" 0 (mod mi) dla j `" i
StÄ…d x a" aiMiyi a" ai (mod mi)
Jednoznaczność:
(a a" b (mod n) oraz a a" b (mod m) Ò! a a" b (mod NWW(n, m))
StÄ…d x1 a" x2 (mod mi), dla 1 d" i d" r Ò! x1 a" x2 (mod M)
Przykład: x a" 1 (mod 3), x a" 3 (mod 4), x a" 3 (mod 5)
M = 60, M1 = 20, M2 = 15, M3 = 12
y1 = 20 1 (mod 3) = 2 1 (mod 3) = 2
y2 = 15 1 (mod 4) = 3 1 (mod 4) = 3
y3 = 12 1 (mod 5) = 2 1 (mod 5) = 3
x = 1Å"20Å"2 + 3Å"15Å"3 + 3Å"12Å"3 (mod 60) = 40 + 135 + 108 (mod 60)
= 283 (mod 60) = 43
ELEMENTY TEORII LICZB (11) Matematyka Dyskretna
Zadania pożegnalne:
(1) Udowodnij, że jeśli n | q i m | q, to NWW(n, m) | q
(2) Udowodnij, że jeśli q | n i q | m, to q | NWD(n, m)
(3) Udowodnij, że NWD(a, b)NWW(a, b) = |ab|
(4) Rozwiąż układ równań:
NWD(x, y) = 10
NWW(x, y) = 100
(5) Udowodnij, że jeżeli a2 + b2 + c2 = d2, to co najmniej dwie z
tych liczb sÄ… parzyste.
(6) Wykaż, że iloczyn k kolejnych liczb całkowitych jest
podzielny przez k!
(7) Udowodnij, że jeżeli a2 + b2 = c2, to 60 | abc
9
(8) Znajdz
ostatnie dwie cyfry liczby 99