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