www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAlgebraChinesischer Restsatz
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Algebra" - Chinesischer Restsatz
Chinesischer Restsatz < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Chinesischer Restsatz: Aufgabe
Status: (Frage) beantwortet Status 
Datum: 17:13 Do 08.01.2015
Autor: xx_xx_xx

Aufgabe
Bestimmen Sie alle Lösungen:

X [mm] \equiv [/mm] 1 (mod 5)
X [mm] \equiv [/mm] 5 (mod 6)
X [mm] \equiv [/mm] 8 (mod 15)

Hallo!

Also ich bin mir recht sicher, dass es nicht lösbar ist, bin mir aber nicht sicher warum bzw wie ich es begründe

X [mm] \equiv [/mm] 1 (mod 5)

X [mm] \equiv [/mm] 5 (mod 6)  [mm] \gdw [/mm]  X [mm] \equiv [/mm] 1 (mod 2)   [mm] \wedge [/mm]   X [mm] \equiv [/mm] 2 (mod 3)

X [mm] \equiv [/mm] 8 (mod 15)  [mm] \gdw [/mm]  X [mm] \equiv [/mm] 2 (mod 3)   [mm] \wedge [/mm]   X [mm] \equiv [/mm] 3 (mod 5)

Also:

X [mm] \equiv [/mm] 1 (mod 5)
X [mm] \equiv [/mm] 3 (mod 5)
X [mm] \equiv [/mm] 1 (mod 2)
X [mm] \equiv [/mm] 2 (mod 3)

Wie gehe ich jetzt weiter vor?

Danke!
VG

        
Bezug
Chinesischer Restsatz: Antwort
Status: (Antwort) fertig Status 
Datum: 17:31 Do 08.01.2015
Autor: Marcel

Hallo,

> Bestimmen Sie alle Lösungen:
>  
> X [mm]\equiv[/mm] 1 (mod 5)
>  X [mm]\equiv[/mm] 5 (mod 6)
>  X [mm]\equiv[/mm] 8 (mod 15)
>  Hallo!
>  
> Also ich bin mir recht sicher, dass es nicht lösbar ist,
> bin mir aber nicht sicher warum

das ist mal 'ne interessante Frage: Warum begründe ich das überhaupt? [grins]

> bzw wie ich es begründe
>  
> X [mm]\equiv[/mm] 1 (mod 5)
>  
> X [mm]\equiv[/mm] 5 (mod 6)  [mm]\gdw[/mm]  X [mm]\equiv[/mm] 1 (mod 2)   [mm]\wedge[/mm]   X
> [mm]\equiv[/mm] 2 (mod 3)
>  
> X [mm]\equiv[/mm] 8 (mod 15)  [mm]\gdw[/mm]  X [mm]\equiv[/mm] 2 (mod 3)   [mm]\wedge[/mm]   X
> [mm]\equiv[/mm] 3 (mod 5)
>  
> Also:
>  
> X [mm]\equiv[/mm] 1 (mod 5)
>  X [mm]\equiv[/mm] 3 (mod 5)
>  X [mm]\equiv[/mm] 1 (mod 2)
>  X [mm]\equiv[/mm] 2 (mod 3)
>  
> Wie gehe ich jetzt weiter vor?

Ich wäre das anders angegangen, aber ich benutze den Chinesischen
Restsatz auch in folgender Version:
Gegeben seien $a,b [mm] \in \IZ$ [/mm] und $n,m [mm] \in \IN.$ [/mm] Sei [mm] $d:=\ggT(n,m)$ [/mm] und $y,z [mm] \in \IZ$ [/mm] so,
dass [mm] $yn+zm=d=\ggT(n,m).$ [/mm] Die simultanen Kongruenzen

    $x [mm] \equiv [/mm] a [mm] \mod [/mm] n$ und $x [mm] \equiv [/mm] b [mm] \mod [/mm] m$

sind genau dann lösbar, wenn $a [mm] \equiv [/mm] b [mm] \mod [/mm] d$. Im Falle der Lösbarkeit ist
das System der simultanen Kongruenzen äquivalent zu

    $x [mm] \equiv [/mm] a - [mm] yn\frac{a-b}{d} \mod \frac{mn}{d}\,.$ [/mm]

(Satz 4.11 in "Elementare und algebraische Zahlentheorie, Müller-Stach, P.";
Chinesischer Restsatz, 1. Version!)

Schauen wir mal:

    $x [mm] \equiv [/mm] 1 [mm] \mod [/mm] 5$ und $x [mm] \equiv [/mm] 5 [mm] \mod [/mm] 6.$

Wende den Satz an (beachte [mm] $-1*5+1*6=1=\ggT(5,6)$), [/mm] und wir haben die
äquivalente Kongr. (beachte a=1, n=5, b=5, m=6 in obigem Satz; weiter y=-1, z=1)

    $x [mm] \equiv 1-(-1)*5*\frac{1-5}{1} \mod \frac{5*6}{1}$ [/mm]

    [mm] $\iff$ [/mm]

    $x [mm] \equiv [/mm] -19 [mm] \equiv [/mm] 11 [mm] \mod 30\,.$ [/mm]

Wir haben nun also das zum Ausgangssystem äquivalente System

    $x [mm] \equiv [/mm] 11 [mm] \mod [/mm] 30$ und $x [mm] \equiv [/mm] 8 [mm] \mod [/mm] 15$.

Jetzt haben wir, wenn wir "die alten Variablen löschen", den Satz also anzuwenden
für

    a=11, n=30, b=8 und m=15.

Wegen [mm] $\ggT(n,m)=\ggT(30,15)=15 \nmid [/mm] a-b=11-8=3$ ist dieses System simultaner
Kongrunzen nicht lösbar.

(Beachte: $r [mm] \equiv [/mm] s [mm] \mod \ell$ $\iff$ $\ell \mid [/mm] (r-s)$ [mm] $\iff$ $\ell \mid [/mm] (s-r).$)

P.S. Die $y,z [mm] \in \IZ$ [/mm] mit [mm] $\ggT(n,m)=d=yn+zm$ [/mm] findest Du i.A. etwa mit dem
erweiterten euklidischen Algorithmus!

Gruß,
  Marcel

Bezug
                
Bezug
Chinesischer Restsatz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:56 Do 08.01.2015
Autor: xx_xx_xx

Aufgabe
Bestimmen Sie die Lösungen:

X [mm] \equiv [/mm] 33 (mod 34)
2X [mm] \equiv [/mm] -3 (mod 5)
3X [mm] \equiv [/mm] 5 (mod 7)

Danke! Die erste Aufgabe habe ich verstanden!

Ich habe aber jetzt noch eine zweite Aufgabe und weiß hier leider nicht, was ich mit den Vorfaktoren 2 und 3 machen soll...
Ich habe nur eine Lösung für
X [mm] \equiv [/mm] 33 (mod 34)
X [mm] \equiv [/mm] -3 (mod 5)
X [mm] \equiv [/mm] 5 (mod 7)

[mm] \Rightarrow \IL={747 (mod 1190)} [/mm]
aber das bringt mir auch nichts, richtig?

Wäre super, wenn mir jemand helfen könnte...

Danke!
VG

Bezug
                        
Bezug
Chinesischer Restsatz: Antwort
Status: (Antwort) fertig Status 
Datum: 19:59 Do 08.01.2015
Autor: ms2008de

Hallo,
> Bestimmen Sie die Lösungen:
>  
> X [mm]\equiv[/mm] 33 (mod 34)
>  2X [mm]\equiv[/mm] -3 (mod 5)
>  3X [mm]\equiv[/mm] 5 (mod 7)
>  Danke! Die erste Aufgabe habe ich verstanden!
>  
> Ich habe aber jetzt noch eine zweite Aufgabe und weiß hier
> leider nicht, was ich mit den Vorfaktoren 2 und 3 machen
> soll...

Schreiben wir die letzten beiden Gleichungen doch mal um:
2X [mm]\equiv[/mm] -3 (mod 5)
[mm] \gdw \overline{2X} [/mm] = [mm] \overline{-3} \in \IZ_{5} [/mm]
[mm] \gdw \overline{2X} [/mm] = [mm] \overline{2} \in \IZ_{5} [/mm]
Nun multipilizieren mit dem Inversen zu [mm] \overline{2} \in \IZ_{5}, [/mm] also [mm] \overline{3}. [/mm] Das führt zu:
[mm] \gdw \overline{3*2X} [/mm] = [mm] \overline{3*2} \in \IZ_{5} [/mm]
[mm] \gdw \overline{6X} [/mm] = [mm] \overline{6} \in \IZ_{5} [/mm]
[mm] \gdw \overline{X} [/mm] = [mm] \overline{1} \in \IZ_{5} [/mm]
[mm] \gdw [/mm] X [mm]\equiv[/mm] 1 (mod 5)
Analog  ist:
3X [mm]\equiv[/mm] 5 (mod 7)
[mm] \gdw \overline{3X} [/mm] = [mm] \overline{5} \in \IZ_{7} [/mm]
Mit dem Inversen zu [mm] \overline{3} \in \IZ_{7} [/mm] multiplizieren, also [mm] \overline{5}, [/mm] führt zu:
[mm] \gdw \overline{5*3X} [/mm] = [mm] \overline{5*5} \in \IZ_{7} [/mm]
[mm] \gdw \overline{15X} [/mm] = [mm] \overline{25} \in \IZ_{7} [/mm]
[mm] \gdw \overline{X} [/mm] = [mm] \overline{4} \in \IZ_{7} [/mm]
[mm] \gdw [/mm] X [mm]\equiv[/mm] 4 (mod 7).

Nun musst nur noch das Kongruenzgleichungssystem lösen:
X [mm]\equiv[/mm] 33 (mod 34)
X [mm]\equiv[/mm] 1 (mod 5)
X [mm]\equiv[/mm] 4 (mod 7)

Viele Grüße

Bezug
                                
Bezug
Chinesischer Restsatz: Danke
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:26 Do 08.01.2015
Autor: xx_xx_xx

Toll!
Vielen, vielen Dank!

Bezug
                        
Bezug
Chinesischer Restsatz: Antwort
Status: (Antwort) fertig Status 
Datum: 21:45 Do 08.01.2015
Autor: Marcel

Hallo,

> Bestimmen Sie die Lösungen:
>  
> X [mm]\equiv[/mm] 33 (mod 34)
>  2X [mm]\equiv[/mm] -3 (mod 5)
>  3X [mm]\equiv[/mm] 5 (mod 7)
>  Danke! Die erste Aufgabe habe ich verstanden!
>  
> Ich habe aber jetzt noch eine zweite Aufgabe und weiß hier
> leider nicht, was ich mit den Vorfaktoren 2 und 3 machen
> soll...

neben dem Gesagten gibt es auch hier wieder einen Satz aus dem Buch
"Elementare und algebraische Zahlentheorie". (Satz 4.8)

Die Kongruenz

    $ax [mm] \equiv [/mm] b [mm] \mod [/mm] n$ mit $a,b [mm] \in \IZ$ [/mm] und $n [mm] \in \IN$ [/mm]

ist genau dann lösbar, wenn mit [mm] $d:=\ggT(a,n)$ [/mm] gilt $d [mm] \mid b\,.$ [/mm] Im Falle der Lösbarkeit
ist sie gleichwertig zu

    $x [mm] \equiv [/mm] y [mm] \frac{b}{d} \mod \frac{n}{d}\,,$ [/mm]

wobei $y,z [mm] \in \IZ$ [/mm] mit [mm] $d=\ggT(a,n)=ya+zn\,.$ [/mm]

Gruß,
  Marcel

Bezug
        
Bezug
Chinesischer Restsatz: Antwort
Status: (Antwort) fertig Status 
Datum: 17:41 Do 08.01.2015
Autor: ms2008de

Hallo,
> Bestimmen Sie alle Lösungen:
>  
> X [mm]\equiv[/mm] 1 (mod 5)
>  X [mm]\equiv[/mm] 5 (mod 6)
>  X [mm]\equiv[/mm] 8 (mod 15)
>  Hallo!
>  
> Also ich bin mir recht sicher, dass es nicht lösbar ist,
> bin mir aber nicht sicher warum bzw wie ich es begründe
>  
> X [mm]\equiv[/mm] 1 (mod 5)
>  
> X [mm]\equiv[/mm] 5 (mod 6)  [mm]\gdw[/mm]  X [mm]\equiv[/mm] 1 (mod 2)   [mm]\wedge[/mm]   X
> [mm]\equiv[/mm] 2 (mod 3)
>  
> X [mm]\equiv[/mm] 8 (mod 15)  [mm]\gdw[/mm]  X [mm]\equiv[/mm] 2 (mod 3)   [mm]\wedge[/mm]   X
> [mm]\equiv[/mm] 3 (mod 5)
>  
> Also:
>  
> X [mm]\equiv[/mm] 1 (mod 5)
>  X [mm]\equiv[/mm] 3 (mod 5)
>  X [mm]\equiv[/mm] 1 (mod 2)
>  X [mm]\equiv[/mm] 2 (mod 3)
>  

Naja, wie kann eine Zahl denn gleichzeitig 1(mod 5) und 3 (mod 5) sein...? Geht nicht, denn Sie kann nur eins von beidem sein!

Viele Grüße


Bezug
                
Bezug
Chinesischer Restsatz: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:48 Do 08.01.2015
Autor: Marcel

Hallo,

> Hallo,
>  > Bestimmen Sie alle Lösungen:

>  >  
> > X [mm]\equiv[/mm] 1 (mod 5)
>  >  X [mm]\equiv[/mm] 5 (mod 6)
>  >  X [mm]\equiv[/mm] 8 (mod 15)
>  >  Hallo!
>  >  
> > Also ich bin mir recht sicher, dass es nicht lösbar ist,
> > bin mir aber nicht sicher warum bzw wie ich es begründe
>  >  
> > X [mm]\equiv[/mm] 1 (mod 5)
>  >  
> > X [mm]\equiv[/mm] 5 (mod 6)  [mm]\gdw[/mm]  X [mm]\equiv[/mm] 1 (mod 2)   [mm]\wedge[/mm]   X
> > [mm]\equiv[/mm] 2 (mod 3)
>  >  
> > X [mm]\equiv[/mm] 8 (mod 15)  [mm]\gdw[/mm]  X [mm]\equiv[/mm] 2 (mod 3)   [mm]\wedge[/mm]   X
> > [mm]\equiv[/mm] 3 (mod 5)
>  >  
> > Also:
>  >  
> > X [mm]\equiv[/mm] 1 (mod 5)
>  >  X [mm]\equiv[/mm] 3 (mod 5)
>  >  X [mm]\equiv[/mm] 1 (mod 2)
>  >  X [mm]\equiv[/mm] 2 (mod 3)
>  >  
> Naja, wie kann eine Zahl denn gleichzeitig 1(mod 5) und 3
> (mod 5) sein...? Geht nicht, denn Sie kann nur eins von
> beidem sein!

das ist natürlich auch eine gute Begründung (anders gesagt:

    [mm] $[1]_5 \not= [3]_5$). [/mm]

Gruß,
  Marcel

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]