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|A1 υ … υ An| = ∑I ε {1, … , n} (-1)|I|+1 |∩i ε I Ai|= |A1| + … + |An| - |A1 ∩ A2| - |A1 ∩ A3| - … - |An-2 ∩ An| - |An-1 ∩ An|+ |A1 ∩ A2 ∩ A3| + …+ |An-2 ∩ An-1 ∩ An| - |A1 ∩ A2 ∩ A3 ∩ A4| - … - |An-3 ∩ An-2 ∩ An-1 ∩ An|+ …(-1) n+1 |A1 ∩ … ∩ An|
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|A1 υ … υ An| = ∑I ε {1, … , n} (-1)|I|+1 |∩i ε I Ai|= |A1| + … + |An| - |A1 ∩ A2| - |A1 ∩ A3| - … - |An-2 ∩ An| - |An-1 ∩ An|+ |A1 ∩ A2 ∩ A3| + …+ |An-2 ∩ An-1 ∩ An| - |A1 ∩ A2 ∩ A3 ∩ A4| - … - |An-3 ∩ An-2 ∩ An-1 ∩ An|+ …(-1) n+1 |A1 ∩ … ∩ An|
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|A1 υ … υ An| = ∑I ε {1, … , n} (-1)|I|+1 |∩i ε I Ai|= |A1| + … + |An| - |A1 ∩ A2| - |A1 ∩ A3| - … - |An-2 ∩ An| - |An-1 ∩ An|+ |A1 ∩ A2 ∩ A3| + …+ |An-2 ∩ An-1 ∩ An| - |A1 ∩ A2 ∩ A3 ∩ A4| - … - |An-3 ∩ An-2 ∩ An-1 ∩ An|+ …(-1) n+1 |A1 ∩ … ∩ An|
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)