Forum "Zahlentheorie" - Chinesischer Restesatz - MatheForum.net

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

Mathe

Numerik

Schule

Derive

DynaGeo

FunkyPlot

GeoGebra

LaTeX

Maple

MathCad

Mathematica

Matlab

Maxima

MuPad

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:

Vorhilfe.de

FunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme

Startseite > MatheForen > Zahlentheorie > Chinesischer Restesatz

Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik

Forum "Zahlentheorie" - Chinesischer Restesatz

Chinesischer Restesatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe

Ansicht:

[ geschachtelt ]

Forum "Zahlentheorie" |

Alle Foren |

Forenbaum | Materialien

Chinesischer Restesatz: Aufgabe

Status:	(Frage) reagiert/warte auf Reaktion
Datum:	10:00 Sa 14.05.2011
Autor:	jesi0001

Aufgabe

 Drei Bauern teilen sich den Reis den Sie angebaut haben. Einer geht zu eine Markut wo ein 83 Pfund Gewicht verwendet wird, einer zu einem Markt, bei dem ein 110 Pfund Gewicht verwendet wird und der Dritte zu einem Markt wo ein 135 Pfund Gewicht verwendet wird. 

Rest als Sie nach hause kommen der 1. 32 Pfund der 2. 70 Pfund und der 3. 30 Pfund übrig. 

Wieviel Reis haben Sie zu den Märkten gebracht?

Ich habe folgendermaßen angefangen die Gleichungen zu erstellen:

1. Bauer: Einheit 83 Pfund Rest 32 Pfund
2. Bauer: Einheit 110 Pfund Rest 70 Pfund
3. Bauer: Einheit 135 Pfund Rest 30 Pfund

x = 83 mod 32   wobei b1 = 83 m1 = 32
x = 110 mod 70  wobei b2 = 110 m2 = 70
x = 135 mod 30  wobei b3 = 135 m3 = 30

m = m1 * m2 * m3 = 32 * 70 * 30 = 67200

a1 = m / m1 = 67200 / 32 = 2100
a2 = m / m2 = 67200 / 70 = 960
a3 = m / m3 = 67200 / 30 = 2240

Jetzt habe ich wollen alle ri mit ai * ri  [mm] \equiv [/mm] bi (mod mi)

also in meiner Aufgabe:

a1 * r1 [mm] \equiv [/mm] b1 mod m1    [mm] \hat= [/mm]  2100 * r1 [mm] \equiv [/mm] 83 mod 32
a2 * r2 [mm] \equiv [/mm] b2 mod m2    [mm] \hat= [/mm]  960 * r2 [mm] \equiv [/mm] 110 mod 70
a3 * r3 [mm] \equiv [/mm] b3 mod m3    [mm] \hat= [/mm]  2240 * r3 [mm] \equiv [/mm] 135 mod 30

so und ab hier stehe ich gerade auf dem Schlauch, die Zahlen sind zu groß für einfach mal zu raten. ich wollte dann r1 und r2 über den Eulidschen Alg berechnen aber irgendwie scheitere ich gerade. hier einmal mein Ansatz.

x = 83 mod 32          x = 110 mod 70
ggt (70, 32)
70 = 2 * 32 + 6
32 = 5 * 6 + 2
6 = 3 * 2 + 0
fertig jetzt das ganze Rückwärts damit man r1 und r2 raus bekommt.
An dem folgenden Beispiel habe ich mich orientiert.

geg: x = 5 (mod 17) und x= 8 (mod 29) führt zu:

ggT (29,17) : 29 = 1* 17 + 12
17 = 1*12 + 5
12 = 2*5 + 2
5 = 2*2 + 1
2 = 1*2 + 0

rückwärts r1 und r2 finden:
1 = 5 - 2*2
1 = 5 - 2*(12 - 2*5) = 5*5 - 2*12 in dieser Zeile den 2. Schritt also 5*5 - 2*12 verstehe ich schon nicht mehr.
1 = 5*(17 - 1*12) - 2*12 = 5*17 - 7*12
1 = 5*17 - 7*(29-1*17) = 12*17 - 7*29
also: r1 (zu 17) = 12 und r2 (zu 29) = -7

kann mir das bitte jemand erklären wie man darauf kommt. Und kann mir auch jmd sagen ob der Anfang von meiner Aufgabe richtig ist. Dann muss ich eigentlich ja nur noch r1, r2, r3 rausbekommen und das zusammen zählen oder ?

schonmal im Voraus vielen Dank für eure Hilfe

Gruß Jenny

Bezug

Chinesischer Restesatz: Antwort

Status:	(Antwort) fertig
Datum:	10:56 Sa 14.05.2011
Autor:	Al-Chwarizmi

> Drei Bauern teilen sich den Reis den Sie angebaut haben.
> Einer geht zu eine Markut wo ein 83 Pfund Gewicht verwendet
> wird, einer zu einem Markt, bei dem ein 110 Pfund Gewicht
> verwendet wird und der Dritte zu einem Markt wo ein 135
> Pfund Gewicht verwendet wird.
> Rest als Sie nach hause kommen der 1. 32 Pfund der 2. 70
> Pfund und der 3. 30 Pfund übrig.
>
> Wieviel Reis haben Sie zu den Märkten gebracht?

Eine vollständige Aufgabenstellung findet man da:

http://docs.google.com/viewer?a=v&q=cache:Eo4Y-jz97iEJ:www8.informatik.uni-erlangen.de/IMMD8/Lectures/THINF3/Uebungen08/u9ws0708.pdf+Drei+Bauern+teilen+sich+den+Reis&hl=de&gl=ch&pid=bl&srcid=ADGEESjYpIQaDtjfh0-NWrROSnWVGjCqeTC4uCsat_cntJcbrKnfp-rsp1YxABo2WQSDZT_ESnyAzlHFeOrT6OrjyJuhUqPEILQUO4XtseiObzHRLRSGj1MurNg9j2DBlhFxgj2-OTY2&sig=AHIEtbTw3OoAj4k3Yt1CnEio-6JxsxPXJA

(ich frage mich zwar, ob derartige Monster-Urls wirklich
nötig sind ...)

> Ich habe folgendermaßen angefangen die Gleichungen zu
> erstellen:
>
> 1. Bauer: Einheit 83 Pfund Rest 32 Pfund
> 2. Bauer: Einheit 110 Pfund Rest 70 Pfund
> 3. Bauer: Einheit 135 Pfund Rest 30 Pfund
>
> x = 83 mod 32 wobei b1 = 83 m1 = 32

> x = 110 mod 70 wobei b2 = 110 m2 = 70

> x = 135 mod 30 wobei b3 = 135 m3 = 30

das notierst du so ziemlich verkehrt ...

> m = m1 * m2 * m3 = 32 * 70 * 30 = 67200

Ich verstehe nicht, weshalb du die Reste multiplizierst.

LG   Al-Chw.

> a1 = m / m1 = 67200 / 32 = 2100
> a2 = m / m2 = 67200 / 70 = 960
> a3 = m / m3 = 67200 / 30 = 2240
>
> Jetzt habe ich wollen alle ri mit ai * ri  [mm]\equiv[/mm] bi (mod
> mi)
>
> also in meiner Aufgabe:
>
> a1 * r1 [mm]\equiv[/mm] b1 mod m1    [mm]\hat=[/mm]  2100 * r1 [mm]\equiv[/mm] 83 mod
> 32
>  a2 * r2 [mm]\equiv[/mm] b2 mod m2    [mm]\hat=[/mm]  960 * r2 [mm]\equiv[/mm] 110 mod
> 70
> a3 * r3 [mm]\equiv[/mm] b3 mod m3    [mm]\hat=[/mm]  2240 * r3 [mm]\equiv[/mm] 135 mod
> 30
>
> so und ab hier stehe ich gerade auf dem Schlauch, die
> Zahlen sind zu groß für einfach mal zu raten. ich wollte
> dann r1 und r2 über den Eulidschen Alg berechnen aber
> irgendwie scheitere ich gerade. hier einmal mein Ansatz.
>
> x = 83 mod 32          x = 110 mod 70
> ggt (70, 32)
> 70 = 2 * 32 + 6
>  32 = 5 * 6 + 2
>  6 = 3 * 2 + 0
> fertig jetzt das ganze Rückwärts damit man r1 und r2 raus
> bekommt.
> An dem folgenden Beispiel habe ich mich orientiert.
>
> geg: x = 5 (mod 17) und x= 8 (mod 29) führt zu:
>
> ggT (29,17) : 29 = 1* 17 + 12
> 17 = 1*12 + 5
> 12 = 2*5 + 2
> 5 = 2*2 + 1
> 2 = 1*2 + 0
>
> rückwärts r1 und r2 finden:
> 1 = 5 - 2*2
>  1 = 5 - 2*(12 - 2*5) = 5*5 - 2*12 in dieser Zeile den 2.
> Schritt also 5*5 - 2*12 verstehe ich schon nicht mehr.
> 1 = 5*(17 - 1*12) - 2*12 = 5*17 - 7*12
>  1 = 5*17 - 7*(29-1*17) = 12*17 - 7*29
>  also: r1 (zu 17) = 12 und r2 (zu 29) = -7
>
> kann mir das bitte jemand erklären wie man darauf kommt.
> Und kann mir auch jmd sagen ob der Anfang von meiner
> Aufgabe richtig ist. Dann muss ich eigentlich ja nur noch
> r1, r2, r3 rausbekommen und das zusammen zählen oder ?
>
> schonmal im Voraus vielen Dank für eure Hilfe
>
> Gruß Jenny

Bezug

Chinesischer Restesatz: Rückfrage

Status:	(Frage) beantwortet
Datum:	13:27 So 15.05.2011
Autor:	jesi0001

> Eine vollständige Aufgabenstellung findet man da:
>
> http://docs.google.com/viewer?a=v&q=cache:Eo4Y-jz97iEJ:www8.informatik.uni-erlangen.de/IMMD8/Lectures/THINF3/Uebungen08/u9ws0708.pdf+Drei+Bauern+teilen+sich+den+Reis&hl=de&gl=ch&pid=bl&srcid=ADGEESjYpIQaDtjfh0-NWrROSnWVGjCqeTC4uCsat_cntJcbrKnfp-rsp1YxABo2WQSDZT_ESnyAzlHFeOrT6OrjyJuhUqPEILQUO4XtseiObzHRLRSGj1MurNg9j2DBlhFxgj2-OTY2&sig=AHIEtbTw3OoAj4k3Yt1CnEio-6JxsxPXJA
>
> (ich frage mich zwar, ob derartige Monster-Urls wirklich
>  nötig sind ...)

Ich glaube das ist unrelevant ich denke ich habe alle wichtigen Informationen für diese Aufgabe preisgegebn.

> >  Ich habe folgendermaßen angefangen die Gleichungen zu

> > erstellen:
> >
> > 1. Bauer: Einheit 83 Pfund Rest 32 Pfund
> > 2. Bauer: Einheit 110 Pfund Rest 70 Pfund
> > 3. Bauer: Einheit 135 Pfund Rest 30 Pfund
> >
> > x = 83 mod 32   wobei b1 = 83 m1 = 32

> > x = 110 mod 70 wobei b2 = 110 m2 = 70

> > x = 135 mod 30 wobei b3 = 135 m3 = 30

>

> das notierst du so ziemlich verkehrt ...

warum ist das denn jetzt verkerht ?
ich habe versucht es nach folgendem Muster zu lösen, warum ist das denn falsch ?

http://www.mpipks-dresden.mpg.de/~mueller/download/old_uni/mathe/ChinesischerRestsatzUeb33-v4.pdf

Deswegen habe ich auch die Reste multipliziert. Kannst du mir denn einen einfacherern Lösungsweg vorschlagen.

Gruß Jenny
> > m = m1 * m2 * m3 = 32 * 70 * 30 = 67200
>
> Ich verstehe nicht, weshalb du die Reste multiplizierst.
>
> LG   Al-Chw.
>
>
> > a1 = m / m1 = 67200 / 32 = 2100
> > a2 = m / m2 = 67200 / 70 = 960
> > a3 = m / m3 = 67200 / 30 = 2240
> >
> > Jetzt habe ich wollen alle ri mit ai * ri  [mm]\equiv[/mm] bi (mod
> > mi)
> >
> > also in meiner Aufgabe:
> >
> > a1 * r1 [mm]\equiv[/mm] b1 mod m1    [mm]\hat=[/mm]  2100 * r1 [mm]\equiv[/mm] 83 mod
> > 32
>  >  a2 * r2 [mm]\equiv[/mm] b2 mod m2    [mm]\hat=[/mm]  960 * r2 [mm]\equiv[/mm] 110
> mod
> > 70
> > a3 * r3 [mm]\equiv[/mm] b3 mod m3    [mm]\hat=[/mm]  2240 * r3 [mm]\equiv[/mm] 135 mod
> > 30
> >
> > so und ab hier stehe ich gerade auf dem Schlauch, die
> > Zahlen sind zu groß für einfach mal zu raten. ich wollte
> > dann r1 und r2 über den Eulidschen Alg berechnen aber
> > irgendwie scheitere ich gerade. hier einmal mein Ansatz.
> >
> > x = 83 mod 32          x = 110 mod 70
> > ggt (70, 32)
> > 70 = 2 * 32 + 6
>  >  32 = 5 * 6 + 2
>  >  6 = 3 * 2 + 0
> > fertig jetzt das ganze Rückwärts damit man r1 und r2 raus
> > bekommt.
> > An dem folgenden Beispiel habe ich mich orientiert.
> >
> > geg: x = 5 (mod 17) und x= 8 (mod 29) führt zu:
>  >
> > ggT (29,17) : 29 = 1* 17 + 12
> > 17 = 1*12 + 5
> > 12 = 2*5 + 2
> > 5 = 2*2 + 1
> > 2 = 1*2 + 0
> >
> > rückwärts r1 und r2 finden:
> > 1 = 5 - 2*2
>  >  1 = 5 - 2*(12 - 2*5) = 5*5 - 2*12 in dieser Zeile den
> 2.
> > Schritt also 5*5 - 2*12 verstehe ich schon nicht mehr.
> > 1 = 5*(17 - 1*12) - 2*12 = 5*17 - 7*12
>  >  1 = 5*17 - 7*(29-1*17) = 12*17 - 7*29
>  >  also: r1 (zu 17) = 12 und r2 (zu 29) = -7
>  >
> > kann mir das bitte jemand erklären wie man darauf kommt.
> > Und kann mir auch jmd sagen ob der Anfang von meiner
> > Aufgabe richtig ist. Dann muss ich eigentlich ja nur noch
> > r1, r2, r3 rausbekommen und das zusammen zählen oder ?
> >
> > schonmal im Voraus vielen Dank für eure Hilfe
> >
> > Gruß Jenny
>

Bezug

Chinesischer Restesatz: Antwort

Status:	(Antwort) fertig
Datum:	13:54 So 15.05.2011
Autor:	felixf

Moin!

> > Eine vollständige Aufgabenstellung findet man da:
>  >
> >
> http://docs.google.com/viewer?a=v&q=cache:Eo4Y-jz97iEJ:www8.informatik.uni-erlangen.de/IMMD8/Lectures/THINF3/Uebungen08/u9ws0708.pdf+Drei+Bauern+teilen+sich+den+Reis&hl=de&gl=ch&pid=bl&srcid=ADGEESjYpIQaDtjfh0-NWrROSnWVGjCqeTC4uCsat_cntJcbrKnfp-rsp1YxABo2WQSDZT_ESnyAzlHFeOrT6OrjyJuhUqPEILQUO4XtseiObzHRLRSGj1MurNg9j2DBlhFxgj2-OTY2&sig=AHIEtbTw3OoAj4k3Yt1CnEio-6JxsxPXJA
>  >
> > (ich frage mich zwar, ob derartige Monster-Urls wirklich
>  >  nötig sind ...)
>
> Ich glaube das ist unrelevant ich denke ich habe alle
> wichtigen Informationen für diese Aufgabe preisgegebn.

Die wichtigen Zahlen stehen da schon drin. Es war allerdings nicht wirklich verstaendlich.

> > >  Ich habe folgendermaßen angefangen die Gleichungen zu

> > > erstellen:
> > >
> > > 1. Bauer: Einheit 83 Pfund Rest 32 Pfund
> > > 2. Bauer: Einheit 110 Pfund Rest 70 Pfund
> > > 3. Bauer: Einheit 135 Pfund Rest 30 Pfund
> > >
> > > x = 83 mod 32   wobei b1 = 83 m1 = 32

> > > x = 110 mod 70 wobei b2 = 110 m2 = 70

> > > x = 135 mod 30 wobei b3 = 135 m3 = 30

> >
>
> > das notierst du so ziemlich verkehrt ...
>
> warum ist das denn jetzt verkerht ?

Du vertauschst die [mm] $b_i$s [/mm] mit den [mm] $m_i$s. [/mm]

Der Modulus bei der ersten Gleichung ist 83, der Rest ist 32. Also ist [mm] $b_1 [/mm] = 32$, [mm] $m_1 [/mm] = 83$.

LG Felix

Bezug

Chinesischer Restesatz: Antwort

Status:	(Antwort) fertig
Datum:	15:53 So 15.05.2011
Autor:	Al-Chwarizmi

> ich habe versucht es nach folgendem Muster zu lösen, warum
> ist das denn falsch ?
>
> http://www.mpipks-dresden.mpg.de/~mueller/download/old_uni/mathe/ChinesischerRestsatzUeb33-v4.pdf

Hallo Jenny,

in diesem Dokument wird nur der Fall behandelt, wo die
verschiedenen Moduli paarweise teilerfremd sind. Dies
ist aber in der vorliegenden Aufgabe nicht der Fall, weil
110 und 135 beide durch 5 teilbar sind.
Nun kann man aber aus den beiden Kongruenzen

$\ [mm] x\equiv{70}\quad(\,mod\ 110\,)$ [/mm] und $\ [mm] x\equiv{30}\quad(\,mod\ 135\,)$ [/mm]

(sofern sie überhaupt simultan lösbar sind)

nach

Lösen simultaner Kongruenzen  eine einzige machen.
edit: sorry, hier stand zuerst ein falscher Link ...
Durch Anwendung des dort angegebenen Rezepts bin
ich auf

    $\ [mm] x\equiv{840}\quad(\,mod\ 2970\,)$ [/mm]

gekommen. In einem weiteren Schritt kann man nun
diese Kongruenz zusammen mit

    $\ [mm] x\equiv{32}\quad(\,mod\ 83\,)$ [/mm]

betrachten. In diesem Fall sind die Moduli teilerfremd
und man kann den Restsatz in seiner normalen Form
anwenden.

LG    Al-Chw.

Bezug

Chinesischer Restesatz: Mitteilung

Status:	(Mitteilung) Reaktion unnötig
Datum:	13:59 So 15.05.2011
Autor:	felixf

Moin,

> http://docs.google.com/viewer?a=v&q=cache:Eo4Y-jz97iEJ:www8.informatik.uni-erlangen.de/IMMD8/Lectures/THINF3/Uebungen08/u9ws0708.pdf+Drei+Bauern+teilen+sich+den+Reis&hl=de&gl=ch&pid=bl&srcid=ADGEESjYpIQaDtjfh0-NWrROSnWVGjCqeTC4uCsat_cntJcbrKnfp-rsp1YxABo2WQSDZT_ESnyAzlHFeOrT6OrjyJuhUqPEILQUO4XtseiObzHRLRSGj1MurNg9j2DBlhFxgj2-OTY2&sig=AHIEtbTw3OoAj4k3Yt1CnEio-6JxsxPXJA
>
> (ich frage mich zwar, ob derartige Monster-Urls wirklich
> nötig sind ...)

wenn du nicht auf die PDF-Datei verlinkst, sondern auf den Google-Docs-Viewer der die PDF anzeigen soll, dann schon. :) Google moechte die ganzen Informationen nicht selber speichern (wer weiss ob die nochmal benoetigt werden), deshalb werden die in die URL gepackt.

LG Felix

Bezug

Chinesischer Restesatz: Mitteilung

Status:	(Mitteilung) Reaktion unnötig
Datum:	16:22 Mo 16.05.2011
Autor:	jesi0001

Hey ihr zwei,

vielen lieben Dank für eure Hilfe und Geduld. Ich hab mit diesem Teil echt sehr große Schwierigkeiten.
Bei dieser Aufgabe habe ich ja schon am Anfang direkt die Fehler mit dem Vertauschen gemacht. Danke für eure Mühe.

Ich werde versuchen meine nächsten Aufgaben besser vorzubereiten, es fällt mir nur sehr schwer ich lese das Skript 4-5 mal und verstehe einfach nix.

Gruß Jenny

Bezug

Chinesischer Restesatz: Mitteilung

Status:	(Mitteilung) Reaktion unnötig
Datum:	16:25 Mo 16.05.2011
Autor:	jesi0001

Bezug

Chinesischer Restesatz: Mitteilung

Status:	(Mitteilung) Reaktion unnötig
Datum:	16:56 Mo 16.05.2011
Autor:	felixf

Moin Jenny,

> vielen lieben Dank für eure Hilfe und Geduld. Ich hab mit
> diesem Teil echt sehr große Schwierigkeiten.
> Bei dieser Aufgabe habe ich ja schon am Anfang direkt die
> Fehler mit dem Vertauschen gemacht. Danke für eure Mühe.

bitte!

> Ich werde versuchen meine nächsten Aufgaben besser
> vorzubereiten, es fällt mir nur sehr schwer ich lese das
> Skript 4-5 mal und verstehe einfach nix.

Das Thema ist auch nicht so einfach. Es ist allerdings auch nicht so schlimm, wie es auf den ersten Blick aussieht. Es dauert aber normalerweise eine gewisse Zeit, bis man das einsieht :-)

LG Felix

Bezug

Ansicht:

[ geschachtelt ]

Forum "Zahlentheorie" |

Alle Foren |

Forenbaum | Materialien