Chinesischer Restsatz?

Question

Hallo,
ich komme ab dem Punkt "multiplikative Inversen" nicht mehr weiter. Wie berechne ich M1, M2 und M3? Ich habe zwar die Lösungen, aber ich weiß nicht, wie man drauf kommt...

Also ich habe folgendes:
2 * M1^(−1) = 1 (mod 3)       => M1^(−1) = 2
5 * M2^(−1) = 1 (mod 7)       => M2^(−1) = 3
10 * M3^(−1) = 1 (mod 11)   => M3^(−1) = 10

Über eine Antwort würde ich mich freuen.

Vielen Dank.

Robert · Accepted Answer

Im folgenden wird der Unterstrich zur Trennung der Daten benutzt.

Berechnung M1^(-1)

a_b_q_s_t
2_3_0_-1_1
3_2_1_1_-1
2_1_0_0_1
1_0_#_1_0

s * a + t * b = 1
(-1) * 2 + 1 * 3 = 1

(b+s) * a + (t-a) * b = 1
(3-1) * 2 + (1-2) * 3 = 1
2 * 2 + (-1) * 3 = 1

M1^(-1) = s = 2

Berechnung M2^(-1)

a_b_q_s_t
5_7_0_3_-2
7_5_1_-2_3
5_2_2_1_-2
2_1_2_0_1
1_0_#_1_0

s * a + t * b = 1
3 * 5 + (-2) * 7 = 1

M2^(-1) = s = 3

Berechnung M3^(-1)

a_b_q_s_t
10_11_0_-1_1
11_10_1_1_-1
10_1_10_0_1
1_0_#_1_0

s * a + t * b = 1
(-1) * 10 + 1 * 11 = 1

(b+s) * a + (t-a) * b = 1
(11-1) * 10 + (1-10) * 11 = 1
10 * 10 + (-9) * 11 = 1

M3^(-1) = s = 10

Chinesischer Restsatz?

1 Antwort