Modular-Rechnung < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | 1) 34 mod 11
2) [mm] 34^{16} [/mm] mod 11 |
Hallo,
wir haben heute eine Einführung in die Diskrete Mathematik bekommen und das erste Thema war Rechnen mit Kongruenzen ( kenne ich nur aus der Geometrie , kongruent = deckungsgleich)
Bestimmte Rechnungen kannte ich schon vom Informatikunterricht , zum Beispiel 10 mod 3 = 3 Rest 1 etc.
Aber irgendwie komme ich mit dem neuen Stoff nicht klar, weiß nicht , was ich wie rechnen soll.
Also zum Beispiel die erste Aufgabe:
34 mod 11 = 3 Rest 1. Das ist der einzige Weg der mir einfällt udn den ich auch nur so kenne. Aber bei anderen Aufgaben komme ich nich tmehr klar.
Zum Beispielk die zweite Aufgabe:
[mm] 34^{16} [/mm] mod 11
Hier weiß ich nicht , was ich machen soll , was ich mitbekommen habe ist , dass man diese 34 ^{16} irgendwie vereinfacht bzw anders aufschreibt.
Könnte mir das einer erklären ?
Vielen Dank im Voraus
|
|
| |
|
> 1) 34 mod 11
> 2) [mm]34^{16}[/mm] mod 11
Hallo,
"modulo 11" fragt nach dem Rest bei Division durch 11.
Die 34 läßt bei Division durch 11 den Rest 1, es ist ja 34=3*11+1.
Daher ist
[mm] 34\equiv [/mm] 1 (mod 11).
Nun kannst Du Dir überlegen, daß
[mm] 34^{16}=(3*11+1)^{16}=11*k+1^{16} [/mm] für eine passende ganze Zahl k ist,
und damit kennst Du [mm] 34^{16} [/mm] mod 11.
Beim Umgang mit Kongruenzen ist oft auch der kleine Fermatsche Satz nützlich. Kannst ihn Dir ja mal zu Gemüte führen.
LG Angela
EDIT: Regeln fürs Rechnen mit Kongruenzen findest Du ![[]](/images/popup.gif) hier.
|
|
|
| |
|
Hallo, danke für die Antwort , aber leider habe ich das noch nicht so richtig verstanden.
Also wenn ich [mm] 34^{16} [/mm] habe und diese "zerteile" , habe ich ja,
[mm] (3*11+1)^{16} [/mm] mod 11 und jetzt hast du ja gesagt , dass ich eine Zahl k suchen soll. Also :
11 *k [mm] +1^{16}. [/mm] Was soll ich ejtzt genau machen ? Verstehe die Grundidee leider nicht.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:32 Fr 04.10.2013 | | Autor: | abakus |
> Hallo, danke für die Antwort , aber leider habe ich das
> noch nicht so richtig verstanden.
>
> Also wenn ich [mm]34^{16}[/mm] habe und diese "zerteile" , habe ich
> ja,
> [mm](3*11+1)^{16}[/mm] mod 11 und jetzt hast du ja gesagt , dass
> ich eine Zahl k suchen soll. Also :
> 11 *k [mm]+1^{16}.[/mm] Was soll ich ejtzt genau machen ? Verstehe
> die Grundidee leider nicht.
Hallo,
einer der Sätze, die ihr in der Einführung kennengelernt haben solltet, ist folgender:
"Aus [mm]a\equiv b[/mm] mod m folgt [mm]a^n\equiv b^n[/mm] mod m.".
Nun gilt zunächst [mm]34\equiv 1[/mm] mod 11.
Nimm nun beide Seiten hoch 16.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 15:36 Fr 04.10.2013 | | Autor: | pc_doctor |
Meinst du so hier :
[mm] 34^{16} [/mm] = [mm] 1^{16} [/mm] mod 11 ?
Wie geht es jetzt weiter
|
|
|
| |
|
> Also wenn ich [mm]34^{16}[/mm] habe und diese "zerteile" , habe ich
> ja,
> [mm](3*11+1)^{16}[/mm] mod 11
Hallo,
nein.
Du hast dann, daß [mm] 34^{16}=(3*11+1)^{16} [/mm] ist.
Nix mit "modulo".
>und jetzt hast du ja gesagt , dass
> ich eine Zahl k suchen soll.
Nein, das habe ich nicht gesagt.
Ich habe gesagt: überlege Dir, daß es eine Zahl k gibt, mit [mm] (3*11+1)^{16}=11*k+1^{16}.
[/mm]
Das geht einem z.B. auf, wenn man den binomischen Lehrsatz auf [mm] (3*11+1)^{16} [/mm] losläßt.
Also: es gibt so eine Zahl k mit [mm] 34^{16}=11*k+1^{16}=11*k+1.
[/mm]
Also läßt [mm] 34^{16} [/mm] bei Division durch 11 den Rest 1.
Anders ausgedrückt:
[mm] 34^{16}\equiv [/mm] 1 (mod 11).
> Also :
> 11 *k Was soll ich ejtzt genau machen ? Verstehe
> die Grundidee leider nicht.
Beim Rechnen "modulo p" geht es immer darum, welcher Rest bei Division durch p bleibt.
Dafür gibt's halt auch die von mir verlinkten Rechenregeln,damit man das Rad nicht immer selbst erfinden muß.
LG Angela
|
|
|
| |
|
Danke für die Antworten , ich versuchs mal mit einer neuen Aufgabe:
[mm] 15^{2} [/mm] mod 11
Kann ich jetzt [mm] 15^{2} [/mm] anders aufschreiben z.B:
(10*1 + 5 ) ^{2} oder so , ich kann ja theoretisch auch [mm] (5*3)^{2} [/mm] mod 11 schreiben , muss immer nach dem "Zerteilen" ein Summand da stehen ? Weil wenn ich [mm] (5*3)^{2} [/mm] nehme , dann habe ich ja keinen Rest. Wie kann ich das hier lösen.
|
|
|
| |
|
Hallo pcdr,
Du machst es Dir schwerer als nötig.
> Danke für die Antworten , ich versuchs mal mit einer neuen
> Aufgabe:
>
> [mm]15^{2}[/mm] mod 11
>
> Kann ich jetzt [mm]15^{2}[/mm] anders aufschreiben z.B:
> (10*1 + 5 ) ^{2} oder so , ich kann ja theoretisch auch
> [mm](5*3)^{2}[/mm] mod 11 schreiben , muss immer nach dem
> "Zerteilen" ein Summand da stehen ? Weil wenn ich [mm](5*3)^{2}[/mm]
> nehme , dann habe ich ja keinen Rest.
Bahnhof?
> Wie kann ich das hier
> lösen.
Na, einmal ganz platt: [mm] 15^2=225, [/mm] und das lässt bei Teilung durch 11 offenbar den Rest 5. Fertig.
Hier aber geht es in der Einübung um etwas anderes. Da $15>11$ gilt, ist ja
[mm] 15^2\mod{11}\equiv(15\mod{11})^2\mod{11}\equiv 4^2\equiv 16\equiv 5\mod{11}.
[/mm]
Damit solltest Du auch leicht z.B. [mm] 7946^2\mod{11} [/mm] bestimmen können, ohne mit achtstelligen Zahlen rechnen zu müssen.
Grüße
reverend
|
|
|
| |
|
>
> [mm]15^2\mod{11}\equiv(15\mod{11})^2\mod{11}\equiv 4^2\equiv 16\equiv 5\mod{11}.[/mm]
Und genau das ist der Schritt , den ich auch in diversen Seiten gesehen habe und den ich nicht verstehe.
Wieso : (15 mod [mm] 11)^{2} [/mm] mod 11 [mm] \equiv 4^{2}
[/mm]
Warum diese [mm] 4^{2} [/mm] ? Wie kommt man drauf ?
|
|
|
| |
|
Hallo,
>
> >
> > [mm]15^2\mod{11}\equiv(15\mod{11})^2\mod{11}\equiv 4^2\equiv 16\equiv 5\mod{11}.[/mm]
>
> Und genau das ist der Schritt , den ich auch in diversen
> Seiten gesehen habe und den ich nicht verstehe.
>
> Wieso : (15 mod [mm]11)^{2}[/mm] mod 11 [mm]\equiv 4^{2}[/mm]
>
> Warum diese [mm]4^{2}[/mm] ? Wie kommt man drauf ?
15:11=1 Rest 4, also [mm]15\mod{11}=4[/mm]
Das Problem ist für mich hier nicht die [mm] 4^2 [/mm] sondern die falsche Verwendung der Kongruenzrealtion. Entweder du schreibst
[mm]\left(15\mod{11}\right)^2\mod{11}=4^2[/mm]
oder aber
[mm]\left(15\mod{11}\right)^2\mod{11}\equiv4^2\mod{11}[/mm]
Mache dir den Unterschied klar, am besten durch eingehendes Studium der Unterlagen...
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 16:25 Fr 04.10.2013 | | Autor: | pc_doctor |
>
> [mm]\left(15\mod{11}\right)^2\mod{11}=4^2[/mm]
Was ich auch nicht verstehe , wieso steht dort zwei mal Mod ? Also ich probiers mal nochmal:
[mm] 15^{2} [/mm] mod 11 = (1*11+4) mod 11 , was ist hier falsch ? Das ist doch eine normale Division mit Rest , wieso muss man - wie beim Zitat- 2 mal "mod 11 " stehen haben und quadrieren ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:56 Fr 04.10.2013 | | Autor: | Diophant |
Hallo,
> > [mm]\left(15\mod{11}\right)^2\mod{11}=4^2[/mm]
>
> Was ich auch nicht verstehe , wieso steht dort zwei mal Mod
> ? Also ich probiers mal nochmal:
>
>
> [mm]15^{2}[/mm] mod 11 = (1*11+4) mod 11 , was ist hier falsch ? Das
> ist doch eine normale Division mit Rest , wieso muss man -
> wie beim Zitat- 2 mal "mod 11 " stehen haben und quadrieren
Das muss man überhaupt nicht. Es war ein sehr eleganter Trick, der Autor des Beitrags ist bekannt dafür, dass er über einen unheimlich großen Vorrat solcher Tricks verfügt und diese insbesondere aus Überzeugung und aus Freude an der Sache mit anderen teilt. Das kann man dann annehmen, oder in den Wind schlagen, ganz wie man möchte.
Es macht aber generell keinen Sinn, in diesem von dir vorgetragenen Chatroom-Tempo jemand Kongruenzrechnung erklären zu wollen, der sich nicht die notwendige Zeit und Gründlichkeit gönnt, gegebene Antworten erst einmal auf ihren Sinn hin zu hinterfragen.
Schlag mal die im Betreff genannte Tempobezeichnung irgendwo nach und halte dich dann daran.
Gruß, Diophant
|
|
|
| |
|
>
> >
> > [mm]15^2\mod{11}\equiv(15\mod{11})^2\mod{11}\equiv 4^2\equiv 16\equiv 5\mod{11}.[/mm]
>
> Und genau das ist der Schritt , den ich auch in diversen
> Seiten gesehen habe und den ich nicht verstehe.
>
> Wieso : (15 mod [mm]11)^{2}[/mm] mod 11 [mm]\equiv 4^{2}[/mm]
>
> Warum diese [mm]4^{2}[/mm] ? Wie kommt man drauf ?
Hallo,
Du willst wissen, welchen Rest [mm] 15^2 [/mm] bei Division durch 11 läßt, wozu also [mm] 15^2 [/mm] modulo 11 kongruent ist.
Es ist [mm] 15\equiv [/mm] 4 (mod 11), denn 15=1*11+4.
Nun überlegen wir, welchen Rest [mm] 15^2 [/mm] läßt.
[mm] 15^2=(1*11+4)^2= [/mm] binomische Formel= [mm] blabla*11+4^2.
[/mm]
Wir sehen: [mm] 15^2 [/mm] läßt bei Division durch 11 denselben Rest wie [mm] 4^2. [/mm] In Zeichen:
[mm] 15^2\equiv 4^2 [/mm] (mod 11).
Tja. Und [mm] 4^2=16\equiv [/mm] 5 (mod 11), was ich nun sicher nicht mehr erklären muß.
Diese Überlegungen finden ihren Niederschlag in den von mir verlinkten und dem reverend angewandten Rechenregeln:
Weil [mm] 15\equiv [/mm] 4 (mod 11),
ist [mm] 15^2\equiv 4^2 [/mm] mod 11.
LG Angela
|
|
|
| |
|
Achsooo, langsam verstehe ich es :
Also noch eine Aufgabe , damit ich sicher gehen kann:
[mm] 15^{4} [/mm] mod 11 = [mm] (1*11+4)^{4} [/mm] mod 11
[mm] 15^{4} \equiv 4^{4} [/mm] ( mod 11 )
[mm] 15^{4} \equiv 4^{4} [/mm] = 256 = 14 mod 11
Ist das so richtig ?
|
|
|
| |
|
> Achsooo, langsam verstehe ich es :
>
> Also noch eine Aufgabe , damit ich sicher gehen kann:
>
> [mm]15^{4}[/mm] mod 11 = [mm](1*11+4)^{4}[/mm] mod 11
> [mm]15^{4} \equiv 4^{4}[/mm] ( mod 11 )
> [mm]15^{4} \equiv 4^{4}[/mm] = 256 [mm] \red{=} [/mm] 14 mod 11
>
> Ist das so richtig ?
Hallo,
ja, beim Gleichheitszeichen müßte aber [mm] \equiv [/mm] stehen - oft wird das aber gar nicht so genau unterschieden..
Und dann bist Du noch nicht am Ende: die 14 läßt den Rest 3,
also lautet das Endergebnis
[mm] 15^4\equiv [/mm] 3 (mod 11).
Rechnet man mod 11, will man Endergebnisse zwischen 0 und 10.
Hättest Du auch so finden können:
[mm] 15^4=(15^2)^2\equiv 5^2=25\equiv [/mm] 3 (mod 11).
LG Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:56 Fr 04.10.2013 | | Autor: | pc_doctor |
Alles klar , vielen vielen Dank an alle , ich habs jetzt verstanden.
|
|
|
| |
|
Hallo,
nachdem es offenbar einigermaßen gelungen ist,
die Aufgabe für den Fragesteller zu klären, möchte
ich hier doch gerne noch etwas anfügen, das mit
den (zum Teil auch in der Literatur) oft inkonsequent
oder uneinheitlich verwendeten Bezeichnungsweisen
in diesem Zusammenhang zu tun hat und für viele
ein unnötiges Hindernis darstellt, die sich erstmals
mit Modulo-Rechnungen herumschlagen müssen.
Mich haben die eher unhandlichen Bezeichnungen
jedenfalls auch schon oft gestört.
Betrachten wir als Beispiele folgende Zeilen:
(1) 29 mod 5 = 4
(2) 29 [mm] \equiv [/mm] 14 (mod 5)
(3) 29 mod 5 = 14
Davon ist die Zeile (3) definitiv falsch; (1) und (2)
sind verschiedene (und eben gerade wegen ihrer
Ähnlichkeit verwirrende) gängige Schreibweisen
mittels des Kürzels "mod".
In (1) steht "mod" für eine zweistellige Rechen-
operation oder Funktion wie z.B. auch die Division.
Meiner Meinung nach wäre es in der heutigen Zeit,
wo die Schreibweise mit zweistelligen Funktionen
geläufig sein sollte, eigentlich auch angemessen,
anstelle von: 29 mod 5
zu schreiben: mod(29,5)
Wenn jedoch in einem bestimmten Zusammenhang
im Rahmen der Zahlentheorie z.B. über mehrere
Zeilen hinweg bezüglich einer bestimmten Basis
Modulo-Rechnungen vorkommen, sollte dies vor
allem zu Anfang klar angegeben werden. Dann
mag es genügen, z.B. die Angabe "modulo 5"
(lieber so ausgeschrieben anstatt zu "mod" abge-
kürzt) jeweils noch am Ende einer Zeile in Klammern
anzugeben. Falls dies klar ist, kann man dann ev.
auch das Symbol " [mm] \equiv [/mm] " durch das gewöhnliche
Gleichheitszeichen ersetzen. Allerdings kostet
aber ja auch das Schreiben des dritten Strichleins
keinen enormen Mehraufwand ...
LG , Al-Chwarizmi
|
|
|
|
