Matematické Fórum

mb305 · 08. 02. 2015 16:11

Ahoj,

mám příklad $248^{1000000000031110} (mod 250)$ . Zkusil jsem:

1/ Vyloučil jsem Malou Fermatovu větu. 250 není prvočíslem.
2/ Vyloučil jsem přímé použití Eulerovy věty, protože 250 a 248 jsou soudělná čísla.

Postupoval jsem tak, že jsem 248 jsem si rozložil na 2^3 * 31. U 31 jsem použil Eulerovu větu. Eulerova funkce mi vyšla = 100. Proto jsem ponechal $2^{3^{1000000000031110}} * 31^{10} (mod 250)$ . Nevím jak zredukovat $2^3$

Pavel · 08. 02. 2015 16:29

↑ mb305:

Není jednodušší vyjít z toho, že

$248\equiv -2\quad(\text{mod }250)$ ?

Pak lze vyšetřovat $(-2)^{1000000000031110}\quad(\text{mod }250)$

mb305 · 08. 02. 2015 16:51 — Editoval mb305 (09. 02. 2015 16:40)

↑ Pavel:

Editace - napsal jsem hloupost:

Autor skryl část textu. Zobrazit/skrýt!

ttt_ · 08. 02. 2015 17:33

↑ mb305:
Podla mna (-2,250)=2 , takze cisla su sudelitelne...

Pavel · 08. 02. 2015 17:57

↑ mb305:

Na to je brzo. Jak poznamenal ↑ ttt_:, obě čísla jsou soudělná. Problém lze převést na hledání $0\leq x\leq 249$ , pro které platí

$2^{1000000000031110}\equiv x\quad(\text{mod }250)$

Kongruenci stačí vydělit dvěma

$2^{1000000000031109}\equiv \frac x2\quad(\text{mod }125)$

a zavést substituci $\frac x2=y$ , tj.

$2^{1000000000031109}\equiv y\quad(\text{mod }125)$

Zde už Eulerovu větu použít můžeš.

mb305 · 09. 02. 2015 16:47

↑ ttt_:
↑ Pavel:

Moc děkuji za upozornění.

Takže udělám Eulerovu fnci = 100. Zbyde 2^9. Spočítám, výjde 512. Po modulení zbyde 12. Vyjádřením substituce získám x = 24.

Matematické Fórum

#1 08. 02. 2015 16:11

Počítání modulo

#2 08. 02. 2015 16:29

Re: Počítání modulo

#3 08. 02. 2015 16:51 — Editoval mb305 (09. 02. 2015 16:40)

Re: Počítání modulo

#4 08. 02. 2015 17:33

Re: Počítání modulo

#5 08. 02. 2015 17:57

Re: Počítání modulo

#6 09. 02. 2015 16:47

Re: Počítání modulo

Zápatí