Bijekcja, funkcje odwrotne

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Akiva
Użytkownik
Użytkownik
Posty: 57
Rejestracja: 26 sty 2018, o 19:47
Płeć: Kobieta
Lokalizacja: Dąbrowa Górnicza
Podziękował: 5 razy

Bijekcja, funkcje odwrotne

Post autor: Akiva »

Dana jest funkcja\(\displaystyle{ f: \ZZ_{67} \rightarrow \ZZ_{67}, f(x)=x ^{31}}\):
(a) należy udowodnić, że\(\displaystyle{ f}\) jest bijekcją;
(b) należy wyznaczyć wzór funkcji odwrotnej do \(\displaystyle{ f}\);
(c) należny wyznaczyć wszystkie \(\displaystyle{ x \in \ZZ _{67}}\), dla których \(\displaystyle{ f(x)=x}\).
Ostatnio zmieniony 25 cze 2018, o 19:22 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Bijekcja, funkcje odwrotne

Post autor: Premislav »

Sylwek tutaj podał już sposób na rozwiązanie: 433378.htm

Punkty a) i b) natychmiast idą przy analogicznym postępowaniu, znajdujesz mianowicie takie całkowite dodatnie \(\displaystyle{ s,t}\), że \(\displaystyle{ 31s=66t+1}\), co można zrobić za pomocą rozszerzonego algorytmu Euklidesa. A stąd się bierze to \(\displaystyle{ 66,}\) że z MTF mamy \(\displaystyle{ x^{66}equiv 1pmod{67}}\) gdy \(\displaystyle{ 67
mid x}\)
.


c) \(\displaystyle{ x^{31}=xLeftrightarrow x=0 vee x^{30}=1}\). W tym drugim przypadku zauważ, że rząd takiego elementu musi być wspólnym dzielnikiem \(\displaystyle{ 30}\) i \(\displaystyle{ 66}\) (czyli rzędu całej grupy multyplikatywnej \(\displaystyle{ Z_{67}}\)), czyli ten rząd jest równy \(\displaystyle{ 2, 3}\) bądź \(\displaystyle{ 6}\). Zlicz (może się przydać funkcja Eulera, aczkolwiek da się to też prosto z podłogami i zasadą włączeń-wyłączeń policzyć) ile jest elementów rzędu \(\displaystyle{ 2,}\) rzędu \(\displaystyle{ 3}\), rzędu \(\displaystyle{ 6}\) w \(\displaystyle{ Z_{67}}\) (rozumianej jako \(\displaystyle{ left{ 1,2, ldots 66
ight}}\)
z mnożeniem modulo \(\displaystyle{ 67}\)).
ODPOWIEDZ