Modulo - Teilergebnisse < Sonstiges < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:30 Mi 26.11.2014 | | Autor: | ggT |
| Aufgabe | | Bei der Modulo-Rechnung ist es erlaubt, dass man beim Vorliegen "großer" Zahlen, also mit vielen Ziffern, einen Teil der Zahl, also die ersten n Ziffern berechnet und das Ergebnis dann an den Rest der übrig gebliebenen Ziffern voranstellt. |
Hallo zusammen,
meine Frage wäre, warum man den oben beschriebenen "Algorithmus" durchführen darf.
Ein Beispiel, falls ich mich oben zu unklar ausgedrückt habe:
Angenommen ich habe die Zahl 12231 und möchte die gern modulo 6 rechnen.
Dann ergibt dies:
12231 mod 6 = 3
Hier wäre 3 das Ergebnis.
Alternativ dazu könnte man nun rechnen:
122 mod 6 = 2 (die 2 wird nun der übrigen Ziffernfolge "31" vorangestellt)
231 mod 6 = 3
Hier wäre auch 3 das Ergebnis.
Und genau den Grund dafür suche ich, warum diese Operation erlaubt ist.
Habe zu Modulo nur die Homomorphieregel gefunden und die kann ich nicht wirklich darauf anwenden.
Vielen Dank im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:01 Do 27.11.2014 | | Autor: | Teufel |
Hi!
Wenn du einen Ausdruck modulo einer Zahl $n$ rechnen willst, dann kannst du in einzelnen Summanden und Faktoren immer modulo $n$ rechnen.
z.B. $6*7+10*8*2 [mm] \equiv [/mm] (6 [mm] \mod [/mm] 4)*(7 [mm] \mod [/mm] 4)+(10 [mm] \mod [/mm] 4)*(8 [mm] \mod [/mm] 4)*(2 [mm] \mod [/mm] 4) [mm] \equiv [/mm] 2*3+2*0*2 [mm] \equiv [/mm] 6 [mm] \equiv [/mm] 2 [mm] \mod [/mm] 4$. Das ist die "Homomorphieregel" mal ganz einfach erklärt.
Damit gilt dann z.B. folgendes:
$12231 [mm] \equiv [/mm] 122*100+31 [mm] \equiv [/mm] (122 [mm] \mod [/mm] 6)*100+31 [mm] \equiv [/mm] 2*100+31 [mm] \equiv [/mm] 231 [mm] \mod [/mm] 6$. Der Trick ist also hier, deine gegebene Zahl einfach in Dezimaldarstellung zu schreiben, also [mm] a_k*10^k+a_{k-1}*10^{k-1}+\ldots+a_1*10+a_0 [/mm] mit [mm] a_i\in\{0,\ldots,9\}.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 03:03 Do 27.11.2014 | | Autor: | ggT |
Hm, also das Beispiel in Verbindung mit der Homomorphieregel leuchtet mir nun ein. Was ich unten allerdings noch nicht verstehe ist, warum man das so schreiben kann:
$ 12231 [mm] \equiv 122\cdot{}100+31 \equiv [/mm] (122 [mm] \mod 6)\cdot{}100+31 \equiv 2\cdot{}100+31 \equiv [/mm] 231 [mm] \mod [/mm] 6 $
und nicht stattdessen Folgendes schreiben muss:
$ 12231 [mm] \equiv 122\cdot{}100+31 \equiv [/mm] (122 [mm] \mod 6)\cdot{}(100 \mod [/mm] 6)+(31 [mm] \mod [/mm] 6) [mm] \equiv 2\cdot{}4+1 \equiv [/mm] 9 [mm] \mod [/mm] 6 $ usw.
(so wäre es doch eigentlich nach obigem Beispiel)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:09 Do 27.11.2014 | | Autor: | Teufel |
Das kannst du auch machen, das Ergebnis ist immer das gleiche im Endeffekt. Allgemeiner kann man das so formulieren:
In Produkten und Summen kann man zu Faktoren und Summanden beliebige Vielfache von $n$ addieren, wenn man modulo $n$ rechnet.
Beispiel: [mm] $3*7+4\equiv [/mm] 11*(-1)+84 [mm] \mod{8}$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 03:48 Do 27.11.2014 | | Autor: | ggT |
Ja das Beispiel kann ich jetzt wieder nachvollziehen, also das man Vielfache von $n$ zu den einzelnen Faktoren bzw. Summanden dazu addieren kann, ich weiß nur nicht wie ich das auf das Folgende beziehen kann.
Das würde dann ja heißen, dass gilt:
$ (a [mm] \mod [/mm] n + b [mm] \mod [/mm] n) [mm] \mod [/mm] n [mm] \equiv [/mm] ((a [mm] \mod [/mm] n) + b) [mm] \mod [/mm] n $
bzw.
$ (a [mm] \mod [/mm] n [mm] \cdot [/mm] b [mm] \mod [/mm] n) [mm] \mod [/mm] n [mm] \equiv [/mm] ((a [mm] \mod [/mm] n) [mm] \cdot [/mm] b) [mm] \mod [/mm] n $
Das ist ja jetzt im Prinzip noch das, was mir nicht ganz klar ist, warum diese Aussage stimmt. (und wo in der Homomorphieregel dies begründet ist)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:13 Do 27.11.2014 | | Autor: | Teufel |
Da ich nicht weiß wie fit du in Gruppentheorie bist, hier eine recht einfache Erklärung:
$a [mm] \mod [/mm] n$ hat immer die Form $a+k*n$ für ein [mm] $k\in\IZ$, [/mm] z.B. $2 = (20 [mm] \mod [/mm] 3) = 20+(-6*3)$. Das liegt einfach an der Division mit Rest, für [mm] $a,n\in\IZ$, $n\not=0$ [/mm] kannst du immer $a=kn+r$ schreiben, [mm] $0\le [/mm] r <b$, also [mm] $a-kn=r=(a\mod [/mm] n)$.
Also ist [mm] $(a\mod [/mm] n)=a+k_an$, [mm] $(b\mod [/mm] n)=a+k_bn$ und damit [mm] $((a\mod n)+(b\mod [/mm] n)) [mm] \mod n=((a+k_an)+(b+k_bn)+kn=a+b+(k_a+k_b+k)n$
[/mm]
Analog ist [mm] $((a\mod [/mm] n)+b) [mm] \mod n=((a+k_an)+b+k'n=a+b+(k_a+k')n$. [/mm] Nun haben also [mm] $((a\mod n)+(b\mod [/mm] n)) [mm] \mod [/mm] n$ und [mm] $((a\mod [/mm] n)+b) [mm] \mod [/mm] n$ den selben Rest modulo $n$ (nämlich $a+b$) und liegen auch beide zwischen 0 und $n$. Das geht aber nur, wenn beide Terme gleich sind, wie man sich leicht überlegen oder an einem Schaubild klarmachen kann.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 04:31 Do 27.11.2014 | | Autor: | ggT |
Ok, das klingt ja dann doch recht kompliziert, aber ich glaube tatsächlich, dass mir das dann als Antwort reicht. :)
Vielen Dank für die Zeit und Mühe, hat mir sehr weitergeholfen!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:11 Do 27.11.2014 | | Autor: | Teufel |
Was ist genau kompliziert? ;) der letzte Teil?
|
|
|
|
