simultaneous linear congruences- Chinese remainder theorem

40 Views Asked by At
   T ≡ 126 mod 1293
   T ≡ 0 mod 3936

hi ive tried to solve this using the CRT existence constructive proof but 1293*207 + 3936*-68 =3 then i used x = (a1*m1*n1) + (a2*m2*n2) and (0*1293*207) + (126*3936*-68) i checked the solution and answer was wrong so im not sure what to do from here

1

There are 1 best solutions below

2
On BEST ANSWER

$3\mid T\ $ so it's equivalent to $\ T/3\equiv 42\pmod{431};\,\ T/3\equiv 0\pmod{1312},\ $ with solution

$\ T/3 \equiv \color{}{42\cdot 1312} (1312^{-1}\bmod 431)\equiv \color{#c00}{42\cdot 1312}(-68)\equiv 211232\pmod{\ \ 431\cdot 1312}$

Scaling the prior comgruence by $3$ yields the solution: $\ T \equiv 633696\pmod{1293\cdot 1312}$

Your mistake is that you effectively scaled twice by $3$ instead of once as above, i.e. you multiplied both $\,\color{#c00}{42}\,$ and $\,\color{#c00}{1312}\,$ by $3$ in your formula $\, \color{#c00}{126\cdot 3936}(-68).\,$