Simultane Kongruenz (nicht teilerfremd)

09.08.2015, 18:35

Matheversteher

Auf diesen Beitrag antworten »

Simultane Kongruenz (nicht teilerfremd)

Hallo alle zusammen Wink

Wink

Ich möchte gerne die folgende simultane Kongruenz lösen:

$\begin{eqnarray*} x \equiv 46 \mod 60 \end{eqnarray*}$
$\begin{eqnarray*} x \equiv 34 \mod 112 \end{eqnarray*}$

Ich habe die Aufgabe mit dem Algorithmus von Wikipedia gelöst.

Mein Ergebnis ist x=706

Allerdings kommt mir das ganze doch ein wenig umständlich vor ohne Taschenrechner.

Ich möchte es also Lösen in dem ich die Kongruenzen so umwandle, dass sie paarweise Teilerfremd sind. Allerdings war mein Anfang falsch:

Ich habe 60 und 112 in Ihre PFZ zerlegt:
$\begin{eqnarray*} 60=2^2\cdot 3 \cdot 5 \end{eqnarray*}$
$\begin{eqnarray*} 112= 2^4 \cdot 7 \end{eqnarray*}$

Ich habe nun gedacht, dass ich die beiden Kongruenzen so umschreiben kann:

I: $\begin{eqnarray*} ( x \equiv 2 \mod 4 ) \end{eqnarray*}$ --> kann gestrichen werden, aufgrund IV
II: $\begin{eqnarray*} x \equiv 1 \mod 3 \end{eqnarray*}$
III: $\begin{eqnarray*} x \equiv 1 \mod 5 \end{eqnarray*}$

sowie:
IV: $\begin{eqnarray*} x \equiv 2 \mod 16 \end{eqnarray*}$
V: $\begin{eqnarray*} x \equiv 6 \mod 7 \end{eqnarray*}$

Allerdings scheinen die Bedingungen nicht zu stimmen, da meine Lösung hier x=1006 ist. Was mache ich falsch?

Ich bitte um Hilfe und vielen Dank schon mal verwirrt

verwirrt

09.08.2015, 19:46

Bjoern1982

Auf diesen Beitrag antworten »

Nicht I kann gestrichen werden sondern IV. Augenzwinkern

Augenzwinkern

09.08.2015, 20:04

Matheversteher

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
Nicht I kann gestrichen werden sondern IV. Augenzwinkern

Augenzwinkern

Hallo, schoen dass du mir hilfst.
Warum muss ich hier IV streichen? In meinem Skript steht, dass ich die höchste Potenz 2^4 behalten muss, da sie die Bedigung der anderen Kongruenz $\begin{eqnarray*} 2^2 \end{eqnarray*}$ enthält. (andernfalls nicht lösbar))

Aber ist es denn überhaupt so richtig, wie ich die Kongruenzen aufgesplittet habe, also in Primfaktoren? verwirrt

verwirrt

09.08.2015, 20:56

Bjoern1982

Auf diesen Beitrag antworten »

Zunächst mal sind doch alle Zahlen, die IV erfüllen, in I enthalten und nicht umgekehrt.
Dazu braucht man eigentlich kein Skript, sondern man muss es sich nur mal aufschreiben:

I ------> 2,6,10,14,18,22,26,30,34....

IV ----> 2,18,34,50,66...

Einverstanden ?

Du kannst das mit dem Aufsplitten so machen.
Probiere es mal mit den richtigen 4 linearen Kongruenzen aus.

Zitat:

II: $\begin{eqnarray*} x \equiv 1 \mod 3 \end{eqnarray*}$
III: $\begin{eqnarray*} x \equiv 1 \mod 5 \end{eqnarray*}$

Das hier kannst du übrigens auch noch zu einer linearen Konguenz zusammenfassen, eine Idee wie ?

Alternativ könnte man sich bei einem solch überschaubaren, nur aus 2 Kongruenzen bestehenden System, vielleicht auch mal folgendes überlegen:

Zitat:

$\begin{eqnarray*} x \equiv 46 \mod 60 \end{eqnarray*}$
$\begin{eqnarray*} x \equiv 34 \mod 112 \end{eqnarray*}$

Umgeschrieben als Gleichungssystem ergibt das ja:

x=60a+46
x=112b+34

Gleichgesetzt und umgestellt führt das z.B. zu 28b=15a+3 bzw. $\begin{eqnarray*} 28b \equiv 3 \mod 15 \end{eqnarray*}$ und mittels genauem Hinschauen (28 ist ja modulo 15 nichts anderes als -2 und mit 7 multipliziert hat man dann leicht die 1 vor dem b erzeugt ganz ohne EEA ) oder eben mit dem EEA folgt recht schnell b=15k+21 und durch Einsetzen die gewünschten Lösungen.

10.08.2015, 06:35

IfindU

Auf diesen Beitrag antworten »

@Bjoern Ich denke nicht, dass du a priori rechtfertigen kannst die schwächere Kongruenz zu nehmen. Und mit deiner Logik könnte man auch alle Gleichungen streichen und $\begin{eqnarray*} x \equiv 0 \mod 1 \end{eqnarray*}$ annehmen.

@Matheversteher
Ich habe mal deine richtige Lösung in die Modulo-Gleichungen gesetzt und diese erfüllt die, 1006 mod 7 ist aber z.B. laut Wolfram Alpha 5 statt 6. Du hast dich also da verrechnet, aufgestellt sieht es richtig aus. $\begin{eqnarray*} [ 1006 = 700 + 350 - 49 + 5] \end{eqnarray*}$

10.08.2015, 08:59

Bjoern1982

Auf diesen Beitrag antworten »

Ui ja klar, hast Recht IFindU - tut mir leid. Hammer

Hammer

Wie war das noch mit Durchschnitt und Vereinigung...

Anzeige

10.08.2015, 18:30

Matheversteher

Auf diesen Beitrag antworten »

Hallo IfindU,
schön dass du dich beteiligst Freude

Freude

Zitat:

Original von IfindU
@Matheversteher
Ich habe mal deine richtige Lösung in die Modulo-Gleichungen gesetzt und diese erfüllt die, 1006 mod 7 ist aber z.B. laut Wolfram Alpha 5 statt 6. Du hast dich also da verrechnet, aufgestellt sieht es richtig aus. $\begin{eqnarray*} [ 1006 = 700 + 350 - 49 + 5] \end{eqnarray*}$

Allerdings bin ich felsenfest davon überzeugt, dass 1006 nicht für die Ausgabgskongruenzen stimmt. Und das sollte aber doch eigentlich der Fall sein. verwirrt

verwirrt

Für die Ausgangskongruenzen
$\begin{eqnarray*} x \equiv 46 \mod 60 \end{eqnarray*}$
$\begin{eqnarray*} x \equiv 34 \mod 112 \end{eqnarray*}$

Denn bei der letzten Kongruenz erhalte ich 9 * 112 = 1008.

Aber:
Für die teilerfremden Kongruenzen hingegen erhalte ich auch x=1006. Das heißt ich habe bei der Aufspaltung einen Fehler gemacht.

10.08.2015, 18:35

IfindU

Auf diesen Beitrag antworten »

RE: Simultane Kongruenz (nicht teilerfremd)

Zitat:

Original von Matheversteher
[...]
Ich habe nun gedacht, dass ich die beiden Kongruenzen so umschreiben kann:
[...]
V: $\begin{eqnarray*} x \equiv 6 \mod 7 \end{eqnarray*}$

Allerdings scheinen die Bedingungen nicht zu stimmen, da meine Lösung hier x=1006 ist. Was mache ich falsch?

Meine Aussage bezog sich darauf. $\begin{eqnarray*} x = 1006 \end{eqnarray*}$ löst nicht V, da $\begin{eqnarray*} 1006 \equiv 5 \mod 7 \end{eqnarray*}$ .

10.08.2015, 19:42

Matheversteher

Auf diesen Beitrag antworten »

RE: Simultane Kongruenz (nicht teilerfremd)

Zitat:

Original von IfindU
Meine Aussage bezog sich darauf. $\begin{eqnarray*} x = 1006 \end{eqnarray*}$ löst nicht V, da $\begin{eqnarray*} 1006 \equiv 5 \mod 7 \end{eqnarray*}$ .

Ah stimmt, da habe ich zu schnell gelesen.

Aber wie stelle ich die Bedingunge denn dann richtig auf?

112 hat die PFZ $\begin{eqnarray*} 2^4 \cdot 7 \end{eqnarray*}$

daraus habe ich dann meine beiden Kongruenzen gebildet. Die eine mod 16 und die andere mod 7.
Dementsprechend habe ich auch die Reste "angepasst". 34 kongruent 6 mod 7.
So komme ich af Bedingung V. Doch diese ist offensichtlich nicht richtig. Wie müsste sie stattdessen aussehen.

$\begin{eqnarray*} [ 1006 = 700 + 350 - 49 + 5] \end{eqnarray*}$

Das hast du jetzt einfach aus meine 4 Kongruenzen berechnet? Oder wie kommst du darauf? verwirrt

verwirrt

10.08.2015, 19:51

IfindU

Auf diesen Beitrag antworten »

RE: Simultane Kongruenz (nicht teilerfremd)
Deine richtige Lösung $\begin{eqnarray*} x = 706 \end{eqnarray*}$ löst dein System an Gleichungen, die falsche Lösung $\begin{eqnarray*} x = 1006 \end{eqnarray*}$ löst nicht das System.

Es ist also nicht das System fehlerhaft, sondern die Berechnung der Lösung aus dem System.

Die Aufteilung $\begin{eqnarray*} 1006 = 700 + ... \end{eqnarray*}$ habe ich nur geschrieben, weil man daraus sofort sieht, dass $\begin{eqnarray*} 1006 \equiv 5 \mod 7 \end{eqnarray*}$ ist.

10.08.2015, 20:59

Matheversteher

Auf diesen Beitrag antworten »

RE: Simultane Kongruenz (nicht teilerfremd)

Zitat:

Original von IfindU
Deine richtige Lösung $\begin{eqnarray*} x = 706 \end{eqnarray*}$ löst dein System an Gleichungen, die falsche Lösung $\begin{eqnarray*} x = 1006 \end{eqnarray*}$ löst nicht das System.

Es ist also nicht das System fehlerhaft, sondern die Berechnung der Lösung aus dem System.

Die Aufteilung $\begin{eqnarray*} 1006 = 700 + ... \end{eqnarray*}$ habe ich nur geschrieben, weil man daraus sofort sieht, dass $\begin{eqnarray*} 1006 \equiv 5 \mod 7 \end{eqnarray*}$ ist.

Jetzt habe ich es verstanden was du mir sagen möchtest Freude

Freude

(Glaube ich zumindest)

Aber hilf mir doch jetzt noch bitte bei der Umformung in die 4 Zielkongruenzen.

Zitat:

Original von Bjoern1982
Nicht I kann gestrichen werden sondern IV.

Denn ich habe es nun auch noch einmal mit Bedingung I statt IV durchgerechnet, auch hier komme ich auf ein falsches Ergebnis (x=286).

Für die Ausgangkongruenz mod 60 passt x, jedoch nicht für mod 112. Was mache ich falsch? verwirrt

verwirrt

Ich bin hier kurz vorm Wahnsinnig werden. Hammer

Hammer

10.08.2015, 21:52

IfindU

Auf diesen Beitrag antworten »

RE: Simultane Kongruenz (nicht teilerfremd)
Schwer zu sagen was du falsch machst. Irgendwo wird sich ein Rechenfehler einschummeln. Ich bin nicht wirklich vertraut mit Zahlentheorie, aber:
Du kannst nicht von I bis V auf $\begin{eqnarray*} x = 1006 \end{eqnarray*}$ kommen. Es mag sein, dass dein System zu schwach ist, unvollständig oder sonstiges, womit du theoretisch auf mehr/andere Lösungen als $\begin{eqnarray*} x = 706 \end{eqnarray*}$ kommen kannst. ABER $\begin{eqnarray*} x = 706 \end{eqnarray*}$ ist wenigstens eine Lösung UND du kannst nicht richtig rechnen und auf $\begin{eqnarray*} x = 1006 \end{eqnarray*}$ kommen. D.h. suche da deinen Rechenfehler/Logikfehler bzw. poste diese hier.

11.08.2015, 08:37

HAL 9000

Auf diesen Beitrag antworten »

Kommen wir mal auf die Aufspaltung der Ausgangskongruenzen zurück: Nach Primfaktorpotenzen getrennt lautet die erste

$\begin{align*} x\equiv 46\equiv 2\bmod 2^2 \end{align*}$
$\begin{align*} x\equiv 46\equiv 1\bmod 3 \end{align*}$
$\begin{align*} x\equiv 46\equiv 1\bmod 5 \end{align*}$

und die zweite

$\begin{align*} x\equiv 34\equiv 2\bmod 2^4 \end{align*}$
$\begin{align*} x\equiv 34\equiv 6\bmod 7 \end{align*}$

Wir sehen nur bei den Zweierpotenzen Gemeinsamkeiten, und da ist die Bedingung mit der höheren Potenz $\begin{align*} x\equiv 2\bmod 2^4 \end{align*}$ stärker, die andere folgt daraus (steht also insbesondere nicht im Konflikt dazu, was ansonsten zur Nichtlösbarkeit des Systems führen würde). Wir können also die schwächere Bedingung hinsichtlich modulo $\begin{align*} 2^2 \end{align*}$ bei der ersten Gleichung weglassen und kommen so auf das System

$\begin{align*} x\equiv 46\equiv 1\bmod 15 \end{align*}$

$\begin{align*} x\equiv 34\bmod 112 \end{align*}$

mit teilerfremden Modulen.

11.08.2015, 19:59

Matheversteher

Auf diesen Beitrag antworten »

Hallo HAL

Wink

Zitat:

Original von HAL 9000

$\begin{align*} x\equiv 46\equiv 1\bmod 15 \end{align*}$

$\begin{align*} x\equiv 34\bmod 112 \end{align*}$

Ach herrjemine!
So habe ich die Kongruenzen nie betrachtet. Hammer

Hammer

Sie sind ja dann bereits schon teilerfremd und ich muss sie gar nicht weiter in ihre jeweiligen Primfaktoren zerlegen.

Ich kann/darf es wahrscheinlich auch gar nicht oder?

Weshalb ich die höhere Potenz behalten muss ist mir klar Freude

Freude

11.08.2015, 20:15

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Matheversteher
Ich kann/darf es wahrscheinlich auch gar nicht oder?

Doch, darfst du - aber dann sind es halt mehr als zwei Kongruenzen, was aufwändiger in der Bearbeitung ist.

11.08.2015, 23:22

Matheversteher

Auf diesen Beitrag antworten »

So ihr drei,

Ich danke euch vielmals, dass ihr euch die Zeit genommen habt. Gott

Gott

Freude

Das Ergebnis stimmt nun auch, wenn ich es mit den Kongruenzen II-V rechne.
Ich habe die ganze Zeit in IV mit mod 15 gerechnet Habe wohl den Wald vor lauter Zahlen nicht gesehen. Augenzwinkern

Augenzwinkern

Ich wünsche euch eine gute Nacht Wink

Wink

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »