Udowodnić bijekcję i wzór funkcji odwrotnej

[Akiva]

W jaki sposób udowodnić, że funkcja \(\displaystyle{ f: \ZZ _{43} \rightarrow \ZZ _{43}, f(x)=18x ^{19}+14\mod 43}\) jest bijekcją i wyznaczyć wzór funkcji odwrotnej?

[Premislav]

Niech \(\displaystyle{ x,y \in\left\{ 1,2, \ldots 42\right\}}\). Wówczas
\(\displaystyle{ 18x^{19}+14\equiv 18y^{19}+14\pmod{43} \Leftrightarrow 43|18(x^{19}-y^{19}) \Leftrightarrow \\ \Leftrightarrow 43|(x^{19}-y^{19})}\)
Przypuśćmy, że \(\displaystyle{ 43|(x^{19}-y^{19})}\).
Zauważmy, że z MTF \(\displaystyle{ 43|(x^{42}-y^{42})}\), zaś
\(\displaystyle{ x^{42}-y^{42}=(x^{21}-y^{21})(x^{21}+y^{21})}\)
czyli
\(\displaystyle{ 43|(x^{21}-y^{21}) \vee 43|(x^{21}+y^{21})}\)
1) Najpierw rozpatrzymy ten pierwszy przypadek.
\(\displaystyle{ 43|(x^{21}-y^{21})}\)
Zapiszmy
\(\displaystyle{ x^{21}-y^{21}=(x^{19}-y^{19})(x^2+y^2)-(xy)^2(x^{17}-y^{17})}\)
Oczywiście \(\displaystyle{ 43\nmid (xy)^2}\) przy założeniach odnośnie \(\displaystyle{ x,y}\), więc
\(\displaystyle{ 43| x^{17}-y^{17}}\). Możemy jednak dalej zapisać:
\(\displaystyle{ x^{19}-y^{19}=(x^{17}-y^{17})(x^2+y^2)-(xy)^2\left( x^{15}-y^{15}\right)}\)
Ogólnie, korzystając z własności
\(\displaystyle{ x^{k+2}-y^{k+2}=(x^k-y^k)(x^2+y^2)-(xy)^2(x^{k-2}-y^{k-2})}\)
i korzystając z tego, że \(\displaystyle{ 43\nmid x, \ 43\nmid y}\) (bo \(\displaystyle{ x,y\in\left\{ 1,2, \ldots 42\right\}}\)) dowodzimy przez indukcję wsteczną, że \(\displaystyle{ 43|(x-y)}\), jednak skoro \(\displaystyle{ x,y\in\left\{ 1,2, \ldots 42\right\}}\), to stąd \(\displaystyle{ x=y}\).
2) Teraz pora na przypadek \(\displaystyle{ 43| (x^{21}+y^{21})}\).
Mamy
\(\displaystyle{ x^{21}+y^{21}=(x^{19}-y^{19})(x^2-y^2)+(xy)^2(x^{17}+y^{17})}\)
Stąd, skoro \(\displaystyle{ 43}\) dzieli liczby \(\displaystyle{ x^{21}+y^{21}}\) oraz \(\displaystyle{ x^{19}-y^{19}}\), to (z uwagi na \(\displaystyle{ 43\nmid x, \ 43\nmid y}\)) widzimy, że \(\displaystyle{ 43}\) dzieli \(\displaystyle{ x^{17}+y^{17}}\). Dalej dostajemy
\(\displaystyle{ x^{19}-y^{19}=(x^{17}+y^{17})(x^2-y^2)+(xy)^2(x^{15}-y^{15})}\),
stąd otrzymujemy podzielność \(\displaystyle{ x^{15}-y^{15}}\) przez \(\displaystyle{ 43}\)
i ponownie na drodze indukcji wstecznej dowodzimy, że \(\displaystyle{ 43|(x^3-y^3)}\) oraz \(\displaystyle{ 43|(x+y)}\), czyli w tym przypadku \(\displaystyle{ x=y}\), gdyż
\(\displaystyle{ x^3-y^3=(x-y)(x^2+xy+y^2)=(x-y)\left( (x+y)^2-xy\right)}\)
i dla \(\displaystyle{ x,y \in \left\{ 1,2, \ldots 42\right\}}\) mamy \(\displaystyle{ 43\nmid xy}\).

Korzystamy przy tym z takich oto własności:
\(\displaystyle{ x^{k+2}+y^{k+2}=(x^k-y^k)(x^2-y^2)+(xy)^2(x^{k-2}+y^{k-2})\\x^{k+2}-y^{k+2}=(x^k+y^k)(x^2-y^2)+(xy)^2(x^{k-2}-y^{k-2})}\)

A wzoru funkcji odwrotnej nie umiem znaleźć. Albo tyle zapomniałem już z algebry, albo nigdy tego nie umiałem.

[Sylwek]

Wystarczy pokazać, że \(\displaystyle{ x^{19}}\) jest bijekcją. Jeśli \(\displaystyle{ x=0}\), to \(\displaystyle{ x^{19}=0}\), a z pozostałych przypadkach proponuję poniższe podejście (wszystko jest w \(\displaystyle{ \ZZ _{43}}\)).

Jeśli \(\displaystyle{ x, y \neq 0}\), to znajdźmy taką liczbę \(\displaystyle{ k}\), że \(\displaystyle{ 19k \equiv 1 \pmod{42}}\). Aha, wiemy, że takie \(\displaystyle{ k}\) istnieje, bo \(\displaystyle{ NWD(19,42)=1}\). No ale jak chcemy być precyzyjni - \(\displaystyle{ k=31}\) pasuje (przyda się w drugiej części).

Wówczas wystarczy pokazać, że \(\displaystyle{ x^{19} = y^{19}}\) daje \(\displaystyle{ x=y}\). Podnosząc pierwszą równość do potęgi \(\displaystyle{ k}\) otrzymujemy \(\displaystyle{ (x^{19})^k = (y^{19})^k}\), czyli \(\displaystyle{ x^{42n+1}=y^{42n+1}}\). Stąd i z małego twierdzenia Fermata dostajemy \(\displaystyle{ x=y}\). Zatem funkcja jest różnowartościowa, dziedzina to \(\displaystyle{ \ZZ _{43} \backslash \lbrace 0 \rbrace}\), przeciwdziedzina też, zatem przyjmuje wszystkie możliwe wartości w naszym zbiorze.

Łącząc to z przypadkiem \(\displaystyle{ x=0}\), dostajemy bijekcję.

Powyższa idea wskazuje też łatwo na funkcję odwrotną. Jeśli \(\displaystyle{ x^{19}=0}\), to \(\displaystyle{ x=0}\). A jeśli \(\displaystyle{ x^{19}=z \neq 0}\), to po podniesieniu do \(\displaystyle{ 31.}\) potęgi (jednak się przydało) dostajemy \(\displaystyle{ x=z^{31}}\).

I aplikujemy tę ideę do naszego zadania.