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
Twierdzenie o reszcie z dzielenia
Twierdzenie o reszcie z dzielenia
Często udowadniając jakieś własności dotyczące arytmetyki modularnej używamy twierdzenia o dzieleniu z resztą.
To prosty pomysł pochodzący bezpośrednio z algorytmu dzielenia pod kreską.
To prosty pomysł pochodzący bezpośrednio z algorytmu dzielenia pod kreską.
Treść twierdzenia o dzieleniu z resztą jest następująca:
Dla każdej liczby całkowitej A i każdej liczby naturalnej B, istnieją jednoznacznie wyznaczone liczby całkowite Q oraz R spełniające równanie
Dla każdej liczby całkowitej A i każdej liczby naturalnej B, istnieją jednoznacznie wyznaczone liczby całkowite Q oraz R spełniające równanie
A= B * Q + R, gdzie 0 ≤ R < B
Twierdzenie to pochodzi dokładnie z algorytmu dzielenia pisemnego, albo "dzielenia pod kreską". Kiedy dzielimy A przez B, Q nazywa się ilorazem a R nazywa się resztą z dzielenia.
Oczywiście, prawdziwe jest równanie A mod B = R
Oczywiście, prawdziwe jest równanie A mod B = R
Przykłady
A = 7, B = 2
7 = 2 * 3 + 1
7 mod 2 = 1
7 mod 2 = 1
A = 8, B = 4
8 = 4 * 2 + 0
8 mod 4 = 0
8 mod 4 = 0
A = 13, B = 5
13 = 5 * 2 + 3
13 mod 5 = 3
13 mod 5 = 3
A = -16, B = 26
-16 = 26 * -1 + 10
-16 mod 26 = 10
-16 mod 26 = 10
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji