Modrechnen! < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:23 Sa 21.03.2009 | | Autor: | Lorence |
| Aufgabe | Man bestimmte:
3^47 mod 23
|
Mir ist aufgefallen, dass (47-1)/2=23 ist,
hat jemand ne idee wie ich OHNE Taschenrechner da ranngehen kann?
Danke schonmal
Gruß
|
|
| |
|
Hallo Lorence,
> Man bestimmte:
>
> 3^47 mod 23
>
> Mir ist aufgefallen, dass (47-1)/2=23 ist,
>
> hat jemand ne idee wie ich OHNE Taschenrechner da ranngehen
> kann?
Benutze den kleinen Satz von Fermat:
Mit p prim und $ggT(a,p)=1$ ist [mm] $a^{p-1}\equiv [/mm] 1 \ [mm] \mod [/mm] p$
Hier ist 23 prim und $ggT(3,23)=1$, also [mm] $3^{22}\equiv [/mm] 1 \ [mm] \mod [/mm] 23$
Also [mm] $3^{44}=\left(3^{22}\right)^2\equiv 1^2=1 [/mm] \ [mm] \mod [/mm] 23$
Den klitzekleinen Rest kriegst du hin, oder ... ?
>
> Danke schonmal
>
> Gruß
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:52 Sa 21.03.2009 | | Autor: | Lorence |
[mm] 3^{44}=1 [/mm] mod 23,
[mm] 3^{44} [/mm] * [mm] 3^{3} [/mm] = 1 mod 23 * 4 mod 23 = 4 mod 23 ???
darf ich das?
Gruß
Danke für deine Hilfe
|
|
|
| |
|
Hallo nochmal,
> [mm]3^{44}=1[/mm] mod 23,
>
> [mm]3^{44}[/mm] * [mm]3^{3}[/mm] = 1 mod 23 * 4 mod 23 = 4 mod 23 ???
>
> darf ich das?
Ja, aber es ist schrecklich aufgeschrieben, ich würde es so schreiben:
Mit [mm] $3^{44}\equiv [/mm] 1 \ [mm] \mod [/mm] 23$ ist [mm] $3^{47}=3^3\cdot{}3^{44}\equiv 3^3\cdot{}1=27\equiv [/mm] 4 \ [mm] \mod [/mm] 23$
>
> Gruß
> Danke für deine Hilfe
Jo, LG
schachuzipus
|
|
|
|
