Co dalej policzyć?
Jeśli pracujesz z resztami z dzielenia albo matematyką dyskretną, przydadzą Ci się także te narzędzia.
Do czego służy kalkulator kongruencji liniowych?
Rozwiązuje równania postaci a·x ≡ b (mod m). Najpierw sprawdza, czy rozwiązania istnieją, następnie upraszcza równanie i wyznacza rozwiązanie bazowe.
Jeżeli rozwiązań jest kilka, wszystkie w jednym okresie modulo m różnią się od siebie o m / NWD(a,m).
Jak to policzyć?
Równanie a·x ≡ b (mod m) ma rozwiązanie wtedy i tylko wtedy, gdy NWD(a,m) dzieli b.
Jeżeli warunek jest spełniony, dzielimy całe równanie przez d, a potem korzystamy z odwrotności modularnej.
Przykład: 14x ≡ 30 (mod 100)
NWD(14,100)=2, a 2 dzieli 30. Po podzieleniu przez 2 otrzymujemy 7x ≡ 15 (mod 50).
Odwrotność 7 modulo 50 wynosi 43, więc x ≡ 45 (mod 50). W zakresie 0 ≤ x < 100 rozwiązaniami są 45 i 95.
Zadania z odpowiedziami
Odpowiedź 1: x ≡ 45 (mod 50), czyli 45 i 95 w zakresie 0 ≤ x < 100.
Odpowiedź 2: Nie, bo NWD(6,9)=3, a 3 nie dzieli 5.
Odpowiedź 3: x ≡ 2 (mod 3), czyli 2, 5 i 8 modulo 9.
Odpowiedź 4: Tak, bo 14·95 mod 100 = 30.
Kilka przykładów
Najczęstsze błędy
- Pomijanie NWD(a,m) | b — wtedy można szukać rozwiązania tam, gdzie go nie ma.
- Dzielenie kongruencji jak zwykłego równania — najpierw trzeba uwzględnić NWD.
- Podawanie tylko jednego x — gdy NWD(a,m) > 1, rozwiązań modulo m jest kilka.
- Mylenie rozwiązania bazowego z całą klasą — zapis x ≡ x₀ (mod m′) opisuje wiele liczb.
Ciekawostka
Kongruencje liniowe są używane w teorii liczb, kryptografii, generatorach liczb pseudolosowych i zadaniach związanych z resztami modulo.
Wskazówka
Najpierw policz NWD(a,m). Dopiero gdy NWD dzieli b, przechodź do upraszczania równania i szukania odwrotności modularnej.