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 Є 

(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 = (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, 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 Є  - {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 Є }

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