Modulo berechnen < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 06:53 Do 18.06.2009 | | Autor: | eppi1981 |
| Aufgabe | (a) Zeigen Sie: [mm] 2^{251} [/mm] ≡1 mod 503 .
(c) Berechnen Sie: [mm] 24^{800} [/mm] ≡ mod 43 . |
hallo,
kann mir jemand erklären, wie man das berechnen soll
|
|
| |
|
> (a) Zeigen Sie: [mm]2^{251}[/mm] ≡1 mod 503 .
> (c) Berechnen Sie: [mm]24^{800}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
≡ mod 43 .
> hallo,
>
> kann mir jemand erklären, wie man das berechnen soll
Hallo,
auf jeden Fall kann man sich langsam vortasten in diesem Stil:
2^{251} =2^{9*27+8) =(2^9)^{27}*2^{8} =512^{27}*2^{8} \equiv 9^{27}*2^{8} = ... (mod 503)
Bei 24^{800} hilft gewiß, daß 800=19*42+2. (Satz v. Euler)
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:41 Do 18.06.2009 | | Autor: | eppi1981 |
leider kann ich nicht weiter :(((
[mm] 2^{251} =2^{9*27+8} =(2^9)^{27}*2^{8} =512^{27}*2^{8} \equiv 9^{27}*2^{8} [/mm] = ... (mod 503)
ich habe nur eine Idee
[mm] 9^{27}*2^{8}=(3^2)^27*2^8=???[/mm]
|
|
|
| |
|
> leider kann ich nicht weiter :(((
>
>
> [mm]2^{251} =2^{9*27+8} =(2^9)^{27}*2^{8} =512^{27}*2^{8} \equiv 9^{27}*2^{8}[/mm]
> = ... (mod 503)
>
> ich habe nur eine Idee
> [mm]9^{3*9}*2^{8}=(9^3)^3*2^8[/mm]
Hallo,
es ist [mm] 9^{3*9} [/mm] nicht dasselbe wie [mm] (9^3)^3.
[/mm]
Es geht hier auch weniger um Ideen als darum, mal ein bißchen herumzuprobieren. Einen Taschenrechner hast Du doch, oder?
Ich habe z.B. eben beim Probieren gesehen, daß 9^4equiv 22 ist, und dies würde ich nun als nächstes verwenden.
Es gibt hier sicher mehrere Wege zum Ziel.
Ömm - "modulo irgendwas" rechnen, das kannst Du aber, oder?
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:08 Do 18.06.2009 | | Autor: | eppi1981 |
leider kann ich das nicht, deswegen habe ich gefragt, ob jemanden mir das erklären kann.
|
|
|
| |
|
> leider kann ich das nicht, deswegen habe ich gefragt, ob
> jemanden mir das erklären kann.
Hallo,
nein, du hast nach diesen beiden Aufgaben gefragt.
Daß Du aber gar nicht weißt, was "modulo" ist, hast Du bisher nicht verraten.
Dein Problem ist also ein Stückchen vor diesen Aufgaben angesiedelt, wenn ich Dich recht verstehe.
Kongruent modulo 7 sind all die Zahlen, die bei der Division durch 7 denselben Rest lassen, oder anders ausgedrückt: deren Differenz ein Vielfaches von 7 ist.
Weil z.B. 11=1*7+4 und 81=11*7+4, sind 11 und 81 kongruent modulo 7, oft geschrieben: [mm] 11\equiv [/mm] 81 mod 7
Für das Rechnen mit Kongruenzen gelten nun einige Regeln, die Du in der Literatur oder auch ![[]](/images/popup.gif) hier findest, und auf diesen Regeln, insbesondere auf
"Ist n [mm] \in \mathbb{N}_0 [/mm] eine natürliche Zahl und [mm] a\equiv [/mm] a' mod m, dann gilt
[mm] a^n \equiv (a')^n \pmod{m} [/mm] ",
beruht das, was ich Dir oben zu tun nahegelegt hatte.
Vielleicht machst Du Dich jetzt im Selbststudium mit den Kongruenzen etwas vertraut und bearbeitest ein paar sehr leichte Aufgaben dazu, damit Du erstmal weißt, worum es geht.
Bei Fragen kannst Du gerne fragen, aber eine komplette Vorlesung tippen, wollen wir hier natürlich nicht.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:01 Do 18.06.2009 | | Autor: | eppi1981 |
[mm] 2^{251} =2^{9*27+8} =(2^9)^{27}*2^{8} =512^{27}*2^{8} \equiv 9^{27}*2^{8}=9^{4*6+3}*2^8=(9^4)^6*9^3*2^8 \equiv 22^6*9^3*2^8=(11*2)^6*9^3*2^8=11^6*9^3*2^14=2^{9+5}*11^6*9^3=2^5*2^9*9^3*11^6 \equiv 2^5*9*9^3*11^6=9^4*2^5*11^6 \equiv 22*2^5*11^6=2^6*11^7
[/mm]
[mm] =2^6*11^{4+3}\equiv54*2^6*11^3=9*6*2^6*11^3\equiv73*6*11^3\equiv73*441\equiv1 [/mm] mod 503
ist soweit richtig?
|
|
|
| |
|
> [mm]2^{251} =2^{9*27+8} =(2^9)^{27}*2^{8} =512^{27}*2^{8} \equiv 9^{27}*2^{8}=9^{4*6+3}*2^8=(9^4)^6*9^3*2^8 \equiv 22^6*9^3*2^8=(11*2)^6*9^3*2^8=11^6*9^3*2^14=2^{9+5}*11^6*9^3=2^5*2^9*9^3*11^6 \equiv 2^5*9*9^3*11^6=9^4*2^5*11^6 \equiv 22*2^5*11^6=2^6*11^7[/mm]
>
> [mm]=2^6*11^{4+3}\equiv54*2^6*11^3=9*6*2^6*11^3\equiv73*6*11^3\equiv73*441\equiv1[/mm]
> mod 503
> ist soweit richtig?
Hallo,
ich habe keinen TR zur Hand im Moment, daher werde ich mich hüten, alles nachzurechnen.
Aber so, wie es dasteht, sieht es so aus, als hättest Du es nun verstanden - und am Ende kommt ja auch das richtige Ergebnis heraus.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:00 Do 18.06.2009 | | Autor: | eppi1981 |
[mm] 24^800=24^{19*42+2}\equiv38^{42}*24^2=\equiv17*38^{42}=17*(19*2)^{42}=17*19^{6*7}*2^{6*7}\equiv17*37^6*2^{6*7}\equiv17*37^6*21^7=17*37^{2*3}*(7*3)^7\equiv17*36^3*7^7*37
[/mm]
ist soweit richtig?
|
|
|
| |
|
Hallo eppi1981,
>
> [mm]24^800=24^{19*42+2}\equiv38^{42}*24^2=\equiv17*38^{42}=17*(19*2)^{42}=17*19^{6*7}*2^{6*7}\equiv17*37^6*2^{6*7}\equiv17*37^6*21^7[/mm]
>
> ist soweit richtig?
Das ist soweit richtig.
Die Rechnung läßt sich vereinfachen, wenn der kleine Fermat zu Hilfe genommen wird.
Teil a) stimmt auch. ![[ok]](/images/smileys/ok.gif "[ok]")
Gruß
MathePower
|
|
|
|
