Algebra-10-10-11-Wyklad

[ Pobierz całość w formacie PDF ]
Pseudo legenda
x1 = x
1
ab = a*b
Twierdzenie: Dla dowolnych dwóch liczb całkowitych a,b takich że a≠b istnieją liczby całkowite k i r
takie że
B = ka + r 0 ≤ r ≤|a|
Jeśli a jest podzielne przez b to r =0
Jeśli a nie jest podzielne przez b to 0 ≤ r ≤|a|
Dowód
Załóżmy najpierw, że a > 0 i rozważmy ciąg arytmetyczny
… b – 3a, b – 2a, b – a, b, b + a, b + 2a …
Najmniejszą liczbę nieujemną w tym ciągu oznaczymy symbolem r. Wtedy dla pewnego q Є
7
(x) b – qa = r , 0 ≤ r ≤a
Przypuśćmy że istnieją liczby q1 i r1 takie że
(xx) b = q1a + r1 0 ≤ r1 ≤ a
Najpierw pokażemy, że r1 = r. Nie wprost. Przypuśćmy np. że r1 > r. Odejmując (xx) od (x)
otrzymujemy
(xxx) r1 – r = (q – q1)a
Oznacza to że a | r1–r, ale 0<r1–r<a gdyż 0≤r1<a i 0≤r<a i 0≤<rr1<a zatem sprzeczność.
Zatem r
1
= r
Z (xxx) dostajemy teraz 0 = (qq1)a. Musi być zatem qq1=0 czyli q=q1
Niech teraz a będzie dowolna Liczbą całkowitą różną od zera. Skoro a ≠ 0 to |a| > 0. Zatem dla
bЄ
7
z poprzednich rozważań otrzymujemy b = q|a| + r, 0≤r<|a|
1. Jeśli a > 0, to |a| = a i wówczas b = ka+r, 0≤r<|a|
gdzie k = q, r
2. Jeśli a ≤0 to |a| = a i mamy
b = q|a| + r = q(a) + r = (q)a + r
Oznaczamy k = q. Wtedy
b = ka + r
Przypomnienie : Największy wspólny dzielnik
Definicja: Liczbę a Є
7
{0} nazywamy wspólnym dzielnikiem liczb całkowitych b i c, gdy a | b i
a | c. Jeśli przynajmniej jedna z liczb b,c jest różna od zera to wśród wszystkich wspólnych
dzielników liczb b i c (których jest skończenie wiele) istnieje największy z nich. Nazywamy ją
największym wspólnym dzielnikiem liczb b i c i oznaczamy symbolem (b,c)
W analogiczny sposób definiujemy największy wspólny dzielnik liczb całkowitych b1,b2..bn i
oznaczamy go symbolem (b1,b2,…bn)
Przykłady
Nwd(90,10) = 10
nwd(48,72)=24
Twierdzenie:
Jeśli g=(b,c) jest największym wspólnym dzielnikiem liczb całkowitych b i c, to istnieją liczby
całkowite x0.y0. takie że
g=bx
0
+ cy
0
Innymi słowy największy wspólny dzielnik liczb b i c jest kombinacją liczbową liczb b i c (0
współczynników całkowitych).
Twierdzenie
Największy wspólny dzielnik liczb całkowitych b,c może być scharakteryzowany w dwojaki sposób
1. Jako najmniejsza liczba nienaturalna nalożąca do zbiorów A = { bx + cy : xy Є
7
}
2. Jako wspólny dzielnik dodatnich liczb b i c podzielny przez każdy inny wspólny dzielnik liczb
b i c
Algorytm Euklidesa
Niech b i c będą liczbami całkowitymi przy czym c > 0
NWD liczb b i c może być oibliczany przy pomocy serii twórczości
b = k1c + r1
0 < r1 < c
c = k2r1 + r2
0 < r2 < r1
r1 = k3r2 + r3
0 < r3 < r2
r2 = k4r3 + r4
0 < r4 < r3
.
.
.
r
N-2
= k
N
r
N-1
+ r
N
0 < r
4
< r
3
r
N-1
= k
N + 1
r
N
Ostatnia reszta r
N
jest największym wspólnym dzielnikiem liczb b i c.
Przykład
1. Znaleść (42823,6409)
42823 = 6(6409) + 4369
6409 = 1(4369) + 2040
4369 = 2(2040) + 289
2040 = 7(289) + 17
289 = 17(17)
Odp: (42823,6409) = 17
2. Znaleść rozwiązanie szczególnie całkowite (jakiekolwiek) równania 4x + 29y = 5
Zauważmy ze (4,29) = 1
Rozważny równania
4x’ + 29y’ = 1
x’ = 7 y’=1
4x5(7) + 29x5 = 5
X=35
y=5
Najmniejsza wspólna wielokrotność:
Definicja: Niech dane będą liczby całkowite a1,a2…an różne od zera. Mówimy, że liczba całkowita b
jest wspólną wielokrotnością liczb a1…an jeżeli a ai | b dla i = 1,2…n
Najmniejszą ze wspólnych wielokrotności dodatnich nazywa się najmniejszą wspólną
wielokrotnością liczb a1…an. Oznaczamy ją symbolem [a1…an]. Lub NWW (a1…an);
Przykład
[45,30] = 90
45 | 3 30 | 2
15 | 3 15 | 3
5 | 5 5 | 5
1 | 1
2 x 3x3 x 5 = 90
Twierdzenie 1.7
Każda wspólna wielokrotność liczb a1…an ai≠0 jest podzielna przez ich największą wspólną
wielokrotność
Twierdzenie 1.8
Iloczyn największego wspólnego dzielnika dwóch liczb naturalnych przez ich najmniejszą wspólna
wielokrotność jest zły iloczyn tych liczb:
(a,b) [a,b] = ab a,b Є IN
Definicja 3
Liczby naturalne a I b liczymy wzglednie pierwszymi jeżeli (a,b) = 1
Jeśli liczba naturalna nie posiada innych dzielników poza trywialnymi to nazywamy ją liczbą
pierwszą (prime number)
Liczbe naturalną n>1 która nie jest pierwsza nazywamy liczbą złożoną
Twierdzenie 3.1
Jeżeli (a,b) = 1 i a | bc to a | c
Dowód
Według twierdzenia 1.3 istnieją liczby całkowite x
0
y
0
dla których a ax
0
+ by
0
= 1
acx
0 +
bcy
0
= c
Skoro a | ac i a | ab to a | c
Przykłady par liczb względnie pierwszych
(3,5) = 1
(2,7) = 1
(16,27) = 1 (8,15) = 1
Twierdzenie 3.2
Każda liczba naturalna a>1 daje się przedstawić jednoznacznie (z dokładnością do kolejnych
czynników w postaci iloczynu liczb pierwszych).
Gdy dane są dane rozkładu
a=p1p2…pn a = q1q2….qn
to k=l i liczby q1,q2…qn stanowią permutacje układu <jakiegoś>
Twierdzenie 3.3
Każda liczba złożona n ma dzielnik pierwszy
Twierdzenie 3.3’
Jeżeli liczba naturalna n≥ 2 nie posiada dzielnika pierwszego ≤
√
to jest pierwsza
[ Pobierz całość w formacie PDF ]