Rechnen mit Restklassen < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
1. Finde [mm] \overline{x} [/mm] in [mm] \IZ/11\IZ:
[/mm]
[mm] \overline{6} \overline{x}=\overline{2}
[/mm]
Dazu habe ich mir kurz die Menge [mm] \overline{2} [/mm] angeschaut und ein Element gefunden, welches als ganzzahlig vielfaches von 6 darstellbar ist. Dadurch finde ich [mm] \overline{x}=\overline{4}:
[/mm]
24 ist in [mm] \overline{2} [/mm] und [mm] \overline{6}*\overline{4}=\overline{24}
[/mm]
Jetzt lese ich, dass es auch mit dem zu [mm] \overline{6} [/mm] inversen Element gehen sollte.
Fragen dazu:
Woher weiß ich, dass solch ein Element existiert? Muss ein solches Element existieren? (Durch die Hintertür argumentiert: Ja, muss es: gdw die Gleichung lösbar ist.(?))
Wie finde ich systematisch dieses Inverse? Man muss irgendwie herumprobieren, aber wie ist der Ansatz?
[mm] \overline{x}=\overline{2}*\overline{6}^{-1}
[/mm]
EDIT: Bei 2. (u nicht nur da) bin ich mit dem Modulo total durcheinandergekommen...muss ich nochmal anschauen
EDIT: 2. Aufg. teil überflüssig.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:35 Di 07.10.2014 | | Autor: | leduart |
Hallo
nur in Z/pZ p prim gibt es zu jedem Element ein Inverses, also zu 6 in Z(12/z nicht
(da 6 Teiler von 12 ist 2*6=0 3*6=6, 5*6=6
Nur zu zu 12 teilerfremden Zahlen findest du inverse, also etwa zu 5, 7
in Primzahlklassen gibt es immer ein Inverses, , das man aus der Multiplikationstabelle findet.
auch bei normalen Gleichungen 6x=2 multiplizierst du ja mit 1/6, dem Inversen zu 6.
Die erste Gl hat also KEINE Lösung..
Die zweite schon, das Inverse zu 6 findet man direkt am Anfang,, denn 2*6=12=1 mod 11
Merke: Primzahlrestklassen bilden einen Körper, nicht prime keinen
Gruss leduart
|
|
|
| |
|
> Hallo
> nur in Z/pZ p prim gibt es zu jedem Element ein Inverses,
> also zu 6 in Z(12/z nicht
> (da 6 Teiler von 12 ist 2*6=0 3*6=6, 5*6=6
> Nur zu zu 12 teilerfremden Zahlen findest du inverse, also
> etwa zu 5, 7
> in Primzahlklassen gibt es immer ein Inverses, , das man
> aus der Multiplikationstabelle findet.
> auch bei normalen Gleichungen 6x=2 multiplizierst du ja
> mit 1/6, dem Inversen zu 6.
> Die erste Gl hat also KEINE Lösung..
> Die zweite schon, das Inverse zu 6 findet man direkt am
> Anfang,, denn 2*6=12=1 mod 11
> Merke: Primzahlrestklassen bilden einen Körper, nicht
> prime keinen
> Gruss leduart
Danke.
Ich kenne diese "Multiplikationstabelle" nicht, auch den Merksatz hatten wir noch nicht.
Nur mal bzgl.$ [mm] \IZ/11\IZ: [/mm] $
$ [mm] \overline{x}=\overline{2}\cdot{}\overline{6}^{-1} [/mm] $
Und ab hier brauche ich diese Tabelle? Wie sieht das konkret aus?
|
|
|
| |
|
Hallo geigenzaehler,
> > Hallo
> > nur in Z/pZ p prim gibt es zu jedem Element ein
> Inverses,
> > also zu 6 in Z(12/z nicht
> > (da 6 Teiler von 12 ist 2*6=0 3*6=6, 5*6=6
> > Nur zu zu 12 teilerfremden Zahlen findest du inverse, also
> > etwa zu 5, 7
> > in Primzahlklassen gibt es immer ein Inverses, , das
> man
> > aus der Multiplikationstabelle findet.
> > auch bei normalen Gleichungen 6x=2 multiplizierst du ja
> > mit 1/6, dem Inversen zu 6.
> > Die erste Gl hat also KEINE Lösung..
> > Die zweite schon, das Inverse zu 6 findet man direkt
> am
> > Anfang,, denn 2*6=12=1 mod 11
> > Merke: Primzahlrestklassen bilden einen Körper, nicht
> > prime keinen
> > Gruss leduart
>
> Danke.
>
> Ich kenne diese "Multiplikationstabelle" nicht, auch den
> Merksatz hatten wir noch nicht.
>
> Nur mal bzgl.[mm] \IZ/11\IZ:[/mm]
>
> [mm]\overline{x}=\overline{2}\cdot{}\overline{6}^{-1}[/mm]
>
> Und ab hier brauche ich diese Tabelle? Wie sieht das
> konkret aus?
>
Um das Inverse zu berechnen, benötigst Du diese Tabelle nicht.
Es geht auch mit Hilfe des euklidischen Algorithmus.
Dazu ist der ggT von 11 und 6 gleich 1.
Demnach muss es ein [mm]\alpha, \ \beta \in \IZ[/mm] geben, so daß
[mm]\alpha*11+\beta*6=1[/mm]
Zunächst wird so begonnen:
[mm]11=1*6+5[/mm]
[mm]6=1*5+1[/mm]
Dann ist
[mm]1=1*6-1*5[/mm]
Dann wird die 5 als Vielfachsumme von 11 und 6 dargestellt:
[mm]1=1*6-1*\left(1*11-1*6\right)=2*6-1*11[/mm]
Damit ist 2 das Inverse zu 6 in [mm]\IZ/11\IZ[/mm]
Gruss
MathePower
|
|
|
| |
|
Danke für die Antwort!
Bzgl. mod11:
Kann ich nicht einfach so vorgehen, wenn ich zu [mm] \overline{6} [/mm] das Inverse suche?
1. bzgl. Addition:
[mm] \overline{6}+\overline{6}^{-1}=! \overline{0}
[/mm]
[mm] \overline{6}+\overline{5}=\overline{11} [/mm] , wobei 11 mod11=0
Dadurch ist [mm] \overline{6}^{-1}=\overline{5}
[/mm]
2. Bzgl. Multiplikation:
[mm] \overline{6}*\overline{6}^{-1}=! \overline{1}
[/mm]
es soll also ein [mm] \overline{6}^{-1}:=x [/mm] geben mit
[mm] \bruch{6*x}{11}=X+1, [/mm] mit X ganzzahlig. [<- Kann man das so schreiben für "11 teilt 6*x X mal ganzzahlig mit Rest 1?" Sieht eigentlich kriminell aus...besser 6x mod 11 =! 1, oder?]
Setzt man 2 ein, so passt das: 12/11=1 Rest 1
Das wäre jetzt durch Probieren gefunden, aber ist der Gedankengang richtig?
Das mit dem euklid. Algoritmus (-meine Veranstalutng heisst nicht "Zahlentheorie"), welcher in unserem Skript ueberhaupt nicht vorkommt, muss ich mir nochmal ansehen.
|
|
|
| |
|
Hallo geigenzaehler,
> Danke für die Antwort!
>
> Bzgl. mod11:
> Kann ich nicht einfach so vorgehen, wenn ich zu
> [mm]\overline{6}[/mm] das Inverse suche?
>
> 1. bzgl. Addition:
> [mm]\overline{6}+\overline{6}^{-1}=! \overline{0}[/mm]
>
> [mm]\overline{6}+\overline{5}=\overline{11}[/mm] , wobei 11 mod11=0
>
> Dadurch ist [mm]\overline{6}^{-1}=\overline{5}[/mm]
>
![[ok]](/images/smileys/ok.gif "[ok]")
> 2. Bzgl. Multiplikation:
>
> [mm]\overline{6}*\overline{6}^{-1}=! \overline{1}[/mm]
>
> es soll also ein [mm]\overline{6}^{-1}:=x[/mm] geben mit
>
>
> [mm]\bruch{6*x}{11}=X+1,[/mm] mit X ganzzahlig. [<- Kann man das so
> schreiben für "11 teilt 6*x X mal ganzzahlig mit Rest 1?"
> Sieht eigentlich kriminell aus...besser 6x mod 11 =! 1,
> oder?]
>
Letzteres trifft den Kern.
> Setzt man 2 ein, so passt das: 12/11=1 Rest 1
> Das wäre jetzt durch Probieren gefunden, aber ist der
> Gedankengang richtig?
> Das mit dem euklid. Algoritmus (-meine Veranstalutng
> heisst nicht "Zahlentheorie"), welcher in unserem Skript
> ueberhaupt nicht vorkommt, muss ich mir nochmal ansehen.
Dann wirst Du um eine solche Multiplikationstabelle nicht herumkommen.
Gruss
MathePower
|
|
|
| |
|
Ich denke, da wir weder diese Tabelle noch diesen Algorithmus hatten, ist es so gemeint:
Bzgl. Suche nach Inversem x zu [mm] \overline{6} [/mm] mit
[mm] \overline{6}*x=\overline{1}
[/mm]
Dann schaut man sich an
[mm] \overline{1}= [/mm] {...,1,12,...}
Und frage man sich, ob man mit einem Vielfachen von 6, nämlich x*6, ein Element aus [mm] \overline{1} [/mm] bauen kann.
Für x=2 bekommt man 6*2=12 und das liegt in [mm] \overline{1}, [/mm] wodurch [mm] \overline{12}=\overline{1} [/mm] => Inverse= [mm] \overline{2}.
[/mm]
Das ergibt doch Sinn, oder?
Setzt natürlich voraus, dass die Klassen so gestrickt sind, dass man schnell sieht, wie man welches Vielfache zusammenbauen kann.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:59 Di 07.10.2014 | | Autor: | Marcel |
Hallo,
> Ich denke, da wir weder diese Tabelle noch diesen
> Algorithmus hatten, ist es so gemeint:
>
> Bzgl. Suche nach Inversem x zu [mm]\overline{6}[/mm] mit
>
> [mm]\overline{6}*x=\overline{1}[/mm]
>
> Dann schaut man sich an
>
> [mm]\overline{1}=[/mm] {...,1,12,...}
>
> Und frage man sich, ob man mit einem Vielfachen von 6,
> nämlich x*6, ein Element aus [mm]\overline{1}[/mm] bauen kann.
>
> Für x=2 bekommt man 6*2=12 und das liegt in [mm]\overline{1},[/mm]
> wodurch [mm]\overline{12}=\overline{1}[/mm] => Inverse=
> [mm]\overline{2}.[/mm]
>
> Das ergibt doch Sinn, oder?
natürlich. Du hast eine ENDLICHE Menge
[mm] $\IZ/11\IZ=\{\overline{0},\overline{1},...,\overline{10}\}\,.$
[/mm]
Die Frage, ob [mm] $\overline{6}$ [/mm] ein Inverses hat, kann dann natürlich beantwortet
werden, indem man testet, ob
[mm] $\overline{6}*\overline{x}=\overline{1}$
[/mm]
für ein $x [mm] \in \{0,...,10\}$ [/mm] gilt.
Das "Rechnen in endlichen Mengen" ist dahingehend natürlich sehr viel
einfacher als in nicht endlichen Mengen.
Gruß,
Marcel
|
|
|
| |
|
Das ist natürlich herrlich schlüssig. Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:50 Di 07.10.2014 | | Autor: | Marcel |
Hallo,
> > Hallo
> > nur in Z/pZ p prim gibt es zu jedem Element ein
> Inverses,
> > also zu 6 in Z(12/z nicht
> > (da 6 Teiler von 12 ist 2*6=0 3*6=6, 5*6=6
> > Nur zu zu 12 teilerfremden Zahlen findest du inverse, also
> > etwa zu 5, 7
> > in Primzahlklassen gibt es immer ein Inverses, , das
> man
> > aus der Multiplikationstabelle findet.
> > auch bei normalen Gleichungen 6x=2 multiplizierst du ja
> > mit 1/6, dem Inversen zu 6.
> > Die erste Gl hat also KEINE Lösung..
> > Die zweite schon, das Inverse zu 6 findet man direkt
> am
> > Anfang,, denn 2*6=12=1 mod 11
> > Merke: Primzahlrestklassen bilden einen Körper, nicht
> > prime keinen
> > Gruss leduart
>
> Danke.
>
> Ich kenne diese "Multiplikationstabelle" nicht, auch den
> Merksatz hatten wir noch nicht.
>
> Nur mal bzgl.[mm] \IZ/11\IZ:[/mm]
>
> [mm]\overline{x}=\overline{2}\cdot{}\overline{6}^{-1}[/mm]
an dieser Stelle auch mal ein Hinweis: Du darfst hier so rechnen, weil die
entsprechende Multiplikation kommutiert (unter der Annahme oder mit
einer Begründung, dass [mm] $\overline{6}^{-1}$ [/mm] auch in [mm] $\IZ/(11\IZ)$ [/mm] existiert).
Aber "eigentlich" sollte man das Ganze lieber so rechnen:
[mm] $\overline{6}*\overline{x}=\overline{2}$
[/mm]
[mm] $\Rightarrow$ $\overline{6}^{-1}*(\overline{6}*\overline{x})=\overline{6}^{-1}*\overline{2}$ [/mm]
[mm] $\Rightarrow$ $(\overline{6}^{-1}*\overline{6})*\overline{x}=\overline{6}^{-1}*\overline{2}$ [/mm]
[mm] $\Rightarrow$ $\overline{x}=\overline{6}^{-1}*\overline{2}\,.$
[/mm]
Ich sage das deswegen, weil Du ansonsten im Ring der Matrizen, wo selbst
bei quadratischen Matrizen die Multiplikation nicht kommutiert, evtl. so
wie oben rechnen könntest. Und das kann dann gewaltig in die Hose gehen...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:44 Di 07.10.2014 | | Autor: | Marcel |
Hallo,
> 1. Finde [mm]\overline{x}[/mm] in [mm]\IZ/11\IZ:[/mm]
>
> [mm]\overline{6} \overline{x}=\overline{2}[/mm]
es gilt folgender Satz (siehe etwa "Elementare und algebraische Zahlentheorie"
von Müller-Stach, Piontkowski):
Die Gleichung
$ax [mm] \equiv [/mm] b$ [mm] $\mod$ $n\,$
[/mm]
hat genau dann eine Lösung, wenn
[mm] $\ggT(a,n)\;|\;b\,.$
[/mm]
Alle Lösungen $x [mm] \in \IZ$ [/mm] findet man in diesem Falle wie folgt:
Seien
$y,z [mm] \in \IZ$ [/mm] mit [mm] $\ggT(a,n)=\red{y}\,*a+z*b\,.$
[/mm]
Dann ist
$ax [mm] \equiv [/mm] b$ [mm] $\mod$ $n\,$
[/mm]
gleichwertig zu
$x [mm] \equiv \red{y}\,*\frac{b}{\ggT(a,n)}$ $\mod$ $\frac{n}{\ggT(a,n)}\,.$
[/mm]
Bei Dir:
[mm] $\overline{6}\overline{x}=\overline{2}$ [/mm] in [mm] $\IZ/11\IZ$
[/mm]
[mm] $\iff$ [/mm] $6x [mm] \equiv [/mm] 2$ [mm] $\mod [/mm] 11$
Es ist
[mm] $\ggT(6,11)=1$
[/mm]
und wegen
[mm] $1=\red{2}\,*6+(-1)*11\,$
[/mm]
ist die Ausgangsgleichung äquivalent zu
$x [mm] \equiv \red{2}\,*\frac{2}{1}$ $\mod \frac{11}{1}.$ [/mm]
Also
[mm] $\overline{6}\overline{x}=\overline{2}$ [/mm] in [mm] $\IZ/11\IZ$
[/mm]
[mm] $\iff$ $\overline{x}=\overline{\red{2}\,*2}=\overline{4}\,.$ [/mm] (in [mm] $\IZ/11\IZ$)
[/mm]
P.S. Ich schreibe eigentlich lieber etwa
[mm] ${^{11}\overline{4}}$ [/mm] statt [mm] $\overline{4}\,.$
[/mm]
Insbesondere, da man hier im Falle, dass der [mm] $\ggT(a,n)$ [/mm] mal nicht einfach [mm] $=1\,$
[/mm]
ist, die Lösungsmenge ja einfach als eine Restklasse eines anderen Restklassenrings
(nämlich [mm] $\IZ/(n/\ggT(a,n)\;\IZ)$) [/mm] geschrieben werden kann (im Falle der Lösbarkeit
der Kongruenz). Oben ist natürlich [mm] ${^{11/1}\overline{4}}={^{11}\overline{4}}$.
[/mm]
Andere schreiben etwa auch [mm] $[4]=[4]_{11}\,.$
[/mm]
P.P.S. $y,z [mm] \in \IZ$ [/mm] mit [mm] $y*a+z*n=\ggT(a,n)$ [/mm] findet man auch etwa mit dem erweiterten
euklidischen Algorithmus.
Gruß,
Marcel
|
|
|
| |
|
Danke...Übersteigt unseren Stoff, wir machen Algebraische Strukturen gerade und nicht Zahlentheorie. Daher habe ich die ganze Theorie zu ggT, Euklid.Alg., etc nicht "zur Verfügung"...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:22 Di 07.10.2014 | | Autor: | Marcel |
Hallo,
> Danke...Übersteigt unseren Stoff, wir machen Algebraische
> Strukturen gerade und nicht Zahlentheorie. Daher habe ich
> die ganze Theorie zu ggT, Euklid.Alg., etc nicht "zur
> Verfügung"...
das Buch empfehle ich trotzdem. (Es reicht ja, wenn Du es vielleicht in
Deiner Bibliothek sichtest - wobei ich mal ergänze: Du sollst es Dir dann
schon ruhig auch ausleihen).
Gruß,
Marcel
|
|
|
| |
|
...wobei du mit Ausleihen sicherlich meinst, auch mal reinzuschauen. Und mit Reinschauen ist sicherlich gemeint...
[mir hat mal einer erzählt, in Schach-Frustration: "Ich weiß auch nicht, warum ich so nen Mist spiele, ich schau doch ewig auf's Brett!" Was wohl mit "Schauen" gemeint war...]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:56 Di 07.10.2014 | | Autor: | Marcel |
Hallo,
> ...wobei du mit Ausleihen sicherlich meinst, auch mal
> reinzuschauen. Und mit Reinschauen ist sicherlich
> gemeint...
genau. 
> [mir hat mal einer erzählt, in Schach-Frustration: "Ich
> weiß auch nicht, warum ich so nen Mist spiele, ich schau
> doch ewig auf's Brett!" Was wohl mit "Schauen" gemeint
> war...]
Ich sagte mal zu meiner Freundin, dass sie auf die Ampel schauen
sollte (weil ich gerade etwas im Auto gesucht habe). Als dann die
anderen hinter mir angefangen hatten, zu hupen, sagte ich auch zu
ihr: "Sach' mal, Du sollst mir auch sagen, wenn sie grün wird..." ![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]")
Und sie nur so: "Achso... sowas musst Du mir doch sagen."
Ich: "Warum sage ich wohl sonst, dass Du auf die Ampel gucken sollst?
Weil die so schön ist?"
Sie: "Ja, das habe ich mich ja auch gefragt..."
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:52 Di 07.10.2014 | | Autor: | Marcel |
Hallo,
anbei ein Dokument:
Ich hatte mal die Formel für den erweiterten euklidischen Algorithmus *grob*
hergeleitet, denn ich kann sie mir nie merken. 
![[a]](/images/paperclip.gif "Dateianhänge") pdf: Herleitung der Formel für den erweiterten eukl. Alg.
Gruß,
Marcel
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
|
