Chinesicher Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:09 Mo 08.09.2014 | | Autor: | schnoele |
| Aufgabe | Bestimmen Sie die größte negative und kleinste positive Lösung des folgenden Gleichungssystems
simultaner Kongruenzen für c = -1.
x [mm] \equiv [/mm] c + 4 mod 21
x [mm] \equiv [/mm] 4c mod 35 |
Hallo!
Kann ich hier bei dieser Aufgabenstellung das c+4 als 3 zusammenfassen? Oder wie ist das hier zu verstehen?
Wenn ja ist -4 [mm] \equiv [/mm] 35 = 31 [mm] \equiv [/mm] 35?
Danke!!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:30 Mo 08.09.2014 | | Autor: | Teufel |
Hi!
Sehr unsauber aufgeschrieben, aber ich denke, dass du das richtige meinst.
Ja, $(-1)+4=3=24=-18=...$ in [mm] $\IZ_{21}$ [/mm] und $-4=31$ in [mm] \IZ_{35} [/mm] zum Beispiel.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:14 Mo 08.09.2014 | | Autor: | schnoele |
Danke für deine Antwort!
Ich hab jetzt aber noch eine Frage. Um das zu berechnen muss ich ja folgende kongruenzen lösen:
35 [mm] x_{1} \equiv [/mm] 1 mod 21
[mm] 21x_{2} \equiv [/mm] 1 mod 35
Gibt es da ein Trick um schnell auf eine Lösung zu kommen?
Ich habe beim ersten erstmal die 35 mod 21= 14 gerechnet, um jetzt mit einer kleineren Zahl weiter rechnen zu können.
Aber irgendwie finde ich gerade keine Zahl, welches die Bedingung erfüllt. Da stehe ich gerade auf dem Schlauch
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:58 Mo 08.09.2014 | | Autor: | Marcel |
Hallo,
> Danke für deine Antwort!
> Ich hab jetzt aber noch eine Frage. Um das zu berechnen
> muss ich ja folgende kongruenzen lösen:
> 35 [mm]x_{1} \equiv[/mm] 1 mod 21
> [mm]21x_{2} \equiv[/mm] 1 mod 35
wie kommst Du darauf? Es war doch
$x [mm] \equiv [/mm] 3 [mm] \mod [/mm] 21$
und
$x [mm] \equiv [/mm] 31 [mm] \mod [/mm] 35$
> Gibt es da ein Trick um schnell auf eine Lösung zu
> kommen?
> Ich habe beim ersten erstmal die 35 mod 21= 14 gerechnet,
Es gibt übrigens einen Unterschied zwischen
$a [mm] \equiv [/mm] b [mm] \mod [/mm] n$
und
$a [mm] \textbf{ \red{=} } [/mm] b [mm] \mod n\,.$
[/mm]
Im zweiten Falle ist [mm] $a\,$ [/mm] ein spezieller Repräsentant von [mm] $[b]_n\,,$ [/mm] etwa:
[mm] $a=b-\lfloor b/n\rfloor*n\,,$
[/mm]
vergleiche ![[]](/images/popup.gif) Wiki: Modulo.
> um jetzt mit einer kleineren Zahl weiter rechnen zu
> können.
> Aber irgendwie finde ich gerade keine Zahl, welches die
> Bedingung erfüllt. Da stehe ich gerade auf dem Schlauch
Wie habt ihr denn den chinesischen Restsatz kennengelernt?
Müller-Stach, Piontkowski: Elementare und algebraische Zahlentheorie, Satz 4.11
1. Test: Es ist offenbar
[mm] $d:=\ggT(21,35)=7\,.$
[/mm]
Gilt nun
$3-31 [mm] \equiv [/mm] 0$ [mm] $\mod$ [/mm] $7$?
Ja, denn es ist [mm] $-4*7=-28\,.$ [/mm] Die simultane Kongruenz ist also lösbar!
2. Wende den (erweiterten) euklidischen Algorithmus an, um in der Darstellung
[mm] $7=d=y*21+z*35\,$
[/mm]
die Faktoren $y,z [mm] \in \IZ$ ($y\,$ [/mm] reicht!) zu berechnen (auch, wenn man hier
mit Probieren zum Ziel käme - Tipp: es wird [mm] $z=-1\,$ [/mm] sein, und dann kannst
Du mit diesem Tipp auch [mm] $y\,$ [/mm] berechnen!). Laut des aus dem Buch
zitierten Satzes folgt, dass das obige System der zwei Kongruenzen zu
folgender einzelner Kongruenz äquivalent ist:
$x [mm] \equiv 3-y*21*\frac{3-31}{7} \mod \frac{21*35}{7}\,.$
[/mm]
Tipp zur Lösung: $x [mm] \equiv [/mm] 66$ [mm] $\mod$ [/mm] ...?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:20 Mo 08.09.2014 | | Autor: | schnoele |
Meine Überlegungen:
b:= [mm] \summe_{i=1}^{n}aj*yj*Nj
[/mm]
Gesucht y1,y2 [mm] \in \IZ [/mm] yi Ni [mm] \equiv [/mm] 1 (mod mi)
[mm] x\equiv [/mm] 3 (mod 21)
[mm] x\equiv-4 \equiv [/mm] 31 (mod 35)
m1= 21 m2= 35
N1= 35 N2= 21 und N =735
soweit so gut.
1 [mm] \equiv y1*N1\equivy*35 \equiv14 [/mm] y1 (mod 21 ) und
1 [mm] \equiv [/mm] y2 *N2 [mm] \equiv [/mm] *21(mod 35)
richtig? wenn ja wie komm ich jetzt auf das y1 und das y2? Welche methode ist da die beste?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:34 Mo 08.09.2014 | | Autor: | Marcel |
Hallo,
> Meine Überlegungen:
> b:= [mm]\summe_{i=1}^{n}aj*yj*Nj[/mm]
>
> Gesucht y1,y2 [mm]\in \IZ[/mm] yi Ni [mm]\equiv[/mm] 1 (mod mi)
> [mm]x\equiv[/mm] 3 (mod 21)
> [mm]x\equiv-4 \equiv[/mm] 31 (mod 35)
> m1= 21 m2= 35
> N1= 35 N2= 21 und N =735
> soweit so gut.
> 1 [mm]\equiv y1*N1\equivy*35 \equiv14[/mm] y1 (mod 21 ) und
> 1 [mm]\equiv[/mm] y2 *N2 [mm]\equiv[/mm] *21(mod 35)
> richtig? wenn ja wie komm ich jetzt auf das y1 und das y2?
> Welche methode ist da die beste?
die beste Methode für Dich wäre es, wenn Du meine Antwort liest. Dort
musst Du nur noch Zahlen einsetzen. (Eigentlich sogar nur noch den
Wert von [mm] $y\,,$ [/mm] und Du solltest halt ein paar Vereinfachungen machen!)
Übrigens finde ich es nicht besonders schön, dass Du die Frage ohne
Hinweis in mehreren Foren postest! (Siehe die Links von MaslanyFanclub!)
Hier drücke ich jetzt mal ein Auge zu, das ändert aber nichts daran, dass
ich absolut nicht nachvollziehen kann, wieso Du auf meine Antwort nicht
eingehst. Entsprechend ist mir auch absolut egal, was Du da oben für ein
Zeug schreibst und rechnest - selbst, wenn ich könnte, wollte ich mir das
gar nicht angucken. (Wenn Du willst, dass das jemand macht, dann solltest
Du auf den Satz, den Du anwendest, verweisen - und wenn es per Link
nicht geht: Dann tippe ihn halt ab und sag', woher Du den hast...).
Dass mein Vorschlag zum Ziel führt:
Teste mal gewisse
[mm] $x=x_k=66+k*105\,$ [/mm] ($k [mm] \in \IZ$)
[/mm]
ob die das gewünschte erfüllen. Bei meiner letzten Antwort steht alles
drin (bis auf eine Kleinigkeit), mit der Du das nachvollziehen könntest.
Ob Du das nun willst: Das überlasse ich Dir...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:33 Mo 08.09.2014 | | Autor: | Marcel |
Hallo,
wie Teufel schon sagte:
> Bestimmen Sie die größte negative und kleinste positive
> Lösung des folgenden Gleichungssystems
> simultaner Kongruenzen für c = -1.
> x [mm] $\equiv$ [/mm] c + 4 mod 21
> x [mm] $\equiv$ [/mm] 4c mod 35
> Hallo!
> Kann ich hier bei dieser Aufgabenstellung das c+4 als 3
> zusammenfassen? Oder wie ist das hier zu verstehen?
genau so ist das zu verstehen. Warum man Euch elementarstes rechnen
läßt, weiß ich nicht. Oder kommt die Aufgabe mit einem anderen [mm] $c\,$ [/mm] nochmal?
> Wenn ja ist -4 [mm]\equiv[/mm] 35 = 31 [mm]\equiv[/mm] 35?
Das, was Du schreibst, ist sehr unschön, darauf hat Teufel Dich schon
hingewiesen. Ich fände es sogar noch besser, wenn er
[mm][m]:=[m]_{35}:=\{r \in \IZ: r \equiv m \text{ mod }35\}=\{u \in \IZ:\;\; u=m+k*35\text{, }k \in \IZ\}[/mm]
benutzt hätte. Dann gilt
[mm] $[-4]=[-4+35]=[31]\,.$
[/mm]
Das, was Du schreiben wolltest, war
$-4 [mm] \equiv [/mm] 31$ [mm] $\mod$ $35\,.$
[/mm]
Du hast oben aber wohl etwas falsch verstanden:
Man schreibt NICHT
$a [mm] \equiv [/mm] b$
für $a [mm] \in [a]_b\,.$
[/mm]
Sondern es gilt
$a [mm] \equiv [/mm] b$ [mm] $\mod$ $n\,$
[/mm]
ist gleichwertig mit
[mm] $n\,|\,(a-b)\,.$
[/mm]
Anders gesagt
$a [mm] \equiv [/mm] b$ [mm] $\mod$ $n\,$
[/mm]
[mm] $\iff$ $[a]_n=[b]_n\,.$
[/mm]
Deine Aufgabe ist es also, [mm] $x\,$ [/mm] zu finden, dass
$x [mm] \equiv [/mm] 3$ [mm] $\mod$ $21\,$
[/mm]
und
$x [mm] \equiv [/mm] 31$ [mm] $\mod$ $35\,.$
[/mm]
(D.h. es soll sowohl [mm] $21\,|\,(x-3)$ [/mm] als auch [mm] $35\,|\,(x-31)$ [/mm] gelten!)
Gruß,
Marcel
|
|
|
| |
|
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
Ich hab in den Untiefen des Internets folgende zwei Threads gefunden:
http://www.gute-mathe-fragen.de/146990/chinesicher-restsatz
und
http://www.matheboard.de/thread.php?threadid=545354
Ich finde es furchtbar, dass ich hier mittlerweile so paranoid bin sowas zu googeln und dann auch zu finden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:41 Mo 08.09.2014 | | Autor: | Diophant |
Hi MFC, 
> Ich hab in den Untiefen des Internets folgende zwei Threads
> gefunden:
>
> http://www.gute-mathe-fragen.de/146990/chinesicher-restsatz
> und
> http://www.matheboard.de/thread.php?threadid=545354
>
> Ich finde es furchtbar, dass ich hier mittlerweile so
> paranoid bin sowas zu googeln und dann auch zu finden.
dennoch ist es gut, dass du es machst. Man mag die Regel in Frage stellen, dennoch: es gibt sie und wie alle Regeln zum einen, damit sie eingehalten wird und zum andern, weil sich sicherlich in früheren Jahren diejenigen, die dieses Forum gegründet und zu dem gemacht haben, was es heute ist, etwas dabei gedacht haben.
Auch ich schaue manchmal nach, bisweilen ist wie derzeit sonst (im Alltag) zu viel los. Ich begrüße es aber, dass du dich darum kümmerst.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:53 Mo 08.09.2014 | | Autor: | Marcel |
Hallo Diophant,
> Hi MFC,
>
> > Ich hab in den Untiefen des Internets folgende zwei
> Threads
> > gefunden:
> >
> >
> http://www.gute-mathe-fragen.de/146990/chinesicher-restsatz
> > und
> > http://www.matheboard.de/thread.php?threadid=545354
> >
> > Ich finde es furchtbar, dass ich hier mittlerweile so
> > paranoid bin sowas zu googeln und dann auch zu finden.
>
> dennoch ist es gut, dass du es machst. Man mag die Regel in
> Frage stellen, dennoch: es gibt sie und wie alle Regeln zum
> einen, damit sie eingehalötenm wird und zum anmdern, weil
> sich sicherlcih in früheren Jahren diejenigen, die dieses
> Forum gegründet und zu dem gemacht haben, was es heute
> ist, etwas dabei gedacht haben.
ich war schon früh(er) dabei (nicht ganz zu Beginn) und es war gerade am
Anfang sehr ärgerlich, wenn man eine Antwort geschrieben hat, die man
sich auch hätte sparen können, weil Gleiches schon in einem anderen
Forum geschrieben wurde.
Daher verbieten wir ja auch keine Crosspostings, sondern wir möchten,
dass auf diese hingewiesen wird, damit man sich schnell einen Überblick
verschaffen kann, was schon gesagt wurde, oder ggf. auch, um etwas,
was für uns vielleicht *unschön* oder *unklar* formuliert erscheint, nochmal
klarzustellen. Es geht ja eben um Hilfe zur Selbsthilfe, und ich habe kein
Problem damit, wenn jemand 10 Leute um Hilfe bittet. Ich habe aber ein
Problem damit, wenn mich jemand etwas fragt, ich dem 30 Minuten meiner
Zeit schenke, um mir am Ende dann anzuhören: "Das habe ich aber alles
auch so schon von Person XY gehört."
Denn dann sage ich doch: "Und warum intervenierst Du nicht direkt und
läßt mich hier Dir alles nochmal erzählen?"
Denn das ist Zeitverschwendung. Wobei ich allerdings nun auch kein
Problem mit dieser Situation hätte, wenn man mir von vorneherein sagt:
"Ich habe mir das schonmal von Person XY erklären lassen, aber ich verstehe
das nicht. Kannst Du das mal erklären? Vielleicht machst Du das auf eine
andere Art, mit der ich besser klarkomme."
> Auch ich schaue manchmal nach, bisweilen ist wie derzeit
> sonst zu viel los. Ich begrüße es aber, dass du dich
> darum kümmerst.
Ich gucke auch viel zu selten - ich finde es eigentlich auch nervig, nach so
etwas Ausschau zu halten. Und genauso bin ich genervt, wenn jemand
seine Crosspostings nicht erwähnt. Dann habe ich halt auch irgendwann
auch keine Lust mehr, der Person zu antworten, denn wie halt im richtigen
Leben:
Wenn ich ständig von anderen erfahre, dass die/der Hilfesuchende das
Gleiche, was bei mir gefragt wurde, sich auch von anderen erklären läßt,
ohne es zu begründen:
Naja, warum soll ich mir dann noch die Zeit für ihn/sie nehmen...
Dann bin ich doch genauso *schweigsam* gegenüber derm Hilfegesuch,
wie die Person, die mir dann m.E. nach nur unnötig Arbeit aufhalsen will...
Die Kommunikation ist halt nicht nur ein Mittel, sondern sie bewirkt halt
auch etwas.
P.S. Bei schnoele finde ich hier das Crossposting ohne Hinweis allerdings
weniger schlimm als der Fakt, dass man nach Hilfe fragt, und dann doch
selbst macht, was man will.
Wenn man eine eigene Idee und Vorgehensweise hat, die man geprüft
haben will: Dann schreibt man sie auch direkt hin inklusive der Gedanken,
die man sich dazu gemacht hat. Und das ist eigentlich auch nur ein Appell
direkt an Dich, schnoele! ^^
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:43 Mo 08.09.2014 | | Autor: | Diophant |
Hallo und
![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
Das scheint ja ganz offensichtlich nicht zu stimmen. Bitte lies dir unsere Forenregeln durch, insbesondere Punkt 4 und beachte das bitte in Zukunft.
Gruß, Diophant
|
|
|
|
