Kongruenzensystem

Hallo,

mal eine Frage, wie löst man folgendes Kongruenzensystem?

13x ≡ 4 mod 99
15x ≡ 56 mod 101

Hat jemand eine Idee?

knivil

Probieren [7471, 17470, 27469, 37468,..

mit dem chinesischen Restsatz.

volkard

Ich habs mal so versucht (bestimmt nicht elegant):

13x ≡ 4 mod 99 | *61
15x ≡ 56 mod 101 | *27

(an die Zahlen 61 und 27 kommt man mit dem erweiterten Euklidischen Algorithmus)
http://www2-fs.informatik.uni-tuebingen.de/~reinhard/krypto/German/2.2.d.html

793x ≡ 244 mod 99
405x ≡ 1512 mod 101

x ≡ 26 mod 99
x ≡ -3 mod 101

x=26+a99
x=-3+b101

26+a*99=-3+b*101
29+99a=101b
99a=101b-29

101b-29 ≡ 0 mod 99
101b ≡ 29 mod 99
2b ≡ 29 mod 99 | *50
100b ≡ 1450 mod 99
b ≡ 64 mod 99

b=64+n*99

x=-3+b*101

x=-3+(64+n*99)*101
x=-3+6464+9999n
x=6461+9999n

Und irgendwie auch nicht knivils Lösung, aber irgendwie dicht dran. Hoffentlich nur ein kleines Rechenfehlerchen.

Allgemeine Lösung des Systems x ≡ a_i (mod m_i), m_i teilerfremd:

x = summe(i=1 bis n) über [Produkt(j != i)m_i](x[Produkt(j != i)m_i]^{-1} mod m_i]