423x ≡ 9 mod 483
bedeutet doch, es gibt ein k mit
423x ≡ 9 + k*483 Da alles durch 3 geht
141*x = 3 + k*161
<=> 141*x - k*161 = 3
mit dem erweiterten euklid. Algorithmus bestimmst
du y und n mit (geht wegen ggT(141;161)=1 )
141*y - n*161 = 1 und bekommst y=8 und n=7 also
141*8 - 7*161 = 1 alles mal 3 gibt
141*24 - 21*161 = 3
und 24 ist das gesuchte x.
Probe 423*24 - 21*483 = 9 also 423*24 Ξ 9 mod 483
