+0  
 
+1
177
1
avatar+545 

Find the least positive four-digit solution to the following system of congruences. 

\(\begin{align*} 7x &\equiv 21 \pmod{14} \\ 2x+13 &\equiv 16 \pmod{9} \\ -2x+1 &\equiv x \pmod{25} \\ \end{align*}\)

 Jul 22, 2019
 #1
avatar
0

After a slight re-arrangement, the congruences look like this:
x mod 2 = 1
x mod 9 = 6
x mod 25 = 17
Using "Chinese remainder theorem" + "Modular multiplicative inverse", which are included in this short computer code:
 x = 450 m +  267,where m=0, 1, 2, 3......etc.
i=0;j=0;m=0;t=0;a=(2 9, 25);r= (1, 6, 17);c=lcm(a); d=c / a[i];n=d % a[i] ;loop1:m++; if(n*m % a[i] ==1, goto loop, goto loop1);loop:s=(c/a[i]*r[j]*m);i++;j++;t=t+s;m=0;if(i< count a, goto4,m=m);printc,"m + ",t % c;return.
So, the smallest 4-digit value for x =[450 x 2] + 267 =1,167.

 Jul 22, 2019
edited by Guest  Jul 22, 2019

36 Online Users

avatar
avatar
avatar