Działania na resztach

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Działania na resztach

Post autor: Dasio11 »

Nie, dowód tego faktu jest taki jak zawsze przy wykazywaniu, że podzbiór grupy jest podgrupą - sprawdza się warunki:

1. Podzbiór jest zamknięty na działanie grupowe,
2. Jedynka należy do podzbioru,
3. Każdy element podzbioru ma w nim odwrotność.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Działania na resztach

Post autor: Bran »

Niech \(\displaystyle{ a \in A}\)

Rozpatrzmy zbiór \(\displaystyle{ B = \left\{ a, a^2, ..., a^k\right\},}\) gdzie \(\displaystyle{ a^k \equiv 1 \left( \mbox{ mod } n \right) }\)

Ponieważ \(\displaystyle{ a \in A}\), to \(\displaystyle{ a^2 \in A}\) itd i będzie ciągle różne od \(\displaystyle{ a}\) (chyba, że \(\displaystyle{ a = 1}\)) co wynika z iniektywności funkcji \(\displaystyle{ f}\).
Generujemy (nie wiem czy mogę użyć takiego słowa) ten zbiór aż nie dojdzie do konkretnej liczby, więc wszystkie są różne.

Zauważmy, że \(\displaystyle{ B \subset A}\) Ponieważ \(\displaystyle{ a^k \equiv 1 \left( \mbox{ mod } n \right) }\) to \(\displaystyle{ a^{k+1} \equiv a \left( \mbox{ mod } n \right) }\) itd. Czyli zbiór będzie się cyklicznie powtarzał co \(\displaystyle{ k}\) elementów.
Działanie więc będzie wewnętrzne.

Jedynka należy do podzbioru, to też wynika z iniektywności.

Z elementem odwrotnym mam problem.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Działania na resztach

Post autor: Dasio11 »

Bran pisze: 4 sie 2020, o 21:22Ponieważ \(\displaystyle{ a \in A}\), to \(\displaystyle{ a^2 \in A}\) itd i będzie ciągle różne od \(\displaystyle{ a}\)
Co będzie "ciągle różne od \(\displaystyle{ a}\)"?

Bran pisze: 4 sie 2020, o 21:22Generujemy (nie wiem czy mogę użyć takiego słowa) ten zbiór aż nie dojdzie do konkretnej liczby, więc wszystkie są różne.
Co to znaczy "generujemy ten zbiór aż nie dojdzie do konkretnej liczby"? Co jest różne?

Bran pisze: 4 sie 2020, o 21:22Zauważmy, że \(\displaystyle{ B \subset A}\) Ponieważ \(\displaystyle{ a^k \equiv 1 \left( \mbox{ mod } n \right) }\) to \(\displaystyle{ a^{k+1} \equiv a \left( \mbox{ mod } n \right) }\) itd. Czyli zbiór będzie się cyklicznie powtarzał co \(\displaystyle{ k}\) elementów.
Działanie więc będzie wewnętrzne.
Kierunek dobry, ale ostatecznie nie wykazałeś wewnętrzności działania. W tym celu - jak zawsze - ustal dowolne dwa elementy \(\displaystyle{ b_1, b_2 \in B}\) i wykaż, że ich iloczyn w grupie \(\displaystyle{ A}\) należy do \(\displaystyle{ B}\).

Bran pisze: 4 sie 2020, o 21:22Jedynka należy do podzbioru, to też wynika z iniektywności.
W jaki sposób?
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Działania na resztach

Post autor: Bran »

Dasio11 pisze: 4 sie 2020, o 21:41
Bran pisze: 4 sie 2020, o 21:22Ponieważ \(\displaystyle{ a \in A}\), to \(\displaystyle{ a^2 \in A}\) itd i będzie ciągle różne od \(\displaystyle{ a}\)
Co będzie "ciągle różne od \(\displaystyle{ a}\)"?
Mam na myśli, że jeżeli \(\displaystyle{ a \neq 1}\), to \(\displaystyle{ a^m}\) dla \(\displaystyle{ m \in \left\{ 2, 3, \ldots, k\right\} }\) jest różne od \(\displaystyle{ a}\).
Dasio11 pisze: 4 sie 2020, o 21:41
Bran pisze: 4 sie 2020, o 21:22Generujemy (nie wiem czy mogę użyć takiego słowa) ten zbiór aż nie dojdzie do konkretnej liczby, więc wszystkie są różne.
Co to znaczy "generujemy ten zbiór aż nie dojdzie do konkretnej liczby"? Co jest różne?
Chodzi mi o to, że z powyższej własności i iniektywności funkcji \(\displaystyle{ f}\) wynika, że kolejne potęgi elementu \(\displaystyle{ a}\) będą różnymi od siebie elementami zbioru \(\displaystyle{ A}\) i chcemy je tworzyć aż do uzyskania elementu, który przystaje to \(\displaystyle{ 1}\).
Dasio11 pisze: 4 sie 2020, o 21:41
Bran pisze: 4 sie 2020, o 21:22Jedynka należy do podzbioru, to też wynika z iniektywności.
W jaki sposób?
Jeżeli \(\displaystyle{ a = 1}\), to sprawa jest oczywista.

Jeżeli \(\displaystyle{ a \neq 1}\) to tak jak napisałem wyżej mamy taką sytuację:
Mnożymy \(\displaystyle{ a}\) przez \(\displaystyle{ a}\) i otrzymujemy element \(\displaystyle{ y_1 \in A}\) taki że \(\displaystyle{ y_1 \neq a.}\)
Jeżeli \(\displaystyle{ y_1 \neq 1}\), to wówczas mamy \(\displaystyle{ a^3 = f(y_1) = a \cdot y_1 \mbox{ mod } n}\) co daje nam element \(\displaystyle{ y_2}\) różny od \(\displaystyle{ y_1}\) ponieważ \(\displaystyle{ a \neq 1}\) i różne od \(\displaystyle{ a}\), ponieważ \(\displaystyle{ y_1 \neq 1.}\)

Rozumowanie powtarzamy maksymalnie \(\displaystyle{ \phi(n)}\) wówczas mamy \(\displaystyle{ \phi(n)}\) różnych od siebie elementów \(\displaystyle{ A,}\) zatem mamy wszystkie elementy zbioru \(\displaystyle{ A}\), w szczególności \(\displaystyle{ 1}\)

Dodano po 20 godzinach 1 minucie 20 sekundach:
Dasio11 pisze: 4 sie 2020, o 21:41
Bran pisze: 4 sie 2020, o 21:22Zauważmy, że \(\displaystyle{ B \subset A}\) Ponieważ \(\displaystyle{ a^k \equiv 1 \left( \mbox{ mod } n \right) }\) to \(\displaystyle{ a^{k+1} \equiv a \left( \mbox{ mod } n \right) }\) itd. Czyli zbiór będzie się cyklicznie powtarzał co \(\displaystyle{ k}\) elementów.
Działanie więc będzie wewnętrzne.
Kierunek dobry, ale ostatecznie nie wykazałeś wewnętrzności działania. W tym celu - jak zawsze - ustal dowolne dwa elementy \(\displaystyle{ b_1, b_2 \in B}\) i wykaż, że ich iloczyn w grupie \(\displaystyle{ A}\) należy do \(\displaystyle{ B}\).
Ustalmy dwa dowolne elementy \(\displaystyle{ a^m, a^q \in B}\) gdzie \(\displaystyle{ m,q \in \NN \wedge 1 \le m \le q \le k}\)

\(\displaystyle{ a^m \cdot a^q \mbox{ mod } n = a^{m+q} \mbox{ mod } n}\)
Zbiór powtarza się cyklicznie zatem \(\displaystyle{ a^{i} \mbox{ mod } n \in B}\) dla dowolnej liczby naturalnej \(\displaystyle{ i.}\)
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Działania na resztach

Post autor: Dasio11 »

Bran pisze: 5 sie 2020, o 19:48Jeżeli \(\displaystyle{ a = 1}\), to sprawa jest oczywista.

Jeżeli \(\displaystyle{ a \neq 1}\) to tak jak napisałem wyżej mamy taką sytuację:
Mnożymy \(\displaystyle{ a}\) przez \(\displaystyle{ a}\) i otrzymujemy element \(\displaystyle{ y_1 \in A}\) taki że \(\displaystyle{ y_1 \neq a.}\)
Jeżeli \(\displaystyle{ y_1 \neq 1}\), to wówczas mamy \(\displaystyle{ a^3 = f(y_1) = a \cdot y_1 \mbox{ mod } n}\) co daje nam element \(\displaystyle{ y_2}\) różny od \(\displaystyle{ y_1}\) ponieważ \(\displaystyle{ a \neq 1}\) i różne od \(\displaystyle{ a}\), ponieważ \(\displaystyle{ y_1 \neq 1.}\)

Rozumowanie powtarzamy maksymalnie \(\displaystyle{ \phi(n)}\) wówczas mamy \(\displaystyle{ \phi(n)}\) różnych od siebie elementów \(\displaystyle{ A,}\) zatem mamy wszystkie elementy zbioru \(\displaystyle{ A}\), w szczególności \(\displaystyle{ 1}\)
Zapis jest trochę niezgrabny, ale rozumowanie zasadniczo poprawne.

Właściwie istnienie jedynki w zbiorze \(\displaystyle{ B}\) wynika już bezpośrednio z polecenia:
Bran pisze: 4 sie 2020, o 18:12dla 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) }\)
bo szukaną jedynką jest \(\displaystyle{ a^k}\) będące jawnie wypisanym elementem omawianego zbioru. Ty zaś udowodniłeś istnienie owego \(\displaystyle{ k}\) spełniającego \(\displaystyle{ a^k = 1}\), co w poleceniu jest przyjęte z góry.

Ja ten dowód zapisałbym tak:
Ponieważ \(\displaystyle{ \left\{ a^i : 0 \le i \le \phi(n) \right\}}\) jest podzbiorem zbioru \(\displaystyle{ A}\) mającego \(\displaystyle{ \phi(n)}\) elementów, więc \(\displaystyle{ a^i}\) nie mogą być parami różne dla \(\displaystyle{ 0 \le i \le \phi(n)}\). Istnieją więc takie indeksy \(\displaystyle{ 0 \le i < j \le \phi(n)}\), dla których \(\displaystyle{ a^i = a^j}\). Na mocy prawa skreśleń - obowiązującego w każdej grupie, zatem i w \(\displaystyle{ A}\) - mamy \(\displaystyle{ a^0 = a^{j-i}}\), czyli \(\displaystyle{ a^k = 1}\) gdzie \(\displaystyle{ k = j-i \ge 1}\).

Bran pisze: 5 sie 2020, o 19:48Ustalmy dwa dowolne elementy \(\displaystyle{ a^m, a^q \in B}\) gdzie \(\displaystyle{ m,q \in \NN \wedge 1 \le m \le q \le k}\)

\(\displaystyle{ a^m \cdot a^q \mbox{ mod } n = a^{m+q} \mbox{ mod } n}\)
Zbiór powtarza się cyklicznie zatem \(\displaystyle{ a^{i} \mbox{ mod } n \in B}\) dla dowolnej liczby naturalnej \(\displaystyle{ i.}\)
Jest poprawnie.

Co do elementu odwrotnego: skoro \(\displaystyle{ a^k = 1}\), to przez jaki element trzeba pomnożyć \(\displaystyle{ a}\), żeby uzyskać jedynkę?
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Działania na resztach

Post autor: Bran »

Dasio11 pisze: 6 sie 2020, o 10:01 Ja ten dowód zapisałbym tak:
Ponieważ \(\displaystyle{ \left\{ a^i : 0 \le i \le \phi(n) \right\}}\) jest podzbiorem zbioru \(\displaystyle{ A}\) mającego \(\displaystyle{ \phi(n)}\) elementów, więc \(\displaystyle{ a^i}\) nie mogą być parami różne dla \(\displaystyle{ 0 \le i \le \phi(n)}\). Istnieją więc takie indeksy \(\displaystyle{ 0 \le i < j \le \phi(n)}\), dla których \(\displaystyle{ a^i = a^j}\). Na mocy prawa skreśleń - obowiązującego w każdej grupie, zatem i w \(\displaystyle{ A}\) - mamy \(\displaystyle{ a^0 = a^{j-i}}\), czyli \(\displaystyle{ a^k = 1}\) gdzie \(\displaystyle{ k = j-i \ge 1}\).
Dziękuje za matematyczny zapis, bardzo chcę go zrozumieć i umieć takie przedstawiać, więc jeśli masz jeszcze odrobinkę cierpliwości do mnie, to popytam:
1. Z indeksów od \(\displaystyle{ 0}\) do \(\displaystyle{ \phi(n)}\) wynika, że istnieją co najmniej dwa takie indeksy, które się pokryją, to jest \(\displaystyle{ a^i = a^j}\), bo w \(\displaystyle{ A}\) mamy \(\displaystyle{ \phi(n)}\) elementów, a indeksy od \(\displaystyle{ 0}\) do \(\displaystyle{ \phi(n)}\) mamy \(\displaystyle{ \phi(n)+1}\) więc przynajmniej jeden się powtarza (a jeżeli podzbiór nie jest całym zbiorem, to więcej). Dobrze rozumiem?

2. Jak z \(\displaystyle{ a^0 = a^{j-i}}\) wynika \(\displaystyle{ a^k = 1}\)?
Dasio11 pisze: 6 sie 2020, o 10:01 Co do elementu odwrotnego: skoro \(\displaystyle{ a^k = 1}\), to przez jaki element trzeba pomnożyć \(\displaystyle{ a}\), żeby uzyskać jedynkę?
Czyli rozważamy zbiór \(\displaystyle{ C = \left\{ 1,2, \ldots, k-1\right\}}\) \(\displaystyle{ a^{k-m} \cdot a^m = 1}\) gdzie \(\displaystyle{ m}\) jest dowolnym elementem ze zbioru \(\displaystyle{ C}\) widać więc, że zawsze znajdziemy taki element, który ma element odwrotny z wyjątkiem elementu \(\displaystyle{ a^k}\), który jest odwrotny do samego siebie, co kończy dowód?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Działania na resztach

Post autor: Dasio11 »

1. Tak.
2. Bo z definicji \(\displaystyle{ a^0 = 1}\) i \(\displaystyle{ k = j-i}\).

Odwrotność: ok.
ODPOWIEDZ