Partner von azubiworld.com - Logo
 
Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Simultane Kongruenz

Simultane Kongruenz

Universität / Fachhochschule

Elementare Zahlentheorie

Teilbarkeit

Tags: Elementare Zahlentheorie, Modulorechnung, simultane Kongruenz, Teilbarkeit

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Tackleberry

Tackleberry aktiv_icon

15:12 Uhr, 22.11.2010

Antworten
Hallöchen zusammen,

wäre nett wenn mir jemand bei der Lösung der folgenden Aufgabe behilflich sein könnte:

Finden Sie alle Lösungen [x]924 der simultanen Kongruenzen

x5(mod77) und x6(mod12).

Habe überhaupt keinen Ansatz weil mich dieses [x]924 total verwirrt.
Vielen Dank für Eure Hilfe.

MfG Axel

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)
Antwort
michaL

michaL aktiv_icon

18:06 Uhr, 22.11.2010

Antworten
Hallo,

also, ich erkläre dir, wie ich es verstanden habe. Es geht also um
x5 mod 77
x6 mod 12

Wenn x der ersten Kongruenz genügt, dann gibt es ein v, sodass x=77v+5.
Wenn x der zweiten Kongruenz genügt, dann gibt es ein w, sodass x=12w+6.

Also muss
77v+5=12w+677v-12w=1 (I)
gelten. Nun finden wir erst einmal so ein Paar (v,w), das sowas leistet. So etwas gibt es nur, wenn der ggT(12,77) ein Teiler von 6-5 ist, was aber hier der Fall ist.
Wir bedienen uns des euklidischen Algorithmus:

77=612+5
12=25+2
5=22+1
2=21+0 (<- diese Zeile brauchen wir eigentlich nicht)

Gut, also ist der ggT(12,77)=1 (was man vom Hinsehen her hätte sagen können). Wir brauchen die Rückwärtseinsetzung, um aus 1 eine Z-Linearkombination aus 12 und 77 zu machen:

Vorletzte Zeile => 1=5-22=(77-612)-2(12-25)=77-812+45=77-812+4(77-612)
=577-3212

Also schreibe ich (I) wie folgt:
77v-12w=577-3212
Umformen ergibt:
77v-577=12w-3212 bzw. 77(v-5)=12(w-32) (II)

All die Arbeit, nur um (II) zu erhalten. Da nämlich 77 kein Teiler von 12 ist, muss es also ein Teiler von w-32 sein. Umgekehrt muss 12 (was 77 nicht teilt) einer von v-5 sein.

Der Einfachheit halber kann man v-5=12v=17 und w-32=77w=109 setzen.
(Probe: x=77v+5=1314 einerseits und x=12w+6=1314 andererseits.

So, damit ist eine Partikulärlösung gefunden, nämlich x=1314 (eine kleinere wäre auch möglich gewesen, aber ich rechne eben so).
Nun überlegen wir uns, welches noch alles Lösungen sind.
Geht man nun gleichzeitig in 77er Schritten UND(!) in 12er Schritten (also in kgV(12,77)=924er Schritten), dann treffen wir natürlich wieder auf so eine Lösung, etwa x=1314-924=390.
Also sind schonmal alle x mit
x1314 mod 924 Lösungen.
Dass es keine anderen Lösungen außerhalb dieser Schrittreichweite (924) geben kann, kann man leicht damit beweisen, dass 390 tatsächlich die kleinste natürliche Lösung darstellt. Gäbe es noch andere, kann man leicht einen Widerspruch zu dieser Tatsache konstruieren. (Details im Beweis zum chinesischen Restsatz)

Mfg Michael
Tackleberry

Tackleberry aktiv_icon

09:18 Uhr, 23.11.2010

Antworten
Vielen vielen Dank Michael für die äußerst detailierte und, sogar für mich :-), verständliche Antwort.
Antwort
BjBot

BjBot aktiv_icon

03:27 Uhr, 24.11.2010

Antworten
Alternativ:

5+77r=6+12s77r=1+12s77r5rmod 12r5mod 12 da 55=251 mod 12

r IN die 1. Kongruenz bzw Gleichung einsetzen x=5+77(5+12k)=390+924kx390 mod 924