+149 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:
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
N = 315 m + 311, where m =0, 1, 2, 3.......etc. And since they want "4-digit positive integer", then:
N =[315 * 3] + 311 =945 + 311 =1,256, which is the answer.
