Arytmetyka modularna

03.12.2009 - Krzysztof Piecuch
TrudnośćTrudność

Zajmijmy się teraz sytuacją w której mamy więcej równań.

Rozwiązywanie układu modularnych równań liniowych

Zadanie z cukierkami możemy zapisać za pomocą trzech liniowych równań modularnych:

$  x \equiv 1 \pmod 3 $
$  x \equiv 2 \pmod 4 $
$  x \equiv 0 \pmod 5 $

Układ taki rozwiązujemy rozwiązując pierw pierwsze równanie, a następnie wynik wstawiając do kolejnego. Równanie $ x \equiv 1 (mod 3) $ jest trywialne. Jego rozwiązanie to $ x = 3t + 1 $. Wynik ten wstawiamy do drugiego równania:

$  3t + 1 \equiv 2 \pmod 4 $
$  3t \equiv 1 \pmod 4 $
$  t \equiv 3 \pmod 4 $

Stąd $ t = 4s + 3 $ zatem $ x = 3t + 1 = 3(4s + 3) + 1 = 12s + 10 $. Wstawiamy ten wynik do ostatniego równania:

$  12s + 10 \equiv 0 \pmod 5 $
$  2s \equiv 0 \pmod 5 $
$  s \equiv 0 \pmod 5 $

Ostatecznie $ s = 5u $ czyli $ x = 12s + 10 = 60u + 10 $. Ponieważ w treści mowa jest o dużej paczce cukierków, możemy wnioskować, że jest ich raczej $ 70 $ a nie $ 10 $. Odpowiadamy zatem: W paczce Jasia było $ 70 $ cukierków.

Metoda ta jest dobra do rozwiązywania ręcznego małych układów równań z małymi liczbami całkowitymi. Poznamy teraz twierdzenie, które ułatwi nam rozwiązywanie większych układów równań.

Chińskie twierdzenie o resztach

Powiedzmy, że mamy dany układ k liniowych równań modularnych:

$  x \equiv a_1 \pmod n_1 $
$  x \equiv a_2 \pmod n_2 $
$ \vdots  $
$  x \equiv a_k \pmod n_k $

Przy czym wszystkie $ n_i $ są parami względnie pierwsze. Wtedy: $  x \equiv a_1 b_1 + a_2 b_2 + \ldots + a_k b_k \pmod n  $ gdzie $ n = n_1 n_2 \ldots n_k $ oraz

$ b_i = \dfrac{n}{n_i} \left(\left( \dfrac{n}{n_i} \right)^{-1} \pmod n_i\right) $.

Zobaczmy jak to działa. Weźmy dobrze nam znany układ liniowych równań modularnych:

$  x \equiv 1 \pmod 3 $
$  x \equiv 2 \pmod 4 $
$  x \equiv 0 \pmod 5 $

Obliczamy kolejno poszczególne parametry. Zaczniemy od $ n = 3 * 4 * 5 = 60 $. Teraz kolejne $ b_i $:

$ b_1 = 20 \times (20^{-1} \pmod 3) = 20 \times 2 = 40 $, $ b_2 = 15 \times (15^{-1} \pmod 4) = 15 \times 3 = 45 $

oraz $ b_3 = 12 \times (12^{-1} \pmod 5) = 12 \times 3 = 36 $.

Stąd $ a_1 b_1 + a_2 b_2 + a_3 b_3 = 1 \times 40 + 2 \times 45 + 0 \times 36 = 20 + 90 + 0 = 130 $. Stąd $ x \equiv 130 \pmod 60 $ czyli $ x \equiv 10 \pmod 60 $. Uzyskaliśmy zatem ten sam wynik, gdy liczyliśmy ten układ "na piechotę".

Więcej o chińskim twierdzeniu o resztach można przeczytać tutaj w artykule Agaty Murawskiej.

Funkcja Eulera

Funkcją Eulera $ \phi(n) $ definiujemy na liczbach naturalnych w następujący sposób. $ \phi(n) $ jest równa liczbie liczb naturalnych mniejszych od $ n $, które są względnie pierwsze z $ n $. Rozważmy przykład: $ \phi(6) $. Liczby mniejsze od 6 to 1, 2, 3, 4 oraz 5. Liczby 2, 3 oraz 4 nie są liczbami względnie pierwszymi z 6; natomiast 1 oraz 5 są. Zatem mamy dwie liczby naturalne mniejsze od 6, które są z 6 względnie pierwsze. Zatem $ \phi(6) = 2 $. Natomiast $ \phi(11) = 10 $ ponieważ 11 jest liczbą pierwszą czyli jest względnie pierwsza z wszystkimi liczbami: $ 1, 2, \ldots 10 $.

Trochę trudno wprost z definicji liczyć wartość funkcji $ \phi(n) $. Dużo czasu zajęłoby nam policzenie na przykład $ \phi(200) $. Z pomocą przychodzą nam dwie pomocne własności:

$  gcd(n, m) = 1 \Rightarrow \phi\left(n \times m\right) = \phi\left(n\right) \times \phi\left(m\right)  $
jeśli p jest pierwsza $ \Rightarrow \phi(p^k) = p^{k-1} \times (p - 1) $

Używając tych własności łatwo obliczamy $ \phi(200) $: $ \phi(200) = \phi(2^3 5^2) = \phi(2^3)\phi(5^2) = 2^2(2-1)5(5-1) = 4 \times 4 \times 5 = 80 $.

Poznamy teraz ważne dwa twierdzenia arytmetyki modularnej. Twierdzenie Eulera brzmi: jeśli $ gcd(a, n) = 1 $ to $ a^{\phi(n)} \equiv 1 \pmod n $. Na przykład skoro $ gcd(200, 3) = 1 $ to $ 3^{80} \equiv 1 \pmod 200 $. Małe twierdzenie Fermata brzmi: jeśli p jest liczbą pierwszą i a nie jest wielokrotnością p to $ a^{p-1} \equiv 1 \pmod p $.

Rozwiążemy teraz nasze ostatnie już zadanie. Policzymy trzy ostatnie cyfry liczby $ 3^{14404} $. Policzmy $ \phi(1000) = \phi(2^3 \times 5^3) = 400 $. Skorzystamy teraz z faktu, że $ 14404 = 400 \times 36 + 4 $ oraz $ 3^{400} \equiv 1 (mod 1000) $.

$  3^{14404} \equiv 3^{400 \times 36 + 4} \pmod 1000  $
$  3^{400 \times 36 + 4} \equiv (3^{400})^{36} \times 3^4 \pmod 1000  $
$  (3^{400})^{36} \times 3^4 \equiv 3^4 \pmod 1000 $

Skoro $ 3^4 = 81 $ to trzy ostatnie cyfry liczby $ 3^{14404} $ to 081.

Zadania

Na następnej stronie znajdują się zadania programistyczne. Wszystkich chętnych zapraszam do rozwiązywania!$

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com