Arytmetyka modularna

03.12.2009 - Krzysztof Piecuch

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$ .