Zasada mnożenia Dla skończonych zbiorów X,Y zachodzi |X x Y| = |X| * |Y|. Zasada dodawania(a) Dla skończonych i rozłącznych zbiorów A i B mamy: |A υ B| = |A| + |B|.(b) Dla skończonych zbiorów mamy: |A υ B| = |A| + |B| - |A ∩ B|.

Zasada włączania i wyłączania Dla zbiorów skończonych {A1, …, An} zachodzi|A₁ υ … υ A_n| = ∑_{I ε {1, … , n}} (-1)^|I|+1 |∩_{i ε I} A_i|= |A₁| + … + |A_n| - |A₁ ∩ A₂| - |A₁ ∩ A₃| - … - |A_n-2 ∩ A_n| - |A_n-1 ∩ A_n|+ |A₁ ∩ A₂ ∩ A₃| + …+ |A_n-2 ∩ A_n-1 ∩ A_n| - |A₁ ∩ A₂ ∩ A₃ ∩ A₄| - … - |A_n-3 ∩ A_n-2 ∩ A_n-1 ∩ A_n|+ …(-1) ⁿ⁺¹ |A₁ ∩ … ∩ A_n|

Zasada Minimum (ZMin): Dowolny niepusty podzbiór S zbioru liczb naturalnych N ma w sobie liczbę najmniejszą. Zasada Indukcji Matematycznej (ZIM) Jeżeli Z zawiera się w zbiorze liczb naturalnych N :w którymko należy do Z oraz Z wraz z każdą liczbą naturalną k >= ko zawiera również kolejną liczbę k+1 (tzn. dla każdego k >= ko zachodzi, że jeśli k należy do Z , to k+1 należy do Z), to zbiór Z zawiera wszystkie liczby naturalne n >= ko (tzn. N – {0,1,...,ko-1} zawiera się w Z). Pierwszy warunek nazywamy bazą indukcji (krok podstawowy). W drugim warunku najpierw dokonujemy założenia indukcyjnego (o tym, że k należy do Z),a następnie wykonujemy krok indukcyjny dowodząc, że k+1 należy do Z. Zasada Indukcji Zupełnej (ZIZ) Jeżeli Z jest jakimś zbiorem liczb naturalnych , który wraz z każdym początkowym fragmentem zbioru N postaci {0,1,...,k-1} zawieran również kolejną liczbę k (tzn. dla każdego k należącego do N zachodzi:jeśli (dla każdego l<k jest tak, że l należy do Z), to k+1 należy do Z to Z zawiera wszystkie liczby naturalne (Z=N). Zauważmy, że nie ma tu wyróżnionego kroku bazowego (ukryty jest on w warunku dla k=0, bo poprzednik implikacji jest trywialnie spełniony). Zasada Maksimum (ZMax) Dowolny niepusty i ograniczony od góry podzbiór S zbioru liczb naturalnych ma w sobie liczbę największą Zasada Szufladkowa Dirichleta Jeśli n obiektów jest rozmieszczonych w m szufladach i n>m, to istnieje szuflada z przynajmniej dwoma obiektami. Uogólniona Zasada Szufladkowa Jeśli m obiektów rozmieszczonych jest w n szufladach i m>n*r, dla pewnego naturalnego r, to istnieje szufladka z co najmniej r+1 obiektami.(jeżeli każda szuflada ma co najwyżej r obiektów i n szuflad jest, to w sumie jest co najwyżej n*r obiektów)

Dzielenie liczb całkowitych z resztą. Niech b>0 wtedy dla każdej liczby całkowitej a istnieją jednoznacznie wyznaczone: iloraz qi reszta T spełniające: a = bq + r i 0  ≤ r < b .Resztę Tz dzielenia a przez b zapisujemy też jako: a mod b. B dzieli a (lub ajest podzielne przez b), co zapisujemyb|a, jeśli istnieje q takie, że b=aq. W takim wypadku mówimy też, że b jest dzielnikiem a lub, że a jest wielokrotnościąb., jeśli b dzieli a to reszta z dzielenia a przez b równa jest 0 tzn a mod b =0 . Dla dowolnych a,b,c zachodzi: jeśli a|b to a|bc ; jeśli a |b i b|c to a|c; jeśli a|b ,a|c to a|(b+c) Największy wspólny dzielnik liczb a i b (zapisywany przez NWD (a,b), gdzie chociaż jedna z liczb a.b jest różna od0, to największa liczba d taka, że d|a i d|b . Oczywiście, 1≤NWD(a,b) ≤ min(|,|).Najmniejsza wspólna wielokrotność dwu liczb a, b > 0 (oznaczana przez NWW (a,b) to najmniejsza liczba dodatnia w taka, że a|w i b|w . Funkcja φ-Eulera toφ : N − {0} → N zdefiniowaną poprzez $\varphi\left( n \right) = \left| \left\{ 1 \leq a < n:\text{NWD}\left( a,n \right) = 1 \right\} \right|\ \ \ ;\ \varphi(p^{\alpha} - \ p^{\alpha - 1} = \ p^{\alpha}(1 - \frac{1}{p})$ .Dla dowolnych m,n>0 takich, że m⊥nzachodzi :φ(m,n) = φ(m)φ(n) Tw. Eulera : Dla dowolnych a,n gdzie NWD(a,n) =1 zachodzi: α^φ(n) ≡ n 1  Cykl Eulera to zamknięta marszruta przechodząca przez każdą krawędź dokładnie raz Graf eulerowski to graf posiadający cykl Eulera Graf G=V,E)jest eulerowski wtedy i tylko wtedy, gdy jest spójny i stopień każdego wierzchołka jest parzysty. Graf jednokreślny to graf posiadający marszrutę przechodzącą dokładnie raz przez każdą krawędź Graf spójny – graf, w którym między dwoma dowolnymi wierzchołkami istnieje droga Graf skierowany nie ma pętli Graf hamiltonowski to graf posiadający cykl Hamiltona.

Algorytm Euklidesa: to algorytm wyznaczania największego wspólnego dzielnika dwu dodatnich liczb całkowitych 1.Wczytaj a,b >0; 2. Oblicz r jako reszte z a|b; 3.zastap a|b i b|r; 4. Jeżeli b=0 zwroc a, w przeciwnym wypadku przejdz do 2.

NWD (1029, 1071)

A=1029 , b= 1071

1029= 0:1071+ 1029

N= 1025

A= 1071 , b= 1029

1071=1+1029+42

r=42;

a=1029, b =42

1029= 24*42+21

r=21;

a=42, b=21

42=2*21+0

n=0

NWD=21

Euklides (a,b)

If b=0 then return a

Else return Euklides (b,a mod b)

1.R jest zwrotna :∀x∈S (x,x)∈R 2.R jest przeciwzwrotna∈S (x,x) nie nalezy do R; 3.R jest symetryczna ∀x,y∈S(x,y)∈R→(y,x)∈R)

Zasada Minimum (ZMin): Dowolny niepusty podzbiór S zbioru liczb naturalnych N ma w sobie liczbę najmniejszą. Zasada Indukcji Matematycznej (ZIM) Jeżeli Z zawiera się w zbiorze liczb naturalnych N :w którymko należy do Z oraz Z wraz z każdą liczbą naturalną k >= ko zawiera również kolejną liczbę k+1 (tzn. dla każdego k >= ko zachodzi, że jeśli k należy do Z , to k+1 należy do Z), to zbiór Z zawiera wszystkie liczby naturalne n >= ko (tzn. N – {0,1,...,ko-1} zawiera się w Z). Pierwszy warunek nazywamy bazą indukcji (krok podstawowy). W drugim warunku najpierw dokonujemy założenia indukcyjnego (o tym, że k należy do Z),a następnie wykonujemy krok indukcyjny dowodząc, że k+1 należy do Z. Zasada Indukcji Zupełnej (ZIZ) Jeżeli Z jest jakimś zbiorem liczb naturalnych , który wraz z każdym początkowym fragmentem zbioru N postaci {0,1,...,k-1} zawieran również kolejną liczbę k (tzn. dla każdego k należącego do N zachodzi:jeśli (dla każdego l<k jest tak, że l należy do Z), to k+1 należy do Z to Z zawiera wszystkie liczby naturalne (Z=N). Zauważmy, że nie ma tu wyróżnionego kroku bazowego (ukryty jest on w warunku dla k=0, bo poprzednik implikacji jest trywialnie spełniony). Zasada Maksimum (ZMax) Dowolny niepusty i ograniczony od góry podzbiór S zbioru liczb naturalnych ma w sobie liczbę największą Zasada Szufladkowa Dirichleta Jeśli n obiektów jest rozmieszczonych w m szufladach i n>m, to istnieje szuflada z przynajmniej dwoma obiektami. Uogólniona Zasada Szufladkowa Jeśli m obiektów rozmieszczonych jest w n szufladach i m>n*r, dla pewnego naturalnego r, to istnieje szufladka z co najmniej r+1 obiektami.(jeżeli każda szuflada ma co najwyżej r obiektów i n szuflad jest, to w sumie jest co najwyżej n*r obiektów)

Dzielenie liczb całkowitych z resztą. Niech b>0 wtedy dla każdej liczby całkowitej a istnieją jednoznacznie wyznaczone: iloraz qi reszta T spełniające: a = bq + r i 0  ≤ r < b .Resztę Tz dzielenia a przez b zapisujemy też jako: a mod b. B dzieli a (lub ajest podzielne przez b), co zapisujemyb|a, jeśli istnieje q takie, że b=aq. W takim wypadku mówimy też, że b jest dzielnikiem a lub, że a jest wielokrotnościąb., jeśli b dzieli a to reszta z dzielenia a przez b równa jest 0 tzn a mod b =0 . Dla dowolnych a,b,c zachodzi: jeśli a|b to a|bc ; jeśli a |b i b|c to a|c; jeśli a|b ,a|c to a|(b+c) Największy wspólny dzielnik liczb a i b (zapisywany przez NWD (a,b), gdzie chociaż jedna z liczb a.b jest różna od0, to największa liczba d taka, że d|a i d|b . Oczywiście, 1≤NWD(a,b) ≤ min(|,|).Najmniejsza wspólna wielokrotność dwu liczb a, b > 0 (oznaczana przez NWW (a,b) to najmniejsza liczba dodatnia w taka, że a|w i b|w . Funkcja φ-Eulera toφ : N − {0} → N zdefiniowaną poprzez $\varphi\left( n \right) = \left| \left\{ 1 \leq a < n:\text{NWD}\left( a,n \right) = 1 \right\} \right|\ \ \ ;\ \varphi(p^{\alpha} - \ p^{\alpha - 1} = \ p^{\alpha}(1 - \frac{1}{p})$ .Dla dowolnych m,n>0 takich, że m⊥nzachodzi :φ(m,n) = φ(m)φ(n) Tw. Eulera : Dla dowolnych a,n gdzie NWD(a,n) =1 zachodzi: α^φ(n) ≡ n 1  Cykl Eulera to zamknięta marszruta przechodząca przez każdą krawędź dokładnie raz Graf eulerowski to graf posiadający cykl Eulera Graf G=V,E)jest eulerowski wtedy i tylko wtedy, gdy jest spójny i stopień każdego wierzchołka jest parzysty. Graf jednokreślny to graf posiadający marszrutę przechodzącą dokładnie raz przez każdą krawędź Graf spójny – graf, w którym między dwoma dowolnymi wierzchołkami istnieje droga Graf skierowany nie ma pętli Graf hamiltonowski to graf posiadający cykl Hamiltona.

Algorytm Euklidesa: to algorytm wyznaczania największego wspólnego dzielnika dwu dodatnich liczb całkowitych 1.Wczytaj a,b >0; 2. Oblicz r jako reszte z a|b; 3.zastap a|b i b|r; 4. Jeżeli b=0 zwroc a, w przeciwnym wypadku przejdz do 2.

NWD (1029, 1071)

A=1029 , b= 1071

1029= 0:1071+ 1029

N= 1025

A= 1071 , b= 1029

1071=1+1029+42

r=42;

a=1029, b =42

1029= 24*42+21

r=21;

a=42, b=21

42=2*21+0

n=0

NWD=21

Euklides (a,b)

If b=0 then return a

Else return Euklides (b,a mod b)

1.R jest zwrotna :∀x∈S (x,x)∈R 2.R jest przeciwzwrotna∈S (x,x) nie nalezy do R; 3.R jest symetryczna ∀x,y∈S(x,y)∈R→(y,x)∈R)

Zasada mnożenia Dla skończonych zbiorów X,Y zachodzi |X x Y| = |X| * |Y|. Zasada dodawania(a) Dla skończonych i rozłącznych zbiorów A i B mamy: |A υ B| = |A| + |B|.(b) Dla skończonych zbiorów mamy: |A υ B| = |A| + |B| - |A ∩ B|. Zasada włączania i wyłączania Dla zbiorów skończonych {A1, …, An} zachodzi|A₁ υ … υ A_n| = ∑_{I ε {1, … , n}} (-1)^|I|+1 |∩_{i ε I} A_i|= |A₁| + … + |A_n| - |A₁ ∩ A₂| - |A₁ ∩ A₃| - … - |A_n-2 ∩ A_n| - |A_n-1 ∩ A_n|+ |A₁ ∩ A₂ ∩ A₃| + …+ |A_n-2 ∩ A_n-1 ∩ A_n| - |A₁ ∩ A₂ ∩ A₃ ∩ A₄| - … - |A_n-3 ∩ A_n-2 ∩ A_n-1 ∩ A_n|+ …(-1) ⁿ⁺¹ |A₁ ∩ … ∩ A_n|

Zasada Minimum (ZMin): Dowolny niepusty podzbiór S zbioru liczb naturalnych N ma w sobie liczbę najmniejszą. Zasada Indukcji Matematycznej (ZIM) Jeżeli Z zawiera się w zbiorze liczb naturalnych N :w którymko należy do Z oraz Z wraz z każdą liczbą naturalną k >= ko zawiera również kolejną liczbę k+1 (tzn. dla każdego k >= ko zachodzi, że jeśli k należy do Z , to k+1 należy do Z), to zbiór Z zawiera wszystkie liczby naturalne n >= ko (tzn. N – {0,1,...,ko-1} zawiera się w Z). Pierwszy warunek nazywamy bazą indukcji (krok podstawowy). W drugim warunku najpierw dokonujemy założenia indukcyjnego (o tym, że k należy do Z),a następnie wykonujemy krok indukcyjny dowodząc, że k+1 należy do Z. Zasada Indukcji Zupełnej (ZIZ) Jeżeli Z jest jakimś zbiorem liczb naturalnych , który wraz z każdym początkowym fragmentem zbioru N postaci {0,1,...,k-1} zawieran również kolejną liczbę k (tzn. dla każdego k należącego do N zachodzi:jeśli (dla każdego l<k jest tak, że l należy do Z), to k+1 należy do Z to Z zawiera wszystkie liczby naturalne (Z=N). Zauważmy, że nie ma tu wyróżnionego kroku bazowego (ukryty jest on w warunku dla k=0, bo poprzednik implikacji jest trywialnie spełniony). Zasada Maksimum (ZMax) Dowolny niepusty i ograniczony od góry podzbiór S zbioru liczb naturalnych ma w sobie liczbę największą Zasada Szufladkowa Dirichleta Jeśli n obiektów jest rozmieszczonych w m szufladach i n>m, to istnieje szuflada z przynajmniej dwoma obiektami. Uogólniona Zasada Szufladkowa Jeśli m obiektów rozmieszczonych jest w n szufladach i m>n*r, dla pewnego naturalnego r, to istnieje szufladka z co najmniej r+1 obiektami.(jeżeli każda szuflada ma co najwyżej r obiektów i n szuflad jest, to w sumie jest co najwyżej n*r obiektów) Dzielenie liczb całkowitych z resztą. Niech b>0 wtedy dla każdej liczby całkowitej a istnieją jednoznacznie wyznaczone: iloraz qi reszta T spełniające: a = bq + r i 0  ≤ r < b .Resztę Tz dzielenia a przez b zapisujemy też jako: a mod b. B dzieli a (lub ajest podzielne przez b), co zapisujemyb|a, jeśli istnieje q takie, że b=aq. W takim wypadku mówimy też, że b jest dzielnikiem a lub, że a jest wielokrotnościąb., jeśli b dzieli a to reszta z dzielenia a przez b równa jest 0 tzn a mod b =0 . Dla dowolnych a,b,c zachodzi: jeśli a|b to a|bc ; jeśli a |b i b|c to a|c; jeśli a|b ,a|c to a|(b+c) Największy wspólny dzielnik liczb a i b (zapisywany przez NWD (a,b), gdzie chociaż jedna z liczb a.b jest różna od0, to największa liczba d taka, że d|a i d|b . Oczywiście, 1≤NWD(a,b) ≤ min(|,|).Najmniejsza wspólna wielokrotność dwu liczb a, b > 0 (oznaczana przez NWW (a,b) to najmniejsza liczba dodatnia w taka, że a|w i b|w . Funkcja φ-Eulera toφ : N − {0} → N zdefiniowaną poprzez $\varphi\left( n \right) = \left| \left\{ 1 \leq a < n:\text{NWD}\left( a,n \right) = 1 \right\} \right|\ \ \ ;\ \varphi(p^{\alpha} - \ p^{\alpha - 1} = \ p^{\alpha}(1 - \frac{1}{p})$ .Dla dowolnych m,n>0 takich, że m⊥nzachodzi :φ(m,n) = φ(m)φ(n) Tw. Eulera : Dla dowolnych a,n gdzie NWD(a,n) =1 zachodzi: α^φ(n) ≡ n 1  Cykl Eulera to zamknięta marszruta przechodząca przez każdą krawędź dokładnie raz Graf eulerowski to graf posiadający cykl Eulera Graf G=V,E)jest eulerowski wtedy i tylko wtedy, gdy jest spójny i stopień każdego wierzchołka jest parzysty. Graf jednokreślny to graf posiadający marszrutę przechodzącą dokładnie raz przez każdą krawędź Graf spójny – graf, w którym między dwoma dowolnymi wierzchołkami istnieje droga Graf skierowany nie ma pętli Graf hamiltonowski to graf posiadający cykl Hamiltona.

Algorytm Euklidesa: to algorytm wyznaczania największego wspólnego dzielnika dwu dodatnich liczb całkowitych 1.Wczytaj a,b >0; 2. Oblicz r jako reszte z a|b; 3.zastap a|b i b|r; 4. Jeżeli b=0 zwroc a, w przeciwnym wypadku przejdz do 2.

NWD (1029, 1071)

A=1029 , b= 1071

1029= 0:1071+ 1029

N= 1025

A= 1071 , b= 1029

1071=1+1029+42

r=42;

a=1029, b =42

1029= 24*42+21

r=21;

a=42, b=21

42=2*21+0

n=0

NWD=21

Euklides (a,b)

If b=0 then return a

Else return Euklides (b,a mod b)

1.R jest zwrotna :∀x∈S (x,x)∈R 2.R jest przeciwzwrotna∈S (x,x) nie nalezy do R; 3.R jest symetryczna ∀x,y∈S(x,y)∈R→(y,x)∈R)

Zasada mnożenia Dla skończonych zbiorów X,Y zachodzi |X x Y| = |X| * |Y|. Zasada dodawania(a) Dla skończonych i rozłącznych zbiorów A i B mamy: |A υ B| = |A| + |B|.(b) Dla skończonych zbiorów mamy: |A υ B| = |A| + |B| - |A ∩ B|. Zasada włączania i wyłączania Dla zbiorów skończonych {A1, …, An} zachodzi|A₁ υ … υ A_n| = ∑_{I ε {1, … , n}} (-1)^|I|+1 |∩_{i ε I} A_i|= |A₁| + … + |A_n| - |A₁ ∩ A₂| - |A₁ ∩ A₃| - … - |A_n-2 ∩ A_n| - |A_n-1 ∩ A_n|+ |A₁ ∩ A₂ ∩ A₃| + …+ |A_n-2 ∩ A_n-1 ∩ A_n| - |A₁ ∩ A₂ ∩ A₃ ∩ A₄| - … - |A_n-3 ∩ A_n-2 ∩ A_n-1 ∩ A_n|+ …(-1) ⁿ⁺¹ |A₁ ∩ … ∩ A_n|

Zasada Minimum (ZMin): Dowolny niepusty podzbiór S zbioru liczb naturalnych N ma w sobie liczbę najmniejszą. Zasada Indukcji Matematycznej (ZIM) Jeżeli Z zawiera się w zbiorze liczb naturalnych N :w którymko należy do Z oraz Z wraz z każdą liczbą naturalną k >= ko zawiera również kolejną liczbę k+1 (tzn. dla każdego k >= ko zachodzi, że jeśli k należy do Z , to k+1 należy do Z), to zbiór Z zawiera wszystkie liczby naturalne n >= ko (tzn. N – {0,1,...,ko-1} zawiera się w Z). Pierwszy warunek nazywamy bazą indukcji (krok podstawowy). W drugim warunku najpierw dokonujemy założenia indukcyjnego (o tym, że k należy do Z),a następnie wykonujemy krok indukcyjny dowodząc, że k+1 należy do Z. Zasada Indukcji Zupełnej (ZIZ) Jeżeli Z jest jakimś zbiorem liczb naturalnych , który wraz z każdym początkowym fragmentem zbioru N postaci {0,1,...,k-1} zawieran również kolejną liczbę k (tzn. dla każdego k należącego do N zachodzi:jeśli (dla każdego l<k jest tak, że l należy do Z), to k+1 należy do Z to Z zawiera wszystkie liczby naturalne (Z=N). Zauważmy, że nie ma tu wyróżnionego kroku bazowego (ukryty jest on w warunku dla k=0, bo poprzednik implikacji jest trywialnie spełniony). Zasada Maksimum (ZMax) Dowolny niepusty i ograniczony od góry podzbiór S zbioru liczb naturalnych ma w sobie liczbę największą Zasada Szufladkowa Dirichleta Jeśli n obiektów jest rozmieszczonych w m szufladach i n>m, to istnieje szuflada z przynajmniej dwoma obiektami. Uogólniona Zasada Szufladkowa Jeśli m obiektów rozmieszczonych jest w n szufladach i m>n*r, dla pewnego naturalnego r, to istnieje szufladka z co najmniej r+1 obiektami.(jeżeli każda szuflada ma co najwyżej r obiektów i n szuflad jest, to w sumie jest co najwyżej n*r obiektów)

Dzielenie liczb całkowitych z resztą. Niech b>0 wtedy dla każdej liczby całkowitej a istnieją jednoznacznie wyznaczone: iloraz qi reszta T spełniające: a = bq + r i 0  ≤ r < b .Resztę Tz dzielenia a przez b zapisujemy też jako: a mod b. B dzieli a (lub ajest podzielne przez b), co zapisujemyb|a, jeśli istnieje q takie, że b=aq. W takim wypadku mówimy też, że b jest dzielnikiem a lub, że a jest wielokrotnościąb., jeśli b dzieli a to reszta z dzielenia a przez b równa jest 0 tzn a mod b =0 . Dla dowolnych a,b,c zachodzi: jeśli a|b to a|bc ; jeśli a |b i b|c to a|c; jeśli a|b ,a|c to a|(b+c) Największy wspólny dzielnik liczb a i b (zapisywany przez NWD (a,b), gdzie chociaż jedna z liczb a.b jest różna od0, to największa liczba d taka, że d|a i d|b . Oczywiście, 1≤NWD(a,b) ≤ min(|,|).Najmniejsza wspólna wielokrotność dwu liczb a, b > 0 (oznaczana przez NWW (a,b) to najmniejsza liczba dodatnia w taka, że a|w i b|w . Funkcja φ-Eulera toφ : N − {0} → N zdefiniowaną poprzez $\varphi\left( n \right) = \left| \left\{ 1 \leq a < n:\text{NWD}\left( a,n \right) = 1 \right\} \right|\ \ \ ;\ \varphi(p^{\alpha} - \ p^{\alpha - 1} = \ p^{\alpha}(1 - \frac{1}{p})$ .Dla dowolnych m,n>0 takich, że m⊥nzachodzi :φ(m,n) = φ(m)φ(n) Tw. Eulera : Dla dowolnych a,n gdzie NWD(a,n) =1 zachodzi: α^φ(n) ≡ n 1  Cykl Eulera to zamknięta marszruta przechodząca przez każdą krawędź dokładnie raz Graf eulerowski to graf posiadający cykl Eulera Graf G=V,E)jest eulerowski wtedy i tylko wtedy, gdy jest spójny i stopień każdego wierzchołka jest parzysty. Graf jednokreślny to graf posiadający marszrutę przechodzącą dokładnie raz przez każdą krawędź Graf spójny – graf, w którym między dwoma dowolnymi wierzchołkami istnieje droga Graf skierowany nie ma pętli Graf hamiltonowski to graf posiadający cykl Hamiltona.

Algorytm Euklidesa: to algorytm wyznaczania największego wspólnego dzielnika dwu dodatnich liczb całkowitych 1.Wczytaj a,b >0; 2. Oblicz r jako reszte z a|b; 3.zastap a|b i b|r; 4. Jeżeli b=0 zwroc a, w przeciwnym wypadku przejdz do 2.

NWD (1029, 1071)

A=1029 , b= 1071

1029= 0:1071+ 1029

N= 1025

A= 1071 , b= 1029

1071=1+1029+42

r=42;

a=1029, b =42

1029= 24*42+21

r=21;

a=42, b=21

42=2*21+0

n=0

NWD=21

Euklides (a,b)

If b=0 then return a

Else return Euklides (b,a mod b)

1.R jest zwrotna :∀x∈S (x,x)∈R 2.R jest przeciwzwrotna∈S (x,x) nie nalezy do R; 3.R jest symetryczna ∀x,y∈S(x,y)∈R→(y,x)∈R)