Berechnen von Modulo < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Berechne [mm] 4^{19} [/mm] mod 2173 |
Wie geht das? Mit Euler-Fermat kann ich es nicht schaffen:
19=x*2080 + y
also daraus kommt entweder eine negative zahl oder kleinere als 1 Zahl
bitte um Hilfe!
|
|
| |
|
> Berechne [mm]4^{19}[/mm] mod 2173
> Wie geht das? Mit Euler-Fermat kann ich es nicht
> schaffen:
>
> 19=x*2080 + y
>
> also daraus kommt entweder eine negative zahl oder kleinere
> als 1 Zahl
>
> bitte um Hilfe!
Baue die Potenz schrittweise auf und reduziere mod 2173,
sobald dies möglich wird. So ist z.B.
[m]4^6=\ 4096\ \hat=\ 1923[/m] (mod 2173)
[m]4^7\ \hat=\ 1923*4 = 7692\ \hat=\ 1173[/m] (mod 2173)
..........
Oder in grösseren Schritten:
[m]4^{12}\ =\ (4^6)^2\ \hat=\ 1923^2\ =\ 3697929\ \hat=\ 1656[/m]
[mm] 4^{18}\ [/mm] = .....
[mm] 4^{19}\ [/mm] = .....
LG al-Chw.
|
|
|
|
