Algorytm Euklidesa

Algorytm Euklidesa – czym jest i jak go stosować?

Kiedy został wynaleziony oraz do czego służy algorytm Euklidesa?
Za pomocą algorytmu Euklidesa możemy wyznaczyć Największy Wspólny Dzielnik dwóch liczb całkowitych. Jest to jeden z najstarszych algorytmów. Został on opisany przez Euklidesa około 300 roku p.n.e. w dziele Elementy, dokładniej w księgach siódmej oraz dziesiątej.

Jak wygląda algorytm Euklidesa?
Pierwszy sposób z mnożeniem – bardziej popularny
Aby obliczyć Największy Wspólny Dzielnik liczb całkowitych a i b w skrócie NWD (a, b) (przy założeniu, że a > b) należy podzielić z resztą liczbę a przez liczbę b. Następnie jeżeli otrzymana reszta z dzielenia jest równa 0, to NWD (a, b) = b, w przeciwnym wypadku należy przypisać liczbie a wartość liczby b, a liczbie b wartość otrzymanej reszty. Po takim przypisaniu nowych wartości liczbom a i b należy ponownie wykonać dzielenie z resztą liczby a przez liczbę b. Takie dzielenie wykonujemy do momentu uzyskania reszty równej 0. W przypadku, gdy b = 0, to NWD (a, b) = NWD (a, 0) = a, ponieważ 0 jest podzielne przez każdą liczbę naturalną, czyli największą liczbą dzielącą 0 i a jest a.

Drugi sposób z odejmowaniem
Aby obliczyć Największy Wspólny Dzielnik liczb całkowitych a i b w skrócie NWD (a, b) należy od większej liczby odjąć mniejszą. Następnie porównujemy ze sobą liczbę mniejszą z otrzymaną różnicą. Jeśli te liczby są sobie równe, to jest to szukany przez nas NWD, w przeciwnym wypadku liczbę większą zastępujemy otrzymaną różnicą i znów wykonujemy odejmowanie. Takie odejmowanie wykonujemy do momentu, gdy mniejsza liczba jest równa różnicy.

Przykłady zastosowania algorytmu Euklidesa – pierwszy sposób z dzieleniem

Przykład 1
Należy obliczyć NWD (459, 85).
459 : 85 = 5, reszty 34, teraz a = 85, b = 34;
85 : 34 = 2, reszty 17, teraz a = 34, b = 17;
34 : 17 = 2, reszty 0, teraz a = 17, b = 0.
Zatem NWD (459, 85) = 17.

Przykład 2
Należy obliczyć NWD (298, 112).
298 : 112 = 2, reszty 74, teraz a = 112, b = 74;
112 : 74 = 1, reszty 38, teraz a = 74, b = 38;
74 : 38 = 1, reszty 36, teraz a = 38, b = 36;
38 : 36 = 1, reszty 2, teraz a = 36, b = 2;
36 : 2 = 18, reszty 0, teraz a = 2, b = 0.
Zatem NWD (298, 112) = 2.

Przykład 3
Należy obliczyć NWD (357, 11).
357 : 11 = 32, reszty 5, teraz a = 11, b = 5;
11 : 5 = 2, reszty 1, teraz a = 5, b = 1;
5 : 1 = 5, reszty 0, teraz a = 1, b = 0.
Zatem NWD (357, 11) = 1. Ze względu na to, że Największy Wspólny Dzielnik jest równy 1, to liczby 357 i 11 nazywamy względnie pierwszymi.

Przykład 4
Należy obliczyć NWD (1565, 190).
1565 : 190 = 8, reszty 45, teraz a = 190, b = 45;
190 : 45 = 4, reszty 10, teraz a = 45, b = 10;
45 : 10 = 4, reszty 5, teraz a = 10, b = 5;
10 : 5 = 2, reszty 0, teraz a = 5, b = 0.
Zatem NWD (1565, 190) = 5.

Przykład 5
Należy obliczyć NWD (4782, 243).
4782 : 243 = 19, reszty 165, teraz a = 243, b = 165;
243 : 165 = 1, reszty 78, teraz a = 165, b = 78;
165 : 78 = 2, reszty 9, teraz a = 78, b = 9;
78 : 9 = 8, reszty 6, teraz a = 9, b = 6;
9 : 6 = 1, reszty 3, teraz a = 6, b = 3;
6 : 3 = 2, reszty 0, teraz a = 3, b = 0.
Zatem NWD (4782, 242) = 3.

Przykład 6
Należy obliczyć NWD (2456, 1278).
2456 : 1278 = 1, reszty 1178, teraz a = 1278, b = 1178;
1278 : 1178 = 1, reszty 100, teraz a = 1178, b = 100;
1178 : 100 = 11, reszty 78, teraz a = 100, b = 78;
100 : 78 = 1, reszty 22, teraz a = 78, b = 22;
78 : 22 = 3, reszty 12, teraz a = 22, b = 12;
22 : 12 = 1, reszty 10, teraz a = 12, b = 10;
12 : 10 = 1, reszty 2, teraz a = 10, b = 2;
10 : 2 = 5, reszty 0, teraz a = 2, b = 0.
Zatem NWD (2456, 1278) = 2.

Przykład 7
Należy obliczyć NWD (2505, 1545).
2505 : 1545 = 1, reszty 960, teraz a = 1545, b = 960;
1545 : 960 = 1, reszty 585, teraz a = 960, b = 585;
960 : 585 = 1, reszty 375, teraz a = 585, b = 375;
585 : 375 = 1, reszty 210, teraz a = 375, b = 210;
375 : 210 = 1, reszty 165, teraz a = 210, b = 165;
210 : 165 = 1, reszty 45, teraz a = 165, b = 45;
165 : 45 = 3, reszty 30, teraz a = 45, b = 30;
45 : 30 = 1, reszty 15, teraz a = 30, b = 15;
30 : 15 = 2, reszty 0, teraz a = 15, b = 0.
Zatem NWD (2505, 1545) = 15.

Przykłady zastosowania algorytmu Euklidesa – drugi sposób z odejmowaniem

Przykład 1
Należy obliczyć NWD (100, 28).
100 – 28 = 72, teraz a = 72, b = 28;
72 – 28 = 44, teraz a = 44, b = 28;
44 – 28 = 16, teraz a = 16, b = 28;
28 – 16 = 12, teraz a = 16, b = 12;
16 – 12 = 4, teraz a = 4, b = 12;
12 – 4 = 8, teraz a = 4, b = 8;
8 – 4 = 4, teraz a = 4, b = 4.
Ponieważ a = b =4, to NWD (100, 28) = 4.

Przykład 2
Należy obliczyć NWD (72, 56).
72 – 56 = 16, teraz a = 16, b = 56;
56 – 16 = 40, teraz a = 16, b = 40;
40 – 16 = 24, teraz a = 16, b = 24;
24 – 16 = 8, teraz a = 16, b = 8;
16 – 8 = 8, teraz a = 8, b = 8.
Ponieważ a = b = 8, to NWD (72, 56) = 8.

Przykład 3
Należy obliczyć NWD (225, 80).
225 – 80 = 145, teraz a = 145, b = 80;
145 – 80 = 65, teraz a = 65, b = 80;
80 – 65 = 15, teraz a = 65, b = 15;
65 – 15 = 50, teraz a = 50, b = 15;
50 – 15 = 35, teraz a = 35, b = 15;
35 – 15 = 20, teraz a = 20, b = 15;
20 – 15 = 5, teraz a = 5, b = 15;
15 – 5 = 10. teraz a = 5, b = 10;
10 – 5 = 5, teraz a = 5, b = 5.
Ponieważ a = b = 5, to NWD (225, 80) = 5.

Przykład 4
Należy obliczyć NWD (297, 77).
297 – 77 = 220, teraz a = 220, b = 77;
220 – 77 = 143, teraz a = 143, b = 77;
143 – 77 = 66, teraz a = 66, b = 77;
77 – 66 = 11, teraz a = 66, b = 11;
66 – 11 = 55, teraz a = 55, b = 11;
55 – 11 = 44, teraz a = 44, b = 11;
44 – 11 = 33, teraz a = 33, b = 11;
33 – 11 = 22. teraz a = 22, b = 11;
22 – 11 = 11, teraz a = 11, b = 11.
Ponieważ a = b = 11, to NWD (297, 77) = 11.

Przykład 5
Należy obliczyć NWD (369, 117).
369 – 117 = 252, teraz a = 252, b = 117;
252 – 117 = 135, teraz a = 135, b = 117;
135 – 117 = 18, teraz a = 18, b = 117;
117 – 18 = 99, teraz a = 18, b = 99;
99 – 18 = 81, teraz a = 18, b = 81;
81 – 18 = 63, teraz a = 18, b = 63;
63 – 18 = 45, teraz a = 18, b = 45;
45 – 18 = 27. teraz a = 18, b = 27;
27 – 18 = 9, teraz a = 18, b = 9;
18 – 9 = 9. teraz a = 9, b = 9.
Ponieważ a = b = 9, to NWD (369, 117) = 9.

Przykład 6
Należy obliczyć NWD (301, 119).
301 – 119 = 182, teraz a = 182, b = 119;
182 – 119 = 63, teraz a = 63, b = 119;
119 – 63 = 56, teraz a = 63, b = 56;
63 – 56 = 7, teraz a = 7, b = 56;
56 – 7 = 49, teraz a = 7, b = 49;
49 – 7 = 42, teraz a = 7, b = 42;
42 – 7 = 35, teraz a = 7, b = 35;
35 – 7 = 28, teraz a = 7, b = 28;
28 – 7 = 21, teraz a = 7, b = 21;
21 – 7 = 14, teraz a = 7, b = 14;
14 – 7 = 7, teraz a = 7, b = 7.
Ponieważ a = b = 7, to NWD (301, 119) = 7.

Przykład 7
Należy obliczyć NWD (1748, 1254).
1748 – 1254 = 494, teraz a = 494, b = 1254;
1254 – 494 = 760, teraz a = 494, b = 760;
760 – 494 = 266, teraz a = 494, b = 266;
494 – 266 = 228, teraz a = 228, b = 266;
266 – 228 = 38, teraz a = 228, b = 38;
228 – 38 = 190, teraz a = 190, b = 38;
190 – 38 = 152, teraz a = 152, b = 38;
152 – 38 = 114, teraz a = 114, b = 38;
114 – 38 = 76, teraz a = 76, b = 38;
76 – 38 = 38, teraz a = 38, b = 38.
Ponieważ a = b = 38, to NWD (1748, 1254) = 38.

Po przeczytaniu tego artykułu wyznaczenie Największego Wspólnego Dzielnika nie powinno stanowić dla Ciebie najmniejszego problemu.