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ść.
Działania na resztach
-
- 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
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.
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.
- Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Działania na resztach
Co będzie "ciągle różne od \(\displaystyle{ a}\)"?
Co to znaczy "generujemy ten zbiór aż nie dojdzie do konkretnej liczby"? Co jest różne?
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: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.
W jaki sposób?
-
- 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
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}\).
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}\).
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:
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}\)Dasio11 pisze: ↑4 sie 2020, o 21:41Kierunek 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: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.
\(\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.}\)
- Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Działania na resztach
Zapis jest trochę niezgrabny, ale rozumowanie zasadniczo poprawne.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}\)
Właściwie istnienie jedynki w zbiorze \(\displaystyle{ B}\) wynika już bezpośrednio z polecenia:
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}\).
Jest poprawnie.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.}\)
Co do elementu odwrotnego: skoro \(\displaystyle{ a^k = 1}\), to przez jaki element trzeba pomnożyć \(\displaystyle{ a}\), żeby uzyskać jedynkę?
-
- 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
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: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}\).
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}\)?
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?