N is a four-digit positive integer. Dividing N by 9 , the remainder is 5. Dividing N by 7, the remainder is 3. Dividing N by 5, the remainder is 1. What is the smallest possible value of N?
Using Chinese Remainder Theorem + Modular Multiplicative Inverse, which are incorporated in this computer code, we have:
i=0;j=0;m=0;t=0;a=(9, 7, 5);r= (5, 3, 1);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
315 m + 311, where m=0, 1, 2, 3.......etc.
The smallest 4-digit integer =[315 * 3 + 311] =1,256