Algebra - Teoria podzielności
Twierdzenia:
1. aIa aIb bIc aIc
2. d dI1 d 1
3. a,b aIb bIa a b
4. aIb "k aIbk
5. aIb aIc "x,y aIbx+cy
Definicja:
Liczba d to największy wspólny dzielnik liczb n1,& , nk
d = (n1,& , nk) , jeżeli:
1. dIni "i = 1,& ,k
2. "c ( "i cIni ) cId
d = (a,b) dIa dIb ("x xIa xIb xId)
Definicja:
Liczba m to najmniejsza wspólna wielokrotność liczb n1,& , nk
m = [n1,& , nk] , jeżeli:
1. ni Im "i = 1,& ,k
2. "M ( "i ni IM ) mIM
m = [a,b] aIm bIm ("x aIx bIx mIx)
Twierdzenia:
ab = (a,b) [a,b]
abc = (ab,ac,bc) [a,b,c]
(n1, n2,& , nk-1, nk) = ((n1, n2,& , nk-1), nk)
Twierdzenie:
Równanie ax + by = c posiada rozwiązanie całkowite (a,b)Ic
! Jeżeli (a,b) = 1 to istnieje rozwiązanie całkowite.
Klapi v.1.0 - 1 - ALG 100
Twierdzenie:
Dzieląc dwie liczby przez ich największy wspólny dzielnik otrzymamy
liczby względnie pierwsze.
(a,b) = d (a/d, b/d ) = 1
Twierdzenie:
Jeżeli liczba a jest dzielnikiem iloczynu i jest względnie pierwsza z
jednym ze składników iloczynu to liczba a dzieli drugi składnik
iloczynu.
aIbc (a,b) = 1 aIc
Rozwiązanie ogólne:
Rozwiązanie ogólne równania ax + by = c, gdzie d = (a,b)
x = xo + b/d k
y = yo - a/d k
Twierdzenie:
Jeżeli p jest liczbą pierwszą to:
pIab pIa pIb
Twierdzenie:
Gdy p jest liczbą pierwszą :
pIa1a2& an "1 i n pIai
Zasadnicze twierdzenie arytmetyki:
Każda liczba n 0, 1 da się przedstawić jednoznacznie (z
dokładnością do kolejności czynników) jako:
n = ( 1)p1p2& pk ;
gdzie pi to liczba pierwsza.
Twierdzenie:
Niech: n,m
1 2 k
n = p1 p2 & pk , pi to różne l. pierwsze
1 2 k
m = p1 p2 & pk , , 0,
wtedy:
1 1 2 2 k k
(n,m) = p1min( , ) p2 min( , )& pk min( , )
1 1 2 2 k k
[n,m] = p1max( , ) p2 max( , )& pk max( , )
Klapi v.1.0 - 2 - ALG 100