Matematické Fórum

Torpy · 02. 05. 2011 22:02

Zdravím,
mám následující problém:
"Mějme prvočíslo p splňující podmínku p=4m+1 pro nějaké liché m. Dokažte, že $2^m\mod p$ je druhá odmocnina z -1 v $\mathbb Z_p^*$ ."

Napadlo mě k tomu toto:
Když hledám druhou odmocninu z -1, hledám prvek řádu 4 v $\mathbb Z_p^*$
$\mathbb Z_p^*$ je cyklická a platí $\mathbb Z_p^*\simeq\mathbb Z_{p-1}$
Vezmu izomorfismus $\mathit{m}\rightarrow2^{\mathit{m}}$ , který vede ze $\mathbb Z_{p-1}$ do $\mathbb Z_p^*$ .
Původně zkoumám, zda $$2^{\mathit{m}}$^4\mod p =1$ . Ekvivalentně (díky izomorfismu) zkoumám, zda $4\cdot\mathit{m}\mod ${p-1}$=0$ .
Teď využiji toho, že $\mathit{p}=4\mathit{m}+1$ a dosadím: $4\cdot\mathit{m}\mod ${4\mathit{m}}$=0$ .
Což platí.
Dále platí pro i=1,2,3: $\mathit{i}\cdot\mathit{m}\mod ${4\mathit{m}}$\not=0$ .
Tedy m (a tedy i 2^m) je řádu 4.

Mohl by mi prosím někdo poradit, zda jsou moje úvahy správné, popř. kde je chyba?

Díky moc za radu.

Torpy · 04. 05. 2011 20:13

Opravdu nevíte nikdo?
Budu rád za každý hint...
Díky

check_drummer · 05. 05. 2011 19:24

Já v tom na první pohled nevidím žádný problém.

musixx · 06. 05. 2011 07:56 — Editoval musixx (06. 05. 2011 08:30)

↑ Torpy: Jediné, co jsi tím dokázal, je podle mě to, že $$2^m$^4$ je jednička v ${\mathbb Z}_p^\times$ . Ovšem to už máme z malé Fermatovy věty, protože pro $(2,p)=1$ máme $$2^m$^4\equiv2^{4m}\equiv2^{p-1}\equiv1\ ({\rm mod}\ p)$ .

Chybí mi tam zdůvodnění, proč je pak $$2^m$^2\equiv-1\ ({\rm mod}\ p)$ . A k tomu budeme potřebovat předpoklad lichého m, který nevidím, že bys nějak použil (použil jsi ho teda tam, kde tvrdíš, že $a\mapsto2^a$ je izo, ale není jasné, jsi-li si toho vědom: EDIT: kdy je m generátor v ${\mathbb Z}_{p-1}$ ?). Tvrzení totiž není pravdivé pro sudá m: $$2^4$^2\equiv1\not\equiv-1\ ({\rm mod}\ 17)$ (a tedy ani tvé tvrzení o řádu).

Základní problém je v té definici izomorfismu. Žádá doladit... A možná na to jdeš zbytečně složitě - výše zmíněná malá Fermatova věta a úvaha, jak vypadají odmocniny z +1, vedou také k cíli.

Torpy · 19. 05. 2011 22:11

↑ musixx:
Díky, byl jsem teď nějakou dobu mimo, tak jsem se k tomu dostal opět až teď a upravil jsem to takto:

Ověřuji, že prvek $2^m$ je řádu 4 v $\mathbb Z_p^*$ .
Jednak platí, že $\mathbb Z_p^*$ je cyklická řádu p-1=4m, tedy (z LaGrangeovy věty) obsahuje prvek řádu 4.
Dále platí, že $$2^m \mod p$^4=$2^m$^4 \mod p=2^{4m} \mod p=2^{p-1} \mod p$
Z (malé) Fermatovy věty pak $2^{p-1} \mod p=1$
To znamená, že prvek $2^m$ je exponentu 4, tedy může mít řád 1,2 nebo 4.
Vím, že $\mathbb Z_p^*$ obsahuje 1 prvek řádu 1 a 1 prvek řádu 2, přičemž oba tyto prvky jsou čtvercem nějakého čísla v $\mathbb Z_p^*$ .
(1 je čtvercem -1 a -1 je čtvercem prvku řádu 4).
Dále platí, že prvek 2 není čtvercem v $\mathbb Z_p^*$ protože $p\equiv5 \mod 8$ , tedy pro všechna a ze $\mathbb Z_p^*$ je $a^2\neq2$ ,
díky izomorfismu $\mathbb Z_p^*\simeq\mthbb Z_{p-1}$ ekvivalentně platí, že $a\not\in2\mathbb Z_{p-1}$ .
Protože m je liché, pak i $m\cdot a\not\in2\mathbb Z_{p-1}$ .
To znamená, že prvek $2^m$ není čtvercem v $\mathbb Z_p^*$ , tedy musí být řádu 4.