Euler-Fermat < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:57 Fr 01.05.2015 | | Autor: | KilaZ |
| Aufgabe | | Berechne [mm] 3^{2014^{2014}} [/mm] mod 49 |
Hi,
ich komme bei der Aufgabe nicht weiter. Zuerst habe ich mein [mm] \phi(49) [/mm] bestimmt und erhalte [mm] \phi(49)=42. [/mm]
Dann kann ich schreiben:
[mm] 3^{2014^{2014} mod 42}\equiv3^{2014^{47*42+40} mod 42}\equiv3^{2014^{40} mod 42}
[/mm]
Nun gut, jetzt habe ich meine Aufgabenstellung reduziert, doch [mm] 2014^{40} [/mm] mod 42 kann ich nicht berechnen. Muss ich hier erneut das [mm] \phi [/mm] von 42 bestimmen und nochmals das Ganze wiederholen?
Vielen Dank für eure Hilfe!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:08 Sa 02.05.2015 | | Autor: | bezier |
Hallo,
2014 = 2016 - 2
2014 = 48 * 42 - 2
2014 [mm] \equiv [/mm] - 2 mod 42
Dann :
[mm] 2014^{40} \equiv (-2)^{40} [/mm] mod 42
[mm] 2014^{40} \equiv 4^{20} [/mm] mod 42
Aber : [mm] 4^4 \equiv 4 [/mm] mod 42
Dann :
[mm] 2014^{40} \equiv 4^{ 4 * 4 + 4 } [/mm] mod 42
[mm] 2014^{40} \equiv 16 [/mm] mod 42
Endliche Identifizierung :
[mm] 3^{16 mod 42} \equiv 3^{ 10 + 5 + 1} [/mm] mod 42
[mm] 3^{16 mod 42} \equiv 3^10 * 3^5 * 3^1 [/mm] mod 42
[mm] 3^{16 mod 42} \equiv 4 * ( - 2 ) * 3 [/mm] mod 42
[mm] 3^{16 mod 42} \equiv - 24 [/mm] mod 42
[mm] 3^{16 mod 42} \equiv 25 [/mm] mod 42
Viele Grüsse
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:35 Sa 02.05.2015 | | Autor: | KilaZ |
Hi
vielen Dank für deine Nachricht!
Den letzten Schritt (Endliche Identifizierung) verstehe ich leider nicht. Sollte nicht da stehen: [mm] 3^{16} [/mm] mod 49? Kannst du in Worten erklären, was du hier machst?
Gruss
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mo 04.05.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:37 So 03.05.2015 | | Autor: | bezier |
Hallo,
Entsculdigung,
Ich habe ein Irrtum am Ende gemacht :
In den 4 letzten Linien ( Identifizierung )
Modulo 49, anstatt Modulo 42 :
$ [mm] 3^{2014^{2014} mod 42}\equiv3^{2014^{47\cdot{}42+40} mod 42}\equiv3^{2014^{40} mod 42}\equiv{25 mod 49} [/mm] $
Gruss.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:14 So 03.05.2015 | | Autor: | bezier |
Hallo,
Entschuldigung,
Ich habe ein Irrtum am Ende gemacht :
In den 5 letzten Gleichungen ( Identifizierung )
Modulo 49, anstatt Modulo 42 :
$ [mm] 3^{2014^{2014} mod 42}\equiv3^{2014^{47\cdot{}42+40} mod 42}\equiv3^{2014^{40} mod 42}\equiv{25 mod 49} [/mm] $
Gruss.
|
|
|
| |
|
Hallo KilaZ,
ich fange noch mal ganz von vorn an.
> Berechne [mm]3^{2014^{2014}}[/mm] mod 49
> Hi,
>
> ich komme bei der Aufgabe nicht weiter. Zuerst habe ich
> mein [mm]\phi(49)[/mm] bestimmt und erhalte [mm]\phi(49)=42.[/mm]
Soweit gut.
> Dann kann ich schreiben:
> [mm]3^{2014^{2014} mod 42}\equiv3^{2014^{47*42+40} mod 42}\equiv3^{2014^{40} mod 42}[/mm]
Nein, das stimmt nicht!
Wenn [mm] a\equiv 2014^{2014}\bmod{42} [/mm] ist, dann ist [mm] 3^{2014^{2014}}\equiv 3^a\bmod{49}.
[/mm]
Um nun $a$ zu bestimmen, brauchst Du in der Tat [mm] \varphi(42)=12.
[/mm]
Da [mm] 2014\equiv 10\bmod{12} [/mm] ist, ist [mm] 2014^{2014}\equiv 2014^{10}\bmod{42}.
[/mm]
Das ist immer noch unhandlich, aber Du kannst ja noch die Basis reduzieren. Es ist [mm] 2014\equiv 40\equiv (-2)\bmod{42}, [/mm] also
[mm] 2014^{10}\equiv (-2)^{10}\equiv 2^{10}\bmod{42}. [/mm] Das ist handlich. Insgesamt also
[mm] 3^{2014^{2014}}\equiv 3^{16}\bmod{49}.
[/mm]
Das ist nun leicht mit viermaligem Quadrieren zu lösen. (Kontrollergebnis: 25)
Grüße
reverend
> Nun gut, jetzt habe ich meine Aufgabenstellung reduziert,
> doch [mm]2014^{40}[/mm] mod 42 kann ich nicht berechnen. Muss ich
> hier erneut das [mm]\phi[/mm] von 42 bestimmen und nochmals das
> Ganze wiederholen?
>
> Vielen Dank für eure Hilfe!
|
|
|
|
