Pseudo legenda
x1 = x1 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 d" r d"|a|
Jeśli a jest podzielne przez b to r =0
Jeśli a nie jest podzielne przez b to 0 d" r d"|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  Î÷
(x) b  qa = r , 0 d" r d"a
Przypuśćmy że istnieją liczby q1 i r1 takie że
(xx) b = q1a + r1 0 d" r1 d" 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 0Zatem r1= r
Z (xxx) dostajemy teraz 0 = (q-q1)a. Musi być zatem q-q1=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Î÷ z poprzednich rozważaÅ„ otrzymujemy b = q|a| + r, 0d"r<|a|
1. Jeśli a > 0, to |a| = a i wówczas b = ka+r, 0d"r<|a|
gdzie k = q, r
2. Jeśli a d"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  Î÷ - {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=bx0 + cy0
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  Î÷}
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
.
.
.
rn-2 = knrn-1 + rn 0 < r4 < r3
rn-1 = kn + 1 - rn
Ostatnia reszta rn 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 x0 y0 dla których a ax0 + by0 = 1
acx0 + bcy0 = 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
Twierdzenie 3.3
Każda liczba złożona n ma dzielnik pierwszy
Twierdzenie 3.3
Jeżeli liczba naturalna ne" 2 nie posiada dzielnika pierwszego d" " to jest pierwsza