Arytmetyka modularna

03.12.2009 - Krzysztof Piecuch
TrudnośćTrudność

Multiplikatywna odwrotność a modulo n

Mamy daną liczbę $ a $. Bardzo przydatną umiejętnością będzie dla nas znajdowanie takiej liczby $ x $, że $ a $ przemnożone przez $ x $ da nam $ 1 $. Oczywiście modulo $ n $. Analogicznie do liczb rzeczywistych, taką liczbę będziemy nazywali odwrotnością liczby $ a $ i zapisywać będziemy jako $ (a^{-1} \pmod n) $. Formalnie:

$ (a^{-1} \pmod n) = x \stackrel{def.}{\Longleftrightarrow} ax \equiv 1 \pmod n $

Jeśli $ a $ jest względnie pierwsze z $ n $ to $ a $ ma dokładnie jedną odwrotność modulo $ n $. W przeciwnym przypadku nie ma odwrotności.

Odwrotnością liczby $ 7 $ modulo $ 11 $ jest liczba $ 8 $ bo $ 7 * 8 = 56 $, a $ 56 \equiv 1 (mod 11) $. Odwrotnością liczby $ 4 $ modulo $ 7 $ jest liczba $ 2 $ bo $ 4 * 2 = 8 $, a $ 8 \equiv 1 (mod 7) $. Natomiast odwrotność liczby $ 6 $ modulo $ 27 $ nie istnieje, bo $ gcd(6, 27) = 3 $.

Rodzi się naturalne pytanie jak szybko znajdować taką odwrotność. Z pomocą przychodzi nam rozszerzony algorytm Euklidesa (o rozszerzonym algorytmie Euklidesa możesz poczytać w artykule znajdującym się tutaj):

$ gcd(a, n) = 1 = ax' + ny' $

$ ax' - 1 = -ny' $

$ n | (ax' - 1) $

$ ax' \equiv 1 \pmod n $

Zatem, aby obliczyć odwrotność, wystarczy uruchomić rozszerzony algorytm Euklidesa dla argumentów $ a $ oraz $ n $. Jest to bardzo dobra wiadomość, bo i tak musielibyśmy odpalić ten algorytm, aby sprawdzić czy odwrotność w ogóle istnieje.

Rozwiązała nam się zagadka z tym kiedy możemy obustronnie podzielić równanie przez jakąś liczbę $ k $. Powiedziałem w poprzednim rozdziale, że możemy to zrobić gdy $ gcd(k, n) = 1 $. Nie wiemy jeszcze tylko dlaczego właśnie wtedy. Chwileczkę! Przecież wiemy! Skoro $ gcd(k, n) = 1 $ to $ k $ ma multiplikatywną odwrotność modulo $ n $. Liczba ta jest liczbą całkowitą - więc możemy przez nią obustronnie pomnożyć równanie. Formalnie zapisując:

$  ak \equiv bk \pmod n $
$  ak \times (k^{-1} \pmod n) \equiv bk \times(k^{-1} \pmod n)\pmod n $
$  a \equiv b \pmod n $

Jeśli namieszaliśmy trochę za bardzo to wszystko powinien wyjaśnić przykład. Mamy równanie $ 15 \equiv 55 \pmod 8 $. Chcemy podzielić obustronnie przez $ 5 $. Wiemy, że odwrotnością liczby 5 modulo 8 jest 5 bo $ 25 \equiv 1 \pmod 8 $. Zatem mnożymy przez odwrotność piątki obie strony równania i otrzymujemy $ 3 \times (5 \times 5) \equiv 11 \times (5 \times 5) \pmod 8 $. Ponieważ $ 5 \times 5 \equiv 1 \pmod 8 $ otrzymujemy $ 3 \times 1 \equiv 11 \times 1 \pmod 8 $ czyli $ 3 \equiv 11 \pmod 8 $. Podzieliliśmy obie strony przez 5. Ponadto zrobiliśmy to bez żadnego błędu - co można łatwo sprawdzić.

Poznaliśmy zatem jedno zastosowanie multiplikatywnej odwrotności modulo. W kolejnych działach poznamy dwa kolejne. A tymczasem czy drogi Czytelnik potrafi podać przykład jakiejś liczby która nie ma odwrotności modulo 143? I czy potrafisz uzasadnić czemu jeśli istnieje jakaś odwrotność danej liczby, to jest ona jedyna?

Własność podzielności liczb

Pewnie większość z was wie, że liczba N jest podzielna przez 3 wtedy i tylko wtedy gdy suma cyfr tej liczby jest podzielna przez 3. Na przykład 17265 jest podzielna przez 3 bo $ 1 + 7 + 2 + 6 + 5 = 21 $ a 21 jest podzielne przez 3. Ale czy wiecie dlaczego tak jest? Właśnie teraz ten dowód przeprowadzimy. Weźmy dowolną liczbę N i zapiszmy ją w systemie dziesiętnym: $ N = c_1 \times 10^{n-1} + c_2 \times 10^{n-2} + \ldots + c_n \times 10^0 $. Określmy wielomian wzorem $ W(x) = c_1 \times x^{n-1} + c_2 \times x^{n-2} + \ldots + c_n \times x^0 $. Naturalnie $ N = W(10) $. Ponadto skorzystamy z prostego faktu, że $ 10 \equiv 1 \pmod 3 $. Z własności wielomianów o którym mówiliśmy w drugim rozdziale wiemy już że:

$  N = W(10)  $
$  W(10) \equiv W(1) \pmod 3  $
$  W(1) = c_1 + c_2 + \ldots c_n  $

Zatem $ N $ jest podzielna przez $ 3 $ wtedy i tylko wtedy gdy suma jej cyfr jest podzielna przez $ 3 $ !

Spróbujmy teraz znaleźć regułę na podzielność przez 13. Tym razem liczbę N podzielimy na blocki po 3 liczby: $ N = \ldots + (c_{n-5}c_{n-4}c_{n-3})_10 \times 1000^1 + (c_{n-2}c_{n-1}c_n)_10 \times 1000^0 $ oraz $ w(x) = = \ldots + (c_{n-5}c_{n-4}c_{n-3})_10 \times x^1 + (c_{n-2}c_{n-1}c_n)_10 \times x^0 $. Tym razem skorzystamy z tego, że $ 1000 \equiv -1 \pmod 13 $ (bo $ 1001 = 7 \times 11 \times 13 $). Zatem liczba N dzieli się przez 7 wtedy i tylko wtedy gdy suma naprzemienna: $ \ldots + (c_{n-8}c_{n-7}c_{n-6})_10 - (c_{n-5}c_{n-4}c_{n-3})_10 + (c_{n-2}c_{n-1}c_n) $ dzieli się przez 7. Ponieważ jak wspomnieliśmy $ 1001 = 7 \times 11 \times 13 $ reguła ta odnosi się również do podzielności przez 11 oraz 7.

Umiemy już odpowiedzieć na pierwsze nasze pytanie. 13 dzieli 16971461287794 bo $  16 - 971 + 461 - 287 + 794 = 13 $. Jako ćwiczenie sprawdź czy liczba $ 27583167838910 $ jest podzielna przez $ 11 $.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com