Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 2
Lekcja 5: Arytmetyka modularna- Co to jest arytmetyka modularna?
- Operator modulo
- Wyzwanie modulo
- Przystawanie modulo
- Relacja przystawania
- Relacje równoważności
- Twierdzenie o reszcie z dzielenia
- Dodawanie i odejmowanie modularne
- Dodawanie modularne
- Wyzwanie modulo (dodawanie i odejmowanie)
- Mnożenie modularne
- Mnożenie modularne
- Potęgowanie modularne
- Szybkie potęgowanie modularne
- Szybkie potęgowanie modularne
- Odwrotność modularna
- Algorytm Euklidesa
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Algorytm Euklidesa
Przypomnijmy, że Największy Wspólny Dzielnik (NWD) dwu liczb całkowitych A i B jest największą liczbą całkowitą, która dzieli A oraz B.
Algorytm Euklidesa pozwala na szybkie znalezienie NWD dwóch liczb całkowitych.
Algorytm
Algorytm Euklidesa znajdujący NWD(A,B) wygląda tak:
- Jeśli A = 0, to NWD(A,B)=B (gdyż NWD(0,B)=B) i możemy się zatrzymać.
- Jeśli B = 0, to NWD(A,B)=A (gdyż NWD(A,0)=0) i możemy się zatrzymać.
- Wykonaj dzielenie z resztą A = B⋅Q + R
- Oblicz NWD(B,R) stosując Algorytm Euklidesa i użyj NWD(A,B) = NWD(B,R).
Przykład:
Znajdź NWD liczb 270 i 192:
- A=270, B=192
- A ≠0
- B ≠0
- Używając dzielenia pod kreską mamy 270/192 = 1 z resztą 78. Możemy to zapisać jako 270 = 192 * 1 + 78
- Obliczamy NWD(192,78), by użyć NWD(270,192)=NWD(192,78)
A=192, B=78
- A ≠0
- B ≠0
- Używając dzielenia pod kreską mamy 192/78 = 2 z resztą 36. Możemy to zapisać jako:
- 192 = 78 * 2 + 36
- Obliczamy NWD(78,36), by użyć NWD(192,78)=NWD(78,36)
A=78, B=36
- A ≠0
- B ≠0
- Używając dzielenia pod kreską mamy 78/36 = 2 z resztą 6. Możemy to zapisać jako:
- 78 = 36 * 2 + 6
- Obliczamy NWD(36,6), by użyć NWD(78,36)=NWD(36,6)
A=36, B=6
- A ≠0
- B ≠0
- Używając dzielenia pod kreską mamy 36/6 = 6 z resztą 0. Możemy to zapisać jako:
- 36 = 6 * 6 + 0
- Obliczamy NWD(6,0), by użyć NWD(36,6)=NWD(6,0)
A=6, B=0
- A ≠0
- B =0, NWD(6,0)=6
Pokazaliśmy więc:
NWD(270,192) = NWD(192,78) = NWD(78,36) = NWD(36,6) = NWD(6,0) = 6
NWD(270,192) = 6
Zastanówmy się, dlaczego Algorytm Euklidesa działa
Przyglądając się uważnie algorytmowi Euklidesa, widzimy, że korzysta z następujących własności:
- NWD(A,0) = A
- NWD(0,B) = B
- Jeśli A = B⋅Q + R i B≠0, to NWD(A,B) = NWD(B,R), gdzie Q jest liczbą całkowitą, a R liczbą całkowitą w przedziale od 0 do B-1
Dwie pierwsze własności wyznaczają NWD dwu liczb, gdy jedną z nich jest zero. Trzecia pozwala nam sprowadzić problem większy, bardziej skomplikowany, do mniejszego, łatwiejszego do rozwiązania.
Algorytm Euklidesa wykorzystuje trzecią własność, krok po kroku sprowadzając zadanie do coraz prostszych przypadków, aż wreszcie uda się je rozwiązać dzięki dwu pierwszym własnościom.
By zrozumieć te trzy własności, dowiedziemy ich.
Możemy udowodnić, że NWD(A,0)=A następująco:
- Największą liczbą całkowitą, która dzieli A jest A.
- Każda liczba całkowita dzieli 0, gdyż dla każdej liczby całkowitej C mamy C⋅0 = 0. Zatem A dzieli 0.
- Największą liczbą, która dzieli A oraz 0 jest A.
Własności NWD(0,B)=B dowodzimy podobnie (jak wyżej, tylko z B w miejscu A).
By udowodnić NWD(A,B)=NWD(B,R), pokażemy wpierw, że NWD(A,B)=NWD(B,A-B).
Niech A,B i C będą trzema liczbami całkowitymi takimi, że A-B=C.
Pokazujemy, że NWD(A,B) dzieli C
NWD(A,B) dzieli A z definicji. Stąd A musi być wielokrotnością NWD(A,B), tj. X⋅NWD(A,B)=A, gdzie X jest pewną liczbą całkowitą
NWD(A,B) dzieli B z definicji. Stąd B musi być wielokrotnością NWD(A,B), tj. Y⋅NWD(A,B)=B, gdzie Y jest pewną liczbą całkowitą
A-B=C daje:
- X⋅NWD(A,B) - Y⋅NWD(A,B) = C
- (X - Y)⋅NWD(A,B) = C
Widzimy zatem, że NWD(A,B) dzieli C.
Tę część dowodu zilustrowano poniżej:
Dowód, że NWD(B,C) jest dzielnikiem A
NWD(B,C) dzieli B z definicji. Stąd B musi być wielokrotnością NWD(B,C), tj. M⋅NWD(B,C)=B, gdzie M jest pewną liczbą całkowitą
NWD(B,C) dzieli C z definicji. Stąd C musi być pewną wielokrotnością NWD(B,C), tj. N⋅NWD(B,C)=C, gdzie N jest pewną liczbą całkowitą
A-B=C daje:
- B+C=A
- M⋅NWD(B,C) + N⋅NWD(B,C) = A
- (M + N)⋅NWD(B,C) = A
Widzimy zatem, że NWD(B,C) dzieli A.
Tę część dowodu zilustrowano poniżej
Dowód, że GCD(A,B)=GCD(A,A-B)
- NWD(A,B) dzieli B z definicji.
- Pokazaliśmy, że NWD(A,B) dzieli C.
- Skoro NWD(A,B) dzieli zarówno B, jak i C, jest wspólnym dzielnikiem B i C.
NWD(A,B) jest mniejszy, bądź równy NWD(B,C), ponieważ NWD(B,C) jest największym wspólnym dzielnikiem B i C.
- NWD(B,C) dzieli B z definicji.
- Pokazaliśmy, że NWD(B,C) dzieli A.
- Skoro NWD(B,C) dzieli zarówno A, jak i B, jest wspólnym dzielnikiem A i B.
NWD(B,C) jest mniejszy, bądź równy NWD(A,B), ponieważ NWD(A,B) jest największym wspólnym dzielnikiem A i B.
Mając NWD(A,B)≤NWD(B,C) i NWD(B,C)≤NWD(A,B) stwierdzamy, że:
NWD(A,B)=NWD(B,C)
Co jest równoważne:
NWD(A,B)=NWD(B,A-B)
Dowód ten zilustrowano w prawej części poniższego rysunku.
Dowód, że NWD(A,B)=NWD(B,R)
Pokazaliśmy, że NWD(A,B)=NWD(B,A-B)
Kolejność argumentów nie ma znaczenia, więc możemy napisać NWD(A,B)=NWD(A-B,B)
Możemy wielokrotnie użyć tożsamości NWD(A,B)=NWD(A-B,B), dostając:
NWD(A,B)=NWD(A-B,B)=NWD(A-2B,B)=NWD(A-3B,B)=...=NWD(A-Q⋅B,B)
Ale A= B⋅Q + R, więc A-Q⋅B=R
Zatem NWD(A,B)=NWD(R,B)
Kolejność argumentów nie ma znaczenia, więc
NWD(A,B)=NWD(B,R)
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji