Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Lösen simultaner Kongruenzen

Lösen simultaner Kongruenzen

Universität / Fachhochschule

Tags: simultane Kongruenz

anonymous

13:20 Uhr, 10.06.2011

Hallo, es geht um simultane Kongruenzen, die es zu lösen gilt. Ich habe noch überhaupt keine Ahnung, wie man dies macht.
1.

2 x

kongr.

1 mod 5

3 x

kongr.

2 mod 7

4 x

kongr.

1 mod 11

Ich habe mich im Internet ein wenig schlau gemacht. Da stand, dass bei Teilerfremdheit, die bei 1. gegeben ist, mit dem sogenannten chinesichen Restsatz gerechnet werden kann.

2.

x

kongr.

46 mod 60

x

kongr.

20 mod 112

x

kongr.

56 mod 135

x

kongr.

11 mod 72

Hoffe darauf, dass mir jemand helfen kann.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

michaL aktiv_icon

14:12 Uhr, 10.06.2011

Hallo,

benutze doch bitte die Forensuche. Zwei geeignete Stichwörter fallen dir sicher von selbst ein. Bedenke, dass zunächst nur ein kleiner Teil der (mehr oder weniger) geeigneten Threads angezeigt werden. Ach, ja, eins noch: Vielleicht eignen sich nur die Treffer im Studentenforum.

Mfg Michael

anonymous

16:34 Uhr, 10.06.2011

Hi, das mache ich ja immer, aber habe nicht so richtig ähnliche Fälle gefunden.

Bummerang

16:52 Uhr, 10.06.2011

Hallo,

Schema

F :

2 \cdot x \equiv 1 (mod 5)

3 \cdot x \equiv 2 (mod 7)

4 \cdot x \equiv 1 (mod 11)

5, 7

und

11

sind paarweise Teilerfrend (weil allesamt Primzahlen)

kgV(2,3,4)

= 12

12 \cdot x = 6 \cdot 2 \cdot x \equiv 6 \cdot 1 (mod 5) \equiv 6 (mod 5) \equiv 1 (mod 5)

12 \cdot x = 4 \cdot 3 \cdot x \equiv 4 \cdot 2 (mod 7) \equiv 8 (mod 7) \equiv 1 (mod 7)

12 \cdot x = 3 \cdot 4 \cdot x \equiv 3 \cdot 1 (mod 11) \equiv 3 (mod 11)

Offensichtlich gilt auch:

12 \cdot x \equiv 0 (mod 12)

Weil

12

ebenfalls zu

5, 7

und

11

paarweise Teilerfremd ist, erfüllen die 4 Kongruenzen für

m = 12 \cdot x

die Voraussetzungen für den chinesischen Restklassensatz und für den gibt es einen Algorithmus, den man mehrfach im Internet finden kann.

m \equiv 1 (mod 5)

m \equiv 1 (mod 7)

m \equiv 3 (mod 11)

m \equiv 0 (mod 12)

Zur Kontrolle: Für

m

ergibt sich

36 + k \cdot (5 \cdot 7 \cdot 11 \cdot 12)

und demzufolge ist

x = 3 + k \cdot (5 \cdot 7 \cdot 11)

die gesuchte Lösung.

michaL aktiv_icon

16:53 Uhr, 10.06.2011

Hallo,

aber, aber, das ist wenig glaubwürdig!

http//www.onlinemathe.de/forum/Simultane-Kongruenzen-8

Mfg Michael

anonymous

17:11 Uhr, 10.06.2011

Bei der Aufgabe (wenn man den Link anklickt) verstehe ich bereits den ersten Schritt nicht.

zur 1.

12⋅x=6⋅2⋅x≡6⋅1

(mod

5)≡6

(mod

5)≡1

(mod 5)

12⋅x=4⋅3⋅x≡4⋅2

(mod

7)≡8

(mod

7)≡1

(mod 7)

12⋅x=3⋅4⋅x≡3⋅1

(mod

11)≡3

(mod 11)

Wieso steht da

6 \cdot 2 \cdot x

kongruent

6 \cdot 1 mod 5

? Wie kommt man darauf?

- - - - - - - - - - - - - - - - - - -

m≡1

(mod 5)

m≡1

(mod 7)

m≡3

(mod 11)

m≡0

(mod 12)

Bei Wikipedia habe ich nachgeschaut.

M = 5 \cdot 7 \cdot 11 \cdot 12 = 4620

M 1 = \frac{M}{5} = 924 M 2 = \frac{M}{7} = 660 M 3 = \frac{M}{11} = 420 M 4 = \frac{M}{12} = 385

So soll man jetzt den ggT(5,924) , ggT(7,660) ,ggT(11,420) und ggT(12,385) bestimmen?

924 = 5 \cdot 184 + 4

184 = 46 \cdot 4 + 0

4 = 924 - (5 \cdot 184)

660 = 94 \cdot 7 + 2

7 = 3 \cdot 2 + 1

2 = 2 \cdot 1 + 0

1 = 7 - 3 \cdot (660 - 94 \cdot 7)

1 = 7 - 3 \cdot 660 + 282 \cdot 7

1 = 283 \cdot 7 - 3 \cdot 660

420 = 38 \cdot 11 + 2

11 = 5 \cdot 2 + 1

2 = 2 \cdot 1 + 0

1 = 11 - 5 \cdot (420 - 38 \cdot 11)

1 = 11 - 5 \cdot 420 + 190 \cdot 11

1 = 191 \cdot 11 - 5 \cdot 420

385 = 32 \cdot 12 + 1

12 = 12 \cdot 1 + 0

1 = 385 - 32 \cdot 12

Wie gehts weiter?

Bummerang

17:20 Uhr, 10.06.2011

Hallo,

"Wieso steht da

6 \cdot 2 \cdot x

kongruent 6*1mod5? Wie kommt man darauf?"

Du hast

2 \cdot x \equiv 1 (mod 5)

Wenn man beide Seiten mit 6 multipliziert, sind die beiden Seiten immer noch kongruent, also:

6 \cdot 2 \cdot x \equiv 6 \cdot 1 (mod 5)

Mit 6 multipliziert man, weil das kgV

12

ist und der Faktor vor

x

die 2 ist und

\frac{12}{2} = 6

ist.

Nimm nicht den Algorithmus von wikipedia, es gibt wesentlich eingängigere, intuitivere Algorithmen. Der von mir bevorzugte Algorithmus ist ein iterativer Algorithmus und den starte ich immer mit der Kongruenz mit dem höchsten Modulo und dann gehe ich die Modulo-Werte abwärts voran!

anonymous

17:42 Uhr, 10.06.2011

Habe ich verstanden. Habe noch nie von gehört. Könntest du mir dein Vorgehen genauer beschreiben. Habe noch nie was vom iterativen Algorithmus gehört.

Wie würde es eigentlich mit "meinem" Verfahren weitergehen?

Bummerang

17:53 Uhr, 10.06.2011

Hallo,

iterativ heißt "Schritt für Schritt" der Lösung annähern. Dazu bestimmt man die kleinste Zahl, die eine Kongruenz erfüllt, ich starte wie bereits gesagt immer mit der Kongruenz mit dem größten Modulo Wert. Dann prüfe ich die nächste Kongruenz (die mit dem zweitgrößten Modulo Wert), die wird

i . d . R

. nicht erfüllt sein. Dann überlege ich mir, welches ist die kleinste Zahl, die ich zu meinem Startwert addieren muss, damit die erste Kongruenz erhalten bleibt und ich addiere diese Zahl so lange, bis die zweite Kongruenz ebenfalls erfüllt ist. Jetzt habe ich eine Zahl, die bereits 2 Kongruenzen erfüllt. Dann nehme ich mir den nächstkleineren Modul wert vor und prüfe meine Zahl gegen diesen Wert. Auch hier wird

i . d . R

. die Kongruenz nicht erfüllt sein und ich überlege mir jetzt eine neue Zahl die bei der Addition die beiden ersten Kongruenzen erfült läßt. Diese addiere ich wie der so oft, bis auch die dritte Kongruenz erfüllt ist. So macht man weiter bis zur letzten, aber da Du die Lösung

36

bereits kennst, weißt Du, dass das hier sehr schnell gehen wird.

anonymous

17:58 Uhr, 10.06.2011

Erstmal vielen Dank für deine Hilfe bisher. OK,das Verfahren habe ich verstanden, nur könnte dieses bei größeren Zahlen problematischer werden, finde ich.
Wie kommt man eigentlich darauf:
Für

m

ergibt sich 36+k⋅(5⋅7⋅11⋅12) und demzufolge ist x=3+k⋅(5⋅7⋅11) die gesuchte Lösung.
Einfach durch

12

geteilt, oder?

Und wie ginge mein Verfahren weiter? Würde mich mal interessieren.

Bummerang

18:11 Uhr, 10.06.2011

Hallo,

das Verfahren wird sicher mit größeren Zahlen und mit mehr Kongruenzen immer unübersichtlicher. Aber hast Du Dir diese Gedanken auch für das Verfahren bei wikipedia gemacht? Also! Die zunehmende Unübersichtlichkeit ist keine Folge des Algorithmus sondern der Aufgabenstellung. Ich exerziere mal durch:

Startwert

m = 0,

weil

0 \equiv 0 (mod 12)

m = 0 : 0 \equiv 0 (mod 11) \Rightarrow

kleinste zu addierende Zahl ist

12 \Rightarrow m = 0 + 12 = 12

m = 12 : 12 \equiv 1 (mod 11) \Rightarrow m = 12 + 12 = 24

m = 24 : 24 \equiv 2 (mod 11) \Rightarrow m = 24 + 12 = 36

m = 36 : 36 \equiv 3 (mod 11) \Rightarrow

Kongruenz erfüllt

\Rightarrow

nächste Kongruenz nehmen

m = 36 : 36 \equiv 1 (mod 7) \Rightarrow

Kongruenz erfüllt

\Rightarrow

nächste Kongruenz nehmen

m = 36 : 36 \equiv 1 (mod 5) \Rightarrow

Kongruenz erfüllt

\Rightarrow

fertig

Wäre an der Stelle, an der man mit der Kongruenz zu 7 nicht die 1 gestanden gewesen, müßte man mit Ermittlung der nächsten kleinsten Zahl für die Addition weitermachen. Diese Zahl wäre die

132 = 12 \cdot 11

gewesen. Denn diese Zahl ist sowohl durch

11

als auch durch

12

teilbar und ändert bei einer Addition nicht die bereits erfüllten Kongruenzen. Wäre die Kongruenz mit der 5 nicht gleich erfüllt gewesen, wäre die zu ermittelnde kleinste Zahl für die Addition die

12 \cdot 11 \cdot 7

gewesen. Und wenn alle Kongruenzen erfüllt sind, kann man jedes beliebige Vielfache von

12 \cdot 11 \cdot 7 \cdot 5

dazuaddieren, die Kongruenzen bleiben erhalten. Und auf das

x

kommt man natürlich, indem man die Lösung durch

12

teilt und

\frac{36}{12} = 3

und bei den Faktoren fällt einfach die

12

weg...

anonymous

18:14 Uhr, 10.06.2011

Hi, dein Verfahren habe ich ja verstanden. Bei dem von wikipedia komme ich nicht so recht weiter. Habe ja jetzt den euklidischen algorithmus hingeschrieben, nur was muss man weiter tun?

http//de.wikipedia.org/wiki/Chinesischer_Restsatz

Bummerang

18:16 Uhr, 10.06.2011

Hallo,

"nur was muss man weiter tun?" - Du hast die Lösung, was willst Du weiter machen?

anonymous

18:20 Uhr, 10.06.2011

Ich meine eigentlich mit dem wikipedia-Verfahren?

Dann zu 2.

x

kongr. 46mod60

x

kongr. 20mod112

Die Modulo-Werte sind nicht teilerfremd.
ggT(60,112) wäre 4. Man muss die doch erstmal irgendwie umformen.

michaL aktiv_icon

18:27 Uhr, 10.06.2011

Hallo,

ich würde zunächst zusehen, die Koeffizienten vor der Variablen zu normieren:

Dein Beispiel:

2 x \equiv 1

mod 5 zu

3 \cdot 2 x \equiv 3 \cdot 1

mod 5, also:
(I)

x \equiv 3

mod 5

(II)

x \equiv 3

mod 7

Die beiden lassen sich doch primstens zusammenfassen zu

x \equiv 3

mod 21.

Daran kann man nun aber nichts erklären (weil man statt zu rechnen natürlich lieber das Auge nimmt).

Nehmen wir mal die dritte Gleichung, was für ein Glück, sie ergibt

x \equiv 3

mod 11.

Dann kannst du

x \equiv 3

mod 21

x \equiv 3

mod 11
zusammenfassen zu

x \equiv 3

mod 231.

Das geht hier deshalb so einfach, weil die Zahlen, zu denen

x

kongruent sein soll, jeweils schon gleich sind. Ist das nicht so, muss man erst einmal dafür sorgen dass sie es sind.

Dafür könnten wir ja mal aus dem Link (den du hättest suchen und finden können) zwei Gleichungen nehmen, die wir dann zu einer zusammenfassen.

2 x \equiv 8

mod 3

4 x \equiv 7

mod 11

Das Inverse zu 2 (mod 3) ist 2 selbst. Das Inverse zu 4 (mod 11) ist 3, d.h. die beiden Gleichungen werden "vereinfacht" zu

4 x \equiv x \equiv 16 \equiv 1

mod 3

12 x \equiv x \equiv 21 \equiv 10

mod 11

bzw.:
(I)

x \equiv 1

mod 3
(II)

x \equiv 10

mod 11

Nach diesem ersten Schritt sucht man eine Partikuläre Lösung. Das geht mit Auge (bei so einfachen Zahlen wie diesen) oder aber auch mit Methode. Mit Auge finde ich 43 (

= 14 \cdot 3 + 1

bzw.

= 3 \cdot 11 + 10

).

Mit Methode mache ich das immer so (hab ich mir selbst ausgedacht, daher fehlen mir da teilweise Begriffe):

Nach (I) muss

x = 3 k + 1

für ein ganzzahliges

k

gelten, nach (II)

x = 11 l + 10

.
Zusammen also

11 l + 10 = 3 k + 1 \overset{}{\Leftrightarrow} 3 k - 11 l = 9 = 9 \cdot 1

. (*)
Da der ggT von 11 und 3 ein Teiler von 9 ist, kann man hier weiter machen. Sonst ginge es nicht. Darauf baut auch diese (meine) Methode auf!
Mit Euklid (oder Auge) findet man:

1 = 4 \cdot 3 - 1 \cdot 11

(hier gehen auch andere

ℤ

-Linearkombinationen, aber dies eben mal nach Schema), d.h.

9 = 36 \cdot 3 - 9 \cdot 11

.

Nun greifen wir (*) wieder auf und arbeiten die letzte Gleichung ein:

3 k - 11 l = 36 \cdot 3 - 9 \cdot 11

(**)

Diese Gleichung arbeiten wir so um, dass alles mit dem Faktor 3 auf der einen, alles mit dem Faktor 11 auf der anderen Seite steht. Warum? Gleich!

3 k - 36 \cdot 3 = 11 l - 9 \cdot 11 \overset{}{\Leftrightarrow} 3 (k - 36) = 11 (l - 9)

Und nu kommts. Da 3 kein Teiler von 11 ist, muss 3 ein Teiler von

l - 9

sein, der Einfachheit halber ist das der Fall, wenn gleich

l - 9 = 3

gilt, also

l = 12

.
Umgekehrt ist 11 kein Teiler von 3, also muss 11 ein Teiler von

k - 36

sein, also am besten gleich

k - 36 = 11 \overset{}{\Leftrightarrow} k = 47

.
Dann berechnet sich

x

x = 3 k + 1 = 3 \cdot 47 + 1 = 142

, anders herum gilt ebenfalls

x = 11 l + 10 = 11 \cdot 12 + 10 = 142

.

Auf diese Weise findet man eine Partikulärlösung:

x = 142

. Klar, wenn 142 eine Lösung ist, dann auch

142 + m \cdot 3 \cdot 11

, also kannst du die beiden Kongruenzen zusammenfassen zu

x \equiv 142

mod 33 bzw (kleiner)

x \equiv 10

mod 33.

So mache ich das.

Mfg Michael

anonymous

18:40 Uhr, 10.06.2011

Dann zu 2.

x

kongr. 46mod60

x

kongr. 20mod112

Die Modulo-Werte sind nicht teilerfremd.
ggT(60,112) wäre 4. Man muss die doch erstmal irgendwie umformen.

michaL aktiv_icon

18:49 Uhr, 10.06.2011

Hallo,

die beiden Kongruenzen können nicht simultan erfüllt werden.
Erkennbar daran, dass der ggT von 60 und 112 (das ist 4, wie du selbst schreibst), KEIN Teiler der Differenz

46 - 20 = 26

ist.

Ich weiß, das nicht so einfach einzusehen, aber man kann es in diesem Fall doch leicht verständlich machen.
Betrachte die erste Kongruenz modulo 4, dann müsste

x \equiv 46

mod 4 sein, also kongruent 2 mod 4.
Bei der zweiten ergibt sich aber, dass

x \equiv 20

mod 4 sein müsste, also kongruent 0 mod 4. Das geht gleichzeitig offenbar nicht!

Mfg Michael

anonymous

18:56 Uhr, 10.06.2011

Klingt ja plausibel, also hat die 2. keine Lösung?

3.

x

kongr.

56 mod 135

x

kongr.

11 mod 72

ggT ist ja hier 9.
Also hier bei ist dieser ggT Teiler der Differenz

56 - 11 = 45

michaL aktiv_icon

19:02 Uhr, 10.06.2011

Hallo,

ja, die beiden Gleichungen kannst du mit dem Verfahren (das ich dir vorgerechnet habe) zusammenfassen zu einer Kongruenz.

Zeig mal!

Mfg Michael

EDIT: Kurzschluss ;-)

anonymous

19:07 Uhr, 10.06.2011

Irgendwie finde ich das Verfahren zu kompliziert. Geht das nicht irgendwie mit dem von Bummerang?

Also

56 mod 3

und

11 mod 3

? Das ergebe

x

kongr

2 mod 3

michaL aktiv_icon

19:21 Uhr, 10.06.2011

Hallo,

geht bestimmt auch. Wie ich schon schrieb, dieses Verfahren hab ich mir als Student selbst überlegt. Was brauche ich also ein anderes?

Mfg Michael

anonymous

19:42 Uhr, 10.06.2011

Das muss doch auch irgendwie einfacher gehen? Ist einfach ziemlich unübersichtlich das Ganze. Mit dem iterativen Vorgehen komme ich auch nicht wirklich weiter.

Bringt es was, die Modulo-Zahlen zu zerteilen?

135 = 9 \cdot 15

Ich habe doch dann:

x

kongruent

11 mod 9

x

kongruent

11 mod 15

x

kongruent

11 mod 72

Bummerang

23:09 Uhr, 10.06.2011

Hallo,

der Ansatz mit

x \equiv 11 (mod 9)

x \equiv 11 (mod 15)

x \equiv 11 (mod 72)

führt mit

(z . B .)

meinem iterativen Verfahren zur Lösung

x = 11

. Wie man leicht sieht, ist aber

x = 11

keine Lösung der Ausgangskongruenzen.

Aber das schöne an meinem iterativen Verfahren ist, dass es keine teilerfremden Modulo Werte benötigt sondern einfach funktioniert. Die teilerfremden Modulo Werte hatte ich nur angeführt, weil damit die Lösung garantiert ist. Dass es bei nicht teilerfremden Modulo Werten zu Problemen kommen kann, hast Du gesehen und Du hast inzwischen auch eine Möglichkeit gefunden, zu zeigen, dass es für diese Aufgabe eine Lösung gibt. Also starten wir mal los:

x \equiv 56 (mod 135)

x \equiv 11 (mod 72)

Startwert

x = 56,

weil

56 \equiv 56 (mod 135)

x = 56 : 56 \equiv 56 (mod

72)⇒ kleinste zu addierende Zahl ist

135 \Rightarrow x = 56 + 135 = 191

x = 191 : 191 \equiv 47 (mod 72) \Rightarrow x = 191 + 135 = 326

x = 326 : 326 \equiv 38 (mod 72) \Rightarrow x = 326 + 135 = 461

Jetzt erkennt man bereits ein System:

56 - 9 = 47; 47 - 9 = 38

Es geht also weiter mit:

29, 20, 11

dazu gehören die Zahlen

x :

461, 461 + 1 \cdot 135, 461 + 2 \cdot 135

Die letzten Werte lösen die zweite Kongruenz, also löst

x = 461 + 2 \cdot 135 = 731

löst die Aufgabe.

Probe:

731 = 56 + 675 = 56 + 5 \cdot 135

731 = 11 + 720 = 11 + 10 \cdot 72

Ich weiß jetzt nicht um den Aufwand von MichaL's Lösung, aber den meiner Lösung halte ich für überschaubar.

anonymous

10:46 Uhr, 11.06.2011

OK, vielen Dank. Aber mir ist noch nicht ganz klar, wieso man nicht

x

kongr.

56 mod 135

zu
x≡11

(mod 15)

x≡11

(mod 72)

umschreiben darf.

135 = 9 \cdot 15

Einmal hätten wir

56 mod 9,

also

11 mod 9

zum anderen

11 mod 15

.
Diese beiden Kongruenzen müssen erfüllt sein, damit

56 mod 135

erfüllt ist.
Was habe ich falsch gemacht?

Bummerang

14:33 Uhr, 11.06.2011

Hallo,

"Was habe ich falsch gemacht?"

Nichts, man erhält dann die Lösung der "Dreierkongruenz"

x = 11

. Diese ist keine Lösung der Ausgangskongruenz, aber das habe ich bereits geschrieben. Man müßte einen "Nachloop" durchführen, der einerseits die 3 Kongruenzen unberührt läßt und andererseits die beiden Ausgangskongruenzen berücksichtigt. Ich fasse mal die notwendigen Aktivitäten zusammen:

1. ggT ermitteln
2. aus zwei Kongruenzen drei Kongruenzen machen
3. die drei Kongruenzen lösen
4. "Nachloop" (wie aufwändig der auch sei)?

Dagegen meine Version:

1. die zwei Kongruenzen lösen nach bekanntem Verfahren

Man hätte bei Deinem Vorgehen hier für den Fall, dass die Modulo Werte nicht teilerfremd sind, einen zusätzlichen Algorithmus ("Nachloop") zu finden und zu beherrschen. Außerdem muss man eine Dreierkongruenz lösen, die mit kleineren Modulo Werten sicher einfacher ist als eine Dreierkongruenz mit den gebenen Werten, und hier ergibt sich sogar gleich die Lösung

x = 11,

aber das ist eher Zufall und der Nachloop erfolgt sicher mit größeren Zahlen, mit Zahlen in der Größenordnung, mit denen man den Loop nach meiner Version schon gleich hätte durchzuführen. Demgegenüber steht der exakt gleiche Algorithmus ohne zusätzliches Wissen, Können,

u . s . w ., u . s . f

.Ich kann den Vorteil nicht erkennen, einen anderen Weg zu gehen.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

896294

896028

	Status: nicht eingeloggt	Noch nicht registriert?