Chinesischer Restsatz Teilerfremd

02.06.2023, 14:54

Skydiverin

Chinesischer Restsatz Teilerfremd

Meine Frage:
0?x<1053, x=22mod27, x=16mod39

Lösen Sie die folgende Gleichung (chinesischer Restsatz)

Hallo, kann mir jemand von euch hierbei helfen? Ich hatte bislang noch nie, dass der ggT nicht 1 ist.. man kann das wohl errechnen, indem man die eine Gleichung nimmt und in die andere einsetzt und umformt, aber leider funktioniert das bei mir nicht?

Meine Ideen:

Das war mein Ansatz:

? = 22 + 27k ? 22 + 27k = 16 (mod 39)
j = 16 (mod 39)
j = 39k + 16
? = 22*(39k +16) + 2727
? = 858 + 379

02.06.2023, 16:43

HAL 9000

Auf diesen Beitrag antworten »

Man kann das ganze teilerfremd machen, indem man jede Kongruenz nach Primfaktormodulen zerlegt:

$\begin{eqnarray*} x\equiv 22\bmod 3^3\quad (1) \end{eqnarray*}$ ist bereits ein Primfaktormodul.

$\begin{eqnarray*} x\equiv 16\bmod 39\quad (2) \end{eqnarray*}$ ist äquivalent zum gleichzeitigen Bestehen von

$\begin{eqnarray*} x\equiv 16\bmod 3 \end{eqnarray*}$ , vereinfacht $\begin{eqnarray*} x\equiv 1\bmod 3\quad (2A) \end{eqnarray*}$
$\begin{eqnarray*} x\equiv 16\bmod 13 \end{eqnarray*}$ , vereinfacht $\begin{eqnarray*} x\equiv 3\bmod 13\quad (2B) \end{eqnarray*}$ .

Anschließend muss geprüft werden, ob die ganzen Kongruenzen modulo $\begin{eqnarray*} p^n \end{eqnarray*}$ mit gleicher Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ aber ggfs. unterschiedlichen Exponenten $\begin{eqnarray*} n \end{eqnarray*}$ miteinander konform sind: Dabei geht man von dem höchsten Exponenten aus und "arbeitet" sich nach unten:

Aus (1) folgt $\begin{eqnarray*} x\equiv 22\equiv 1\bmod 3 \end{eqnarray*}$ , geht mit (2A) konform. (Hätte man hier jetzt was anderes als 1 rausbekommen, dann wäre das System unlösbar gewesen!)

Das bedeutet, dass (2A) automatisch durch (1) erfüllt ist. Was jetzt also zu lösen ist, ist das Kongruenzsystem (1)(2B), welches nun aber aus teilerfremden Modulen besteht, im Gegensatz zum Ausgangssystem (1)(2).

P.S.: Ist nicht unbedingt immer die effizienteste Methode, insbesondere bei Modulen mit sehr vielen verschiedenen Primteilern ist es nicht unbedingt nötig, immer derart vorzugehen. Aber zumindest ist es eine sichere Methode. Augenzwinkern

====================================================

Dein Ansatz funktioniert auch, natürlich muss man dann richtig weiter vorgehen:

$\begin{eqnarray*} x=22+27k \end{eqnarray*}$ in die andere Kongruenz eingesetzt ergibt

$\begin{eqnarray*} 22+27k\equiv 16\bmod 39 \end{eqnarray*}$ .

$\begin{eqnarray*} 27k\equiv -6\bmod 39 \end{eqnarray*}$ , die gesamte Kongruenz dividiert durch 3 ergibt das

$\begin{eqnarray*} 9k\equiv -2\bmod 13 \end{eqnarray*}$ , mit Lösung $\begin{eqnarray*} k\equiv 7\bmod 13 \end{eqnarray*}$ .

Ergibt rückwärts eingesetzt $\begin{eqnarray*} x\equiv 211\bmod 351 \end{eqnarray*}$ .

03.06.2023, 07:11

Skydiverin

Auf diesen Beitrag antworten »

Ok danke, aber wie kommst du auf 27 k = -6 mod 39 und auf die Lösung mit k = 7 mod 13? Und was bedeutet rückwärts eingesetzt? Bin leider totaler Anfänger bei sowas

03.06.2023, 08:57

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Skydiverin
Und was bedeutet rückwärts eingesetzt? Bin leider totaler Anfänger bei sowas

Herrje, was soll es denn schon bedeuten??? Wenn man $\begin{eqnarray*} x=22+27k \end{eqnarray*}$ links in $\begin{eqnarray*} x\equiv 16\bmod 39 \end{eqnarray*}$ einsetzt, dann kommt da eben $\begin{eqnarray*} 22+27k\equiv 15\bmod 39 \end{eqnarray*}$ raus. Muss ich denn zu jedem primitiven Schritt so einen Roman schreiben - da kann man auch mal selbst drauf kommen. unglücklich

Zitat:

Original von Skydiverin
Ok danke, aber wie kommst du auf 27 k = -6 mod 39 und auf die Lösung mit k = 7 mod 13?

Also ich wollte jetzt nicht zum Urschleim zurückgehen: Wenn du Systeme linearer Kongruenzen bearbeitest gehe ich einfach mal davon aus, dass du einfache lineare Kongruenzen vom Typ $\begin{eqnarray*} ax\equiv b\bmod m \end{eqnarray*}$ lösen kannst.

03.06.2023, 14:55

Skydiverin

Auf diesen Beitrag antworten »

Danke, aber hab ich bis lang noch nie gelöst. Werde mich mal einlesen in das Thema

Neue Frage »

Antworten »

Chinesischer Restsatz Teilerfremd

Verwandte Themen