www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Gruppe, Ring, Körper" - Rechnen mit Restklassen
Rechnen mit Restklassen < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rechnen mit Restklassen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:10 Di 07.10.2014
Autor: geigenzaehler

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.

        
Bezug
Rechnen mit Restklassen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Rechnen mit Restklassen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:47 Di 07.10.2014
Autor: 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?





Bezug
                        
Bezug
Rechnen mit Restklassen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:09 Di 07.10.2014
Autor: MathePower

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

Bezug
                                
Bezug
Rechnen mit Restklassen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:02 Di 07.10.2014
Autor: 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]

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.

Bezug
                                        
Bezug
Rechnen mit Restklassen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:21 Di 07.10.2014
Autor: MathePower

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]


> 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

Bezug
                                                
Bezug
Rechnen mit Restklassen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:52 Di 07.10.2014
Autor: geigenzaehler

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.

Bezug
                                                        
Bezug
Rechnen mit Restklassen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                
Bezug
Rechnen mit Restklassen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:13 Di 07.10.2014
Autor: geigenzaehler

Das ist natürlich herrlich schlüssig. Danke!

Bezug
                        
Bezug
Rechnen mit Restklassen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
        
Bezug
Rechnen mit Restklassen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Rechnen mit Restklassen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:16 Di 07.10.2014
Autor: geigenzaehler

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"...

Bezug
                        
Bezug
Rechnen mit Restklassen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                
Bezug
Rechnen mit Restklassen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:53 Di 07.10.2014
Autor: geigenzaehler

...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...]

Bezug
                                        
Bezug
Rechnen mit Restklassen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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]

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

Bezug
        
Bezug
Rechnen mit Restklassen: Formel des erweiterten ggT
Status: (Mitteilung) Reaktion unnötig Status 
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]pdf: Herleitung der Formel für den erweiterten eukl. Alg.

Gruß,
  Marcel

Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]