Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Wie löse ich das simultane Kongruenzsystem?

Wie löse ich das simultane Kongruenzsystem?

Universität / Fachhochschule

Algebraische Zahlentheorie

Tags: chinesischer Restsatz, Kongruenz, Lineare Kongruenz, Lösbarkeit, simultan, teilerfremd, Zahlentheorie

matura16 aktiv_icon

16:22 Uhr, 05.12.2021

Es geht um das folgende Beispiel (siehe Bild)

Mein Problem:

1)

die Module sind nicht teilerfremd. Wie kann ich das simultane Kongruenzsystem nun lösen?

2)

darf ich für a nicht alle ganzen Zahlen einsetzen da 1 alle a teilen wird?

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

Hierzu passend bei OnlineMathe:

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

Dreiecke und Kongruenz

michaL aktiv_icon

17:56 Uhr, 05.12.2021

Hallo,

die Teilerfremdheit ist nur hinreichend, nicht aber notwendig.

Vorab: Es gibt auch eine Formel für simultane Kongruenzen, die zu lernen ich aber nie die Notwendigkeit hatte.

Da 7 aber sowohl zu 8 als auch zu 10, und erst recht zu deren gemeinsamen Vielfachen teilerfremd ist, lohnt es sich, die "problematischen" Kongruenzen zunächst gemeinsam zu betrachten.

Es gilt also

x \equiv a

mod 8

x \equiv 7

mod 10

Ich finde es vernünftig, diese Schreibweise zurückzuführen auf eine Gleichung ganzer Zahlen:

x \equiv a

mod 8 bedeutet: es gibt

u

mit

x - a = 8 u \overset{}{\Leftrightarrow} x = a + 8 u

x \equiv 7

mod 10:

x = 7 + 10 v

für ein

v

Zusammengefasst führt das zu

a + 8 u = x = 7 + 10 v

bzw. (da

x

nicht relevant ist)

a + 8 u = 7 + 10 v \overset{}{\Leftrightarrow} 7 - a = 8 u - 10 v = 2 (4 u - 5 v)

.
Insbesondere sieht man hier, dass

a

ungerade sein muss, damit die linke Seite

7 - a

ebenfalls (wie die rechte Seite) durch 2 teilbar ist.
Dass die nicht nur notwendig, sondern auch hinreichend ist, rechne ich dir gern mal für

a = 1

mal vor:

Wir sind also bei

6 = 7 - 1 = 2 \cdot (4 u - 5 v)

angekommen, was sich zu

3 = 4 u - 5 v

vereinfachen lässt.
Da sich 3 relativ leicht als

3 = 2 \cdot 4 - 5

darstellen lässt, wird daraus die Gleichung:

2 \cdot 4 - 5 = 4 u - 5 v \overset{}{\Leftrightarrow} (v - 1) 5 = (u - 2) 4

Da nun 4 und 5 teilerfremd sind, muss gelten:

4 ∣ v - 1

, etwa

v - 1 = 4 k \overset{}{\Leftrightarrow} v = 1 + 4 k

und

5 ∣ u - 2

, etwa

u - 2 = 5 k \overset{}{\Leftrightarrow} u = 2 + 5 k

. (Ja, das gleiche

k

. Rechne nach, dass die Gleichung dann erfüllt ist.)

Insbesondere gilt dann (Eine der beiden Gleichungen für

x

oben einsetzen. Am besten: In beide und sehen, worauf das hinaus läuft!)

x = 7 + 10 (1 + 4 k) = 17 + 40 k

x = 1 + 8 (2 + 5 k) = 17 + 40 k

Beide Gleichungen bedeuten also, dass

x \equiv 17

mod 40.
Beachte: 40 ist das kgV von 8 und 10.
Die Lösung ist für

a = 1

berechnet.

Soll heißen:
Die simultanen Kongruenzen

x \equiv 1

mod 8

x \equiv 7

mod 10
lassen sich zu

x \equiv 17

mod 40 vereinfachen.

Lerne: Zwei simultane Kongruenzen

x \equiv a

mod

m

x \equiv b

mod

n

lassen sich genau dann zusammenfassen, wenn

ggT (m, n) ∣ (a - b)

gilt.

Mfg Michael

HAL9000

12:48 Uhr, 06.12.2021

Betrachten wir erstmal nur die Frage, ob ein solches Lineares Kongruenzsystem mit nicht paarweise teilerfremden Modulen überhaupt Lösungen hat.

Da gibt es verschiedene Zugänge, wobei die "systematischen" dann nicht unbedingt die kürzesten sind - eher im Gegenteil. Ein solcher systematischer Zugang wäre z.B., alle Kongruenzen auf bloße Kongruenzen mit Primzahlpotenzmodulen zurückzuführen. Im vorliegenden Fall betrifft das Modul

10 = 2 \cdot 5

, die anderen bleiben ungeschoren. Insgesamt werden auf diese Weise aus drei Kongruenzen dann vier:

x \equiv a mod 2^{3} (1)

x \equiv 1 mod 7 (2)

x \equiv 7 mod 2 (3_{1})

x \equiv 7 mod 5 (3_{2})

Und nun schauen wir nach Primzahlüberschneidungen in den Gleichungen: Da sehen wir

(1)

und

(3_{1})

hinsichtlich Primzahl 2. Die erste dieser Kongruenzen modulo 2 betrachtet und der anderen gleichgesetzt ergibt dann die Bedingung

a \equiv 1 mod 2

für die Lösbarkeit, d.h.

a

ungerade.

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

Wie es mit unsystematischen, pragmatischen Vorgehen schneller gehen kann, zeigt dieser ganz anders angelegte Weg:

x \equiv 7 mod 10

heißt

x = 10 u + 7

für irgendeine ganze Zahl

u

, dies in

x \equiv 1 mod 7

eingesetzt bekommt man

3 u \equiv 1 \equiv 15 mod 7

, d.h.

u \equiv 5 mod 7

bzw. eben

u = 7 v + 5

und somit

x = 70 v + 57

, was wiederum

x \equiv - 2 v + 1 \equiv a mod 8

bedeutet. D.h., für

v = 4 w + r

mit

r = 0, 1, 2, 3

bekommt man Lösungen für

a \equiv 1, 7, 5, 3 mod 8

respektive, und diese Lösungen sind

x = 280 w + 70 r + 56

oder als Kongruenz geschrieben

x \equiv 70 r + 57 mod 280

. Das ist (i) und (ii) in einem Aufwasch.

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

1546542

1546486

	Status: nicht eingeloggt	Noch nicht registriert?