Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Wie berechnet man Lineare Kongruenz

Wie berechnet man Lineare Kongruenz

Universität / Fachhochschule

Ringe

Tags: chinesischer Restsatz, Kongruenz, Lineare Kongruenz

Erpick aktiv_icon

09:34 Uhr, 31.07.2022

Guten tag,
Ich lerne gerade für Klausuren.
Ich habe gerade jedoch Probleme mit dem ausrechnen.

Als Beispiel habe ich

x = 1 mod 5
x = 6 mod 11
x = 2 mod 7

Könnte mir jemand erklären wie man das hier ausrechnet?

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.)

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Dreiecke und Kongruenz

michaL aktiv_icon

10:16 Uhr, 31.07.2022

Hallo,

es gibt eine abkürzende Formel, die ich aber nie auswendig gelernt habe. Man kann da nach dem chinesischen Restsatz

^{[1]}

suchen.

Letztlich steckt hinter dem Satz aber nur das Verfahren, das ich hier kurz am deinem Beispiel bearbeiten möchte:
Wichtigster Gedanke: Es werden zwei Kongruenzen zu einer zusammengefasst.

Wir machen das mal mit den beiden ersten:

x \equiv 2

mod 7.......(1)

x \equiv 6

mod 11.....(2)

Wenn der ggT(7;11) ein Teiler der Differenz

6 - 2

ist (hier gegeben), dann lassen sich die Kongruenzen zusammenfassen. Sonst nicht!

Gleichung (1) bedeutet ja, dass es ein

k

(ganze Zahl; wir bewegen uns hier ausschließlich im Bereich

ℤ

) gibt, sodass

x = 7 k + 2

.
(2) bedeutet, es gibt ein

m

, sodass

x = 11 m + 6

.
Zusammengefasst gilt also (insbesondere):

11 m + 6 = 7 k + 2 \overset{}{\Leftrightarrow} 4 = 7 k - 11 m

. (3)

Da ggT(7;11) ist gemäß erweitertem euklidischem Algorithmus als

ℤ

-Linearkombination von 7 und 11 darstellbar, d.h. es gibt

p, q

, sodass

7 p + 11 q = 1 = ggT (7; 11)

gilt.
Wie gesagt: Man kann

p, q

über den erweiterten euklidischen Algorithmus suchen und finden.
Hier geht es mit Probieren mindestens ebenso schnell, da

22 - 21 = 1 \overset{}{\Leftrightarrow} - 3 \cdot 7 + 2 \cdot 11 = 1

gilt. Man kann also (Vorsicht, die sogenannten Bézoutkoeffizienten

^{[2]}

p

und

q

sind nicht eindeutig! Es gilt ja

11 \cdot 7 + (- 7) \cdot 11 = 0

, sodass man eine Lösung so verändern kann, dass der eine Koeffizient um 11 erhöht und der andere um 7 verringert wird, ohne, dass die Lösungseigenschaft verloren ginge.)

p = - 3

q = 2

wählen.

Damit ergibt sich aus (3):

7 k - 11 m = 4 \cdot 1 = 4 \cdot (- 3 \cdot 7 + 2 \cdot 11) = - 12 \cdot 7 + 8 \cdot 11 \overset{}{\Leftrightarrow} 7 (k + 12) = 11 (m + 8)

(4)

(4) ist nun die Schlüsselgleichung. Sie ist genau dann lösbar, wenn gleichzeitig

k + 12

ein Vielfaches von 11 und

m + 8

ein Vielfaches von 7 ist, d.h. wenn es ein

v

gibt, sodass

k + 12 = 11 v

...(5) und

m + 8 = 7 v

....(6) gilt.

Setze (5) in

x = 7 k + 2

ein (oder (6) in

x = 11 m + 6

), so erhält man

x = 7 (11 v - 12) + 2 = 77 v - 82

.

Diese Gleichung ist äquivalent zur Kongruenz

x \equiv - 82

mod 77 bzw, wenn du nicht negative Zahlen bevorzugst:

x \equiv 72

mod 77....(7)

(Beachte, dass (7) mod 7 betrachtet, genau wieder (1) ergibt und mod 11 gerade wieder (2)!)

Fazit: Die beiden Konguenzen

x \equiv 2

mod 7.......(1)

x \equiv 6

mod 11.....(2)

lassen sich zusammenfassen zur Kongruenz

x \equiv 72

mod 77....(7)

Nächster Schritt: Fasse (7) mit der verbleibenden Kongruenz zusammen.

Mfg Michael

EDIT:
Weblinks:
[1] de.wikipedia.org/wiki/Chinesischer_Restsatz#Simultane_Kongruenzen_ganzer_Zahlen
[2] de.wikipedia.org/wiki/Lemma_von_B%C3%A9zout

HAL9000

12:55 Uhr, 01.08.2022

> Hier geht es mit Probieren mindestens ebenso schnell,

Das greife ich mal als Stichwort für die gesamte Aufgabe auf. Ein solches System kann man auch als Abfolge mehrerer einfacher linearer Kongruenzen mit je einer Variable begreifen. Die kann man natürlich gemäß Lehrbuch mit EEA lösen, bei kleinen Modulen wie hier aber i.d.R. schneller durch Probieren der wenigen Möglichkeiten:

x \equiv 1 mod 5

heißt, es existiert

a \in ℤ

mit

x = 5 a + 1

.

In

x \equiv 6 mod 11

eingesetzt bedeutet das

5 a + 1 \equiv 6 mod 11

bzw.

5 a \equiv 5 mod 11

mit offensichtlicher Lösung

a \equiv 1 mod 11

, damit existiert

b \in ℤ

mit

a = 11 b + 1

und somit

x = 55 b + 6

.

Dies wiederum in

x \equiv 2 mod 7

eingesetzt ergibt

55 b + 6 \equiv 2 mod 7

, also

6 b \equiv - 4 mod 7

. Probieren heißt nun, man addiert solange 7 zur -4, bis man was durch 6 teilbares rauskriegt: -4, 3, 10, 17, 24. Damit haben wir

6 b \equiv 24 mod 7

und somit

b \equiv 4 mod 7

. (noch schneller hätte das direkt aus

- b \equiv - 4 mod 7

gefolgert werden können). Das macht

b = 7 c + 4

mit

c \in ℤ

und damit schlussendlich

x = 385 c + 226

oder anders geschrieben

x \equiv 226 mod 385

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

1559249

1559207

	Status: nicht eingeloggt	Noch nicht registriert?