Działania na resztach

[Bran]

Weźmy dowolną dodatnią liczbę naturalną \(\displaystyle{ n}\).

Przez \(\displaystyle{ A}\) oznaczmy zbiór wszystkich liczb mniejszych od \(\displaystyle{ n}\) względnie pierwszych z \(\displaystyle{ n}\) (pytanie: czy to jest zbiór reszt modulo?).

Jeżeli dobrze myślę, to będziemy mieli tutaj wszystkie liczby z \(\displaystyle{ \left\{ 1, 2, \ldots, n-1\right\}}\) z wyjątkiem nietrywialnych dzielników liczby \(\displaystyle{ n}\)

i teraz muszę udowodnić, że:
1. Mnożenie modulo \(\displaystyle{ n}\) w \(\displaystyle{ A}\), nie wyprowadzi mnie ze zbioru \(\displaystyle{ A.}\)
2. Dla każdego elementu z \(\displaystyle{ x \in A}\) znajdę taki element \(\displaystyle{ x' \in A}\), ze \(\displaystyle{ xx' = 1.}\)

Będę wdzięczny za naprowadzenie.

[Dasio11]

Przez \(\displaystyle{ A}\) oznaczmy zbiór wszystkich liczb mniejszych od \(\displaystyle{ n}\) względnie pierwszych z \(\displaystyle{ n}\) (pytanie: czy to jest zbiór reszt modulo?).

Jeżeli dobrze myślę, to będziemy mieli tutaj wszystkie liczby z \(\displaystyle{ \left\{ 1, 2, \ldots, n-1\right\}}\) z wyjątkiem nietrywialnych dzielników liczby \(\displaystyle{ n}\)

Niestety, dwa razy "nie".

Zbiór reszt modulo \(\displaystyle{ n}\) to \(\displaystyle{ \{ 0, 1, 2, \ldots, n-1 \}}\) (włączając zero). Z kolei zbiór \(\displaystyle{ A}\) nazywany jest grupą multiplikatywną modulo \(\displaystyle{ n}\) i powstaje z poprzedniego przez odjęcie nie tylko nietrywialnych dzielników \(\displaystyle{ n}\), ale w ogóle liczb mających nietrywialny wspólny dzielnik z \(\displaystyle{ n}\). Na przykład dla \(\displaystyle{ n = 12}\) ten zbiór to \(\displaystyle{ \{ 1, 5, 7, 11 \}}\).

1. Mnożenie modulo \(\displaystyle{ n}\) w \(\displaystyle{ A}\), nie wyprowadzi mnie ze zbioru \(\displaystyle{ A.}\)
2. Dla każdego elementu z \(\displaystyle{ x \in A}\) znajdę taki element \(\displaystyle{ x' \in A}\), ze \(\displaystyle{ xx' = 1.}\)

Ad. 1 - jesteś pewien, że próbowałeś? To naprawdę nietrudne.

Ad. 2: dla ustalonego \(\displaystyle{ x \in A}\) korzystamy z poprzedniego punktu, by zdefiniować funkcję \(\displaystyle{ f : A \to A}\) tak że \(\displaystyle{ f(y) = x \cdot y \bmod{n}}\). Wykaż jej różnowartościowość i połącz to z faktem, że \(\displaystyle{ A}\) jest zbiorem skończonym.

[Bran]

1. Niestety nie mam pomysłu, wydaje mi się to bardzo ogólne dla dowolnego \(\displaystyle{ n}\).
2. Funkcja \(\displaystyle{ f}\) jest różnowartościowa, pokażemy to korzystając z kontrapozycji do definicji iniekcji.
Dla dowolnych elementów \(\displaystyle{ a,b \in A}\)

Dla ustalonego \(\displaystyle{ x \in A}\) zachodzi \(\displaystyle{ f(a) = a \cdot x \mod n}\) i \(\displaystyle{ f(b) = b \cdot x \mod n}\)

Więc: \(\displaystyle{ f(a) = f(b) \Rightarrow \left( a \cdot x \mod n\right) = \left( b \cdot x \mod n\right) }\)

To oznacza, że \(\displaystyle{ ax}\) i \(\displaystyle{ bx}\) dają taką samą resztę z dzielenia przez \(\displaystyle{ n}\)
Załóżmy bez utraty ogólności, że \(\displaystyle{ a \ge b}\) wtedy:
\(\displaystyle{ \left( a \cdot x \mod n\right) = \left( b \cdot x \mod n\right) \Leftrightarrow \left( (b+k) \cdot x \mod n\right) = \left( b \cdot x \mod n\right) }\)
gdzie \(\displaystyle{ k \in \NN_+}\)

jeżeli \(\displaystyle{ a \neq b}\), to \(\displaystyle{ k = 0}\) lub \(\displaystyle{ x = 0}\) a tak nie jest, zatem \(\displaystyle{ a = b}\)

[Dasio11]

1. Rozważmy dowolne \(\displaystyle{ a, b \in A}\). Są to więc liczby ze zbioru \(\displaystyle{ \{ 0, 1, \ldots, n-1 \}}\) niemające nietrywialnych wspólnych dzielników z \(\displaystyle{ n}\). Niech teraz \(\displaystyle{ c := a \cdot b \bmod{n}}\) - oczywiście ta liczba znów jest elementem zbioru \(\displaystyle{ \{ 0, 1, \ldots, n-1 \}}\), pozostaje więc wykazać jej względną pierwszość z \(\displaystyle{ n}\).

Przypuśćmy nie wprost, że ma ona z \(\displaystyle{ n}\) wspólny dzielnik \(\displaystyle{ p}\) będący liczbą pierwszą. Wykonując dzielenie z resztą \(\displaystyle{ a \cdot b : n}\), czyli zapisując

\(\displaystyle{ a \cdot b = k \cdot n + r}\),

gdzie \(\displaystyle{ k}\) jest liczbą całkowitą i \(\displaystyle{ 0 \le r < n}\), widzimy że \(\displaystyle{ r}\) to właśnie nasze \(\displaystyle{ c}\). Skoro zaś \(\displaystyle{ p}\) dzieli prawą stronę równości (bo dzieli \(\displaystyle{ n}\) i \(\displaystyle{ r}\)), to musi dzielić i lewą, tj. \(\displaystyle{ p \mid a \cdot b}\). Stąd \(\displaystyle{ p \mid a}\) bądź \(\displaystyle{ p \mid b}\), czyli \(\displaystyle{ p}\) jest nietrywialnym wspólnym dzielnikiem \(\displaystyle{ n}\) i którejś z liczb wziętych na początku - a takowy miał nie istnieć, QED.


2.

Załóżmy bez utraty ogólności, że \(\displaystyle{ a \ge b}\) wtedy:
\(\displaystyle{ \left( a \cdot x \mod n\right) = \left( b \cdot x \mod n\right) \Leftrightarrow \left( (b+k) \cdot x \mod n\right) = \left( b \cdot x \mod n\right) }\)
gdzie \(\displaystyle{ k \in \NN_+}\)

jeżeli \(\displaystyle{ a \neq b}\), to \(\displaystyle{ k = 0}\) lub \(\displaystyle{ x = 0}\) a tak nie jest, zatem \(\displaystyle{ a = b}\)

Jak z faktu że \(\displaystyle{ a \neq b}\) miałoby wynikać, że \(\displaystyle{ k = 0}\) lub \(\displaystyle{ x = 0}\) ?

[Bran]

Niech teraz \(\displaystyle{ c := a \cdot b \bmod{n}}\) - oczywiście ta liczba znów jest elementem zbioru \(\displaystyle{ \{ 0, 1, \ldots, n-1 \}}\), pozostaje więc wykazać jej względną pierwszość z \(\displaystyle{ n}\).

No właśnie nie tak oczywiście

2.

Załóżmy bez utraty ogólności, że \(\displaystyle{ a \ge b}\) wtedy:
\(\displaystyle{ \left( a \cdot x \mod n\right) = \left( b \cdot x \mod n\right) \Leftrightarrow \left( (b+k) \cdot x \mod n\right) = \left( b \cdot x \mod n\right) }\)
gdzie \(\displaystyle{ k \in \NN_+}\)

jeżeli \(\displaystyle{ a \neq b}\), to \(\displaystyle{ k = 0}\) lub \(\displaystyle{ x = 0}\) a tak nie jest, zatem \(\displaystyle{ a = b}\)

Jak z faktu że \(\displaystyle{ a \neq b}\) miałoby wynikać, że \(\displaystyle{ k = 0}\) lub \(\displaystyle{ x = 0}\) ?

Jeżeli \(\displaystyle{ k = 0}\), to \(\displaystyle{ a = b + 0 = b}\) a tak miało nie być.
Natomiast z tego, że \(\displaystyle{ x = 0}\) faktycznie nie wynika, że \(\displaystyle{ a = b}\), ale równość i tak jest prawdziwa, więc następnik pozostaje prawdziwy, cała implikacja też.

[Dasio11]

No właśnie nie tak oczywiście

Co jest nieoczywistego w tym, że reszta z dzielenia jakiejkolwiek liczby całkowitej przez \(\displaystyle{ n}\) należy do zbioru \(\displaystyle{ \{ 0, 1, 2, \ldots, n-1 \}}\) ?

Jeżeli \(\displaystyle{ k = 0}\), to \(\displaystyle{ a = b + 0 = b}\) a tak miało nie być.

To jest dowód implikacji \(\displaystyle{ k = 0 \implies a = b}\) (lub ewentualnie przez kontrapozycję: \(\displaystyle{ a \neq b \implies k \neq 0}\)), a to nie taką implikację wcześniej napisałeś.

Natomiast z tego, że \(\displaystyle{ x = 0}\) faktycznie nie wynika, że \(\displaystyle{ a = b}\), ale równość i tak jest prawdziwa, więc następnik pozostaje prawdziwy, cała implikacja też.

Która równość i jaka implikacja są prawdziwe?

[Bran]

1. Okej, już rozumiem cały dowód.

2. No to od początku.

Zacznijmy od dowodu różnowartościowości funkcji \(\displaystyle{ f}\).

Dla ustalonego \(\displaystyle{ x \in A}\) mamy \(\displaystyle{ f(a) = x \cdot a \mbox{ mod } n,}\) \(\displaystyle{ f(b) = x \cdot b \mbox{ mod } n}\) gdzie \(\displaystyle{ a,b \in A}\) i \(\displaystyle{ a \neq b.}\)

Wystarczy udowodnić, że \(\displaystyle{ f(a) \neq f(b)}\) zatem \(\displaystyle{ x \cdot a \mbox{ mod } n \neq x \cdot b \mbox{ mod } n.}\)

Załóżmy nie wprost, że \(\displaystyle{ x \cdot a \mbox{ mod } n = x \cdot b \mbox{ mod } n.}\)

Wówczas \(\displaystyle{ \frac{b-r}{n} = \frac{a-r}{n}}\), gdzie \(\displaystyle{ r \in \left\{ 0,1, \ldots, n-1\right\} }\)

po przemnożeniu obu stron równości przez \(\displaystyle{ n}\) i dodaniu do nich \(\displaystyle{ r}\) dostajemy:
\(\displaystyle{ b = a,}\) co jest sprzeczne z założeniem i kończy dowód.

Gdy przemnożymy dowolnie ustalony element \(\displaystyle{ x \in A}\) przez każdy z elementów ze zbioru \(\displaystyle{ A}\), to dostaniemy tyle różnych wyników ile elementów ma zbiór \(\displaystyle{ A}\) czyli znajdziemy dokładnie jeden taki element z \(\displaystyle{ x' z A}\), że \(\displaystyle{ xx' = 1}\)

[Dasio11]

Załóżmy nie wprost, że \(\displaystyle{ x \cdot a \mbox{ mod } n = x \cdot b \mbox{ mod } n.}\)

Wówczas \(\displaystyle{ \frac{b-r}{n} = \frac{a-r}{n}}\), gdzie \(\displaystyle{ r \in \left\{ 0,1, \ldots, n-1\right\} }\)

Dlaczego?

[Bran]

Bo się pomyliłem, mógłbym dostać jakąś podpowiedź?

[Dasio11]

Z założenia \(\displaystyle{ x \cdot a \bmod{n} = x \cdot b \bmod{n}}\) wynika, że \(\displaystyle{ n}\) jest dzielnikiem liczby \(\displaystyle{ x \cdot a - x \cdot b = x \cdot (a - b)}\). Najpierw skorzystaj z założenia o \(\displaystyle{ x}\), a potem wypisz wszystkie możliwe wartości, jakie może przyjąć różnica \(\displaystyle{ a-b}\).

Gdy przemnożymy dowolnie ustalony element \(\displaystyle{ x \in A}\) przez każdy z elementów ze zbioru \(\displaystyle{ A}\), to dostaniemy tyle różnych wyników ile elementów ma zbiór \(\displaystyle{ A}\) czyli znajdziemy dokładnie jeden taki element z \(\displaystyle{ x' z A}\), że \(\displaystyle{ xx' = 1}\)

Dobrze.

[Bran]

Zauważyłem, że istnieją takie elementy \(\displaystyle{ a,b}\), że \(\displaystyle{ n - a = b}\) gdzie \(\displaystyle{ a,b \in A}\)

Natomiast jeżeli chodzi o \(\displaystyle{ a-b}\) to nie widzę, żadnej konkretnej zależności godnej uwagi. No może poza faktem, że na pewno są w zbiorze \(\displaystyle{ \left\{ 1, 2, \ldots, n-1\right\} }\) o ile \(\displaystyle{ a > b}\), ale wydaje mi się, że tak przyjąłeś.

[Dasio11]

Jeśli nie widzisz jak to zrobić ogólniej, może łatwiej będzie na przykładzie: \(\displaystyle{ n = 24}\), \(\displaystyle{ x = 7}\). Wiemy, że \(\displaystyle{ a, b \in \{ 0, 1, \ldots, 23 \}}\) i \(\displaystyle{ 24 \mid 7 (a-b)}\), a chcemy wiedzieć, że \(\displaystyle{ a = b}\).

[Bran]

Ahh, skoro \(\displaystyle{ x}\) jest względnie pierwsze z \(\displaystyle{ n}\), to \(\displaystyle{ (a-b)}\) musi być równe \(\displaystyle{ 0}\) żeby n dzieliło \(\displaystyle{ x(a-b)}\). A żeby tak było to \(\displaystyle{ a = b}\).

[Dasio11]

W istocie.

[Bran]

To mam jeszcze jedno pytanko, pozwolę sobie tutaj, żeby nie wprowadzać tego samego w innym temacie.

dla dowolnego \(\displaystyle{ a \in A}\) zbiór \(\displaystyle{ \left\{ a,a^2, \ldots, a^k\right\} }\) z mnożeniem modulo \(\displaystyle{ n}\) tworzy podgrupę \(\displaystyle{ A}\), gdzie \(\displaystyle{ a^k \equiv 1 \left( \mbox{ mod } n\right) }\)

Dowód tego faktu jest analogiczny do tego wyżej?