Arytmetyka modularna

03.12.2009 - Krzysztof Piecuch
TrudnośćTrudność

Rozwiązywanie liniowych równań modularnych

Powiedzmy, że szukamy liczbę $ x $, taką która spełnia następujące liniowe równanie modularne:

$ 3x + 2 \equiv 1 \pmod 5 $

Będziemy przekształcać to równanie, aż go rozwiążemy. Zaczniemy od przerzucenia liczby $ 2 $ na prawą stronę równania:

$ 3x \equiv -1 \pmod 5 $

Teraz spróbujemy pozbyć się minusa z prawej strony. Możemy to zrobić dodając coś do prawej strony. Jednak jednocześnie nie chcemy psuć lewej strony. Korzystając zatem z tego, że $ 0 \equiv 5 \pmod 5 $ możemy dodać 5 do prawej strony nie dodając nic do lewej.

$ 3x \equiv 4 \pmod 5 $

W zwykłej równośli liniowej $ 3x = 4 $ podzielilibyśmy teraz obie strony przez 3. Czyli innymi słowy pomnożylibyśmy obie strony przez $ 3^{-1} $. Zrobimy coś podobnego - jednak ponieważ jest to równanie modularne, przemnożymy obie stron przez $ (3^{-1} mod 5) $, czyli przez 2.

$ 6x \equiv 8 \pmod 5 $

Wiemy, że dla dowolnego x zachodzi $ 5x \equiv 5 \pmod 5 $. $ 5x $ aby otrzymać samo $ x $ z lewej strony, oraz $ 5 $ aby otrzymać liczbę z przedziału $ [0, 5) $ z prawej. Odejmijmy to równanie od naszego i ostatecznie otrzymamy rozwiązanie naszego zadania:

$ x \equiv 3 \pmod 5 $

Zatem $ x $ jest postaci: $ x = 5k + 3 $. Są to jedyne rozwiązania tego równania. Zatem w przedziale $ [0, 5) $ istnieje tylko jedno rozwiązanie - $ x = 3 $. Istnieją jednak równania które mają więcej rozwiązań. Rozważmy na przykład równanie: $ 3x \equiv 3 \pmod 6 $. To równanie ma aż 3 rozwiązania: $ x = 1; x = 3; x = 5 $. Bo dzieląc wszystkie trzy liczby przez 3 otrzymamy: $ x \equiv 1 \pmod 2 $. Natomiast równanie: $  3x \equiv 1 \pmod 6) $ w ogóle nie ma rozwiązania. To dlatego, że w tym miejscu chcielibyśmy się pozbyć trójki przy iksie. Nie możemy tego zrobić, bo $ 3 $ nie ma odwrotności modulo 6. Nie możemy też przez nic podzielić wszystkich trzech liczb, bo największy wspólny dzielnik tych wszystkich liczb wynosi... 1. Ogólniej mówiąc: $ ax \equiv b \pmod n $ ma rozwiązanie wtedy i tylko wtedy gdy $ gcd(a, n) | b $. Dowód tego faktu nie jest bardzo skomplikowany, ale pominiemy go.

Jeśli równanie $ ax \equiv b \pmod n  $ ma w ogóle rozwiązanie, to ma ich dokładnie $ gcd(a, n) $ (w przedziale $ [0, n) $), a rozwiązania są równooddalone od siebie. Zatem wystarczy znaleźć jedno rozwiązanie i na podstawie jego łatwo otrzymamy pozostałe. Na przykład: $ 4x \equiv 4 (mod 12) $ Łatwo zgadujemy, że jednym z rozwiązań jest $ x = 1 $. Wiedząc, że mamy 4 rozwiązania i są one równooddalone wnioskujemy, że kolejne rozwiązania różnią się od siebie o $ 12 / 4 = 3 $. Zatem rozwiązania to: $ x = 1; x = 4; x = 7; x = 10 $. Albo inaczej - rozwiązania tego równania są postaci: $ x = 3k + 1 $ dla każdego k.

Napiszemy teraz prostą procedurę, która wypisuje wszystkie rozwiązania liniowego równania modularnego.

void ModularLinearEquationSolver(int a, int b, int n)
{
  // Niech d, x', y' obliczone z rozszerzonego
  // algorytmu euklidesa(a, n)

  if (b % d == 0)
  {
    int x0 = x' * (b / d) mod n;
    for (int i = 0; i < d; i++)
      printf("%d\n", (x0 + i * (n / d)) mod n);
  }
  else printf("rozwiazan brak\n");
}

3.5
Twoja ocena: Brak Ocena: 3.5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com