Klapi v.1.0
- 1 -
ALG 100
Algebra - Teoria podzielno ci
Twierdzenia:
1. a a a b b c a c
2. d d 1 d 1
3. a,b a b b a a b
4. a b
∀
k
a bk
5. a b a c
∀
x,y
a bx+cy
Definicja:
Liczba d to najwi kszy wspólny dzielnik liczb n
1
,…, n
k
d = (n
1
,…, n
k
) , je eli:
1. d n
i
∀
i = 1,…,k
2.
∀
c
(
∀
i
c n
i
) c d
d = (a,b) d a d b (
∀
x
x a x b x d)
Definicja:
Liczba m to najmniejsza wspólna wielokrotno liczb n
1
,…, n
k
m = [n
1
,…, n
k
] , je eli:
1. n
i
m
∀
i = 1,…,k
2.
∀
M
(
∀
i
n
i
M ) m M
m = [a,b] a m b m (
∀
x
a x b x m x)
Twierdzenia:
ab = (a,b) [a,b]
abc = (ab,ac,bc) [a,b,c]
(n
1
, n
2
,…, n
k-1
, n
k
) = ((n
1
, n
2
,…, n
k-1
), n
k
)
Twierdzenie:
Równanie ax + by = c posiada rozwi zanie całkowite (a,b) c
! Je eli (a,b) = 1 to istnieje rozwi zanie całkowite.
Klapi v.1.0
- 2 -
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.
a bc (a,b) = 1 a c
Rozwi zanie ogólne:
Rozwi zanie ogólne równania ax + by = c, gdzie d = (a,b)
x = x
o
+
b
/
d
k
y = y
o
-
a
/
d
k
Twierdzenie:
Je eli p jest liczb
pierwsz
to:
p ab p a p b
Twierdzenie:
Gdy p jest liczb pierwsz :
p a
1
a
2
…a
n
∃
1 i n
p a
i
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)p
1
p
2
…p
k
;
gdzie p
i
to liczba pierwsza.
Twierdzenie:
Niech:
n,m
n = p
1
1
p
2
2
… p
k
k
,
p
i
to ró ne l. pierwsze
m = p
1
1
p
2
2
… p
k
k
,
, 0,
wtedy:
(n,m) = p
1
min(
1
,
1
)
p
2
min(
2
,
2
)
…p
k
min(
k
,
k
)
[n,m] = p
1
max(
1
,
1
)
p
2
max(
2
,
2
)
…p
k
max(
k
,
k
)