Matematické Fórum

Witiko · 18. 06. 2014 20:49 — Editoval Witiko (18. 06. 2014 21:07)

Zdravím,

Řeším následující modulární rovnici: $x\equiv14^{15^{14^{13}}} \pmod{80}$ . Normálně bych rovnici řešil následovně: $x\equiv14^t, 14^t\equiv14^{15^{14^{13}}} \pmod{80} \iff t\equiv15^{14^{13}}\pmod{r_{80}^{14}}$ , kde $r_{80}^{14}$ je řád 14 modulo 80 s využitím lemmatu $(a, m) = 1 \implies a^x \equiv a^y\pmod{m} \iff x\equiv y\pmod{r_m^a}$ .

Problémem je, že $(14, 80) \not=1$ , což znemožňuje jak nalezení řádu $r_{80}^{14}$ , tak využití zmiňovaného lemmatu. Rovnici si mohu zredukovat na následující soustavu:
$x\equiv14^{15^{14^{13}}}\equiv(2\cdot7)^{15^{14^{13}}}\equiv(0\cdot7)^{15^{14^{13}}}\equiv0\pmod{2}\\ x\equiv14^{15^{14^{13}}}\equiv4^{15^{14^{13}}}\pmod{5}$

Nyní mám podle čínské zbytkové věty zaručenou existenci právě jednoho řešení modulo 10:
$x \equiv0\pmod2\\ x = 2s\\\text{ }\\ x = 2s\equiv4^{15^{14^{13}}}\pmod{5}\\ 2s\equiv4^t, 4^t\equiv4^{15^{14^{13}}}\pmod5\iff t\equiv 15^{14^{13}}\equiv1^{14^{13}} = 1\pmod{r_5^4=2}\\ t\equiv1\pmod{2}\implies s\equiv2\pmod{5}\\ s = 2 + 5u\\\text{ }\\ x=2s=2(2+5u)=4+10u\\ x\equiv4\pmod{10} \implies x\equiv\{4, 14, 24, 34, 44, 54, 64, 74\}\pmod{80}$

Stále však dochází ke ztrátě informace, jelikož ve skutečnosti existuje právě jedno řešení modulo 80. Nevíte, jakým způsobem k řešení rovnice přistoupit?

Bati · 19. 06. 2014 09:21

Ahoj ↑ Witiko:,
já bych na to použil Eulerovu větu, to je tak na 5 řádků. Nejprve celou rovnici "pokrátíš" 16 a pak třikrát za sebou použiješ Eulera (vyjde ti, že $14^{13}\equiv0\mod2$ , $15^{14^{13}}-4\equiv1\mod4$ , $\frac{x}{16}\equiv7^{15^{14^{13}}}2^{15^{14^{13}}-4}\equiv14^{15^{14^{13}}-4}\mod5$ .

Witiko · 19. 06. 2014 11:27 — Editoval Witiko (19. 06. 2014 11:33)

Ahoj, ↑ Bati:,

nějak tam nevidím tu Eulerovu větu, spíš pouze uváděné lemma
$(a, m) = 1 \Rightarrow \Big(a^x \equiv a^y\pmod{m} \iff \big(x\equiv y\pmod{r_m^a}\Leftarrow x\equiv y\pmod{\varphi(m)}\big)\Big)$ .

Každopádně díky za postrčení, teď už vím, jak tu rovnici řešit:
$x\equiv14^{15^{14^{13}}}\equiv2^{15^{14^{13}}}\cdot7^{15^{14^{13}}}\pmod{80}\text{ }/:16\\ \frac{x}{16}\equiv2^{15^{14^{13}}-4}\cdot7^{15^{14^{13}}}\equiv2^{15^{14^{13}}-4}\cdot2^{15^{14^{13}}}\equiv2^{2\cdot(15^{14^{13}})-4}\pmod{5} \\\frac{x}{16}\equiv 2^s, 2^s\equiv2^{2\cdot(15^{14^{13}})-4}\pmod5\iff s\equiv2\cdot(15^{14^{13}})-4\pmod{\varphi(5)=4}\\\text{ }\\ \frac{s+4}2\equiv3^{14^{13}}\pmod{4}\\ \frac{s+4}2\equiv3^t, 3^t\equiv3^{14^{13}}\pmod{4}\iff t\equiv14^{13}\pmod{\varphi(4)=2}\\\text{ }\\ t\equiv0\pmod2\\\text{ }\\ \frac{s+4}2\equiv3^t\equiv3^0\equiv1\pmod{4}\text{ }/\cdot2\\ s+4\equiv2\pmod{4}\\ s\equiv-2\equiv2\pmod{4}\\\text{ }\\ \frac{x}{16}\equiv2^s\equiv2^2\equiv4\pmod5\text{ }/\cdot16\\ x\equiv64\pmod{80}$

Jinak ten krok $7^{15^{14^{13}}}2^{15^{14^{13}}-4}\equiv14^{15^{14^{13}}-4}\mod5$ , který jsi psal, je chyba, nebo tam je nějaký mezikrok, který nevidím?

Xellos · 19. 06. 2014 11:52 — Editoval Xellos (19. 06. 2014 11:52)

80 vieme rozlozit na mocniny roznych prvocisel: 5 a 16.

No, $15^{14^{13}}$ je velke cislo, takze $14^{15^{14^{13}}}$ bude delitelne strasne velkou mocninou 2, teda aj 16-tkou. $14^{15^{14^{13}}} \equiv 0 \mod 16$

Pre zvysok mod 5 si vsimni ze $14 \equiv -1 \mod 5$ a v exponente ma neparne cislo, takze $14^{15^{14^{13}}} \equiv -1 \mod 5$ .

Podla Cinskej zvyskovej vety potom plati $14^{15^{14^{13}}} \equiv 0\cdot5+(-1)\cdot16=64 \mod 80$ . Hotovo.

Bati · 19. 06. 2014 11:53

Žádné lemma jsem nepoužil, je to přesně ta věta. Používám tam hodnoty Eulerovy fce v 5 a 4. $7^4\equiv1$ . Na větší detaily nemám teď čas.

Witiko · 19. 06. 2014 12:14

↑ Bati:
Už to v tom vidím. To je nesmírně elegantní použití Eulerovy věty! :-)

↑ Xellos:
Nj. Koukám, že moje řešení je příslověčným kladivem na vrabce. Díky

Matematické Fórum

#1 18. 06. 2014 20:49 — Editoval Witiko (18. 06. 2014 21:07)

Hledání zbytku po dělení velkého čísla

#2 19. 06. 2014 09:21

Re: Hledání zbytku po dělení velkého čísla

#3 19. 06. 2014 11:27 — Editoval Witiko (19. 06. 2014 11:33)

Re: Hledání zbytku po dělení velkého čísla

#4 19. 06. 2014 11:52 — Editoval Xellos (19. 06. 2014 11:52)

Re: Hledání zbytku po dělení velkého čísla

#5 19. 06. 2014 11:53

Re: Hledání zbytku po dělení velkého čísla

#6 19. 06. 2014 12:14

Re: Hledání zbytku po dělení velkého čísla

Zápatí