+0  
 
0
35
1
avatar+60 

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?

 Oct 3, 2020
 #1
avatar
0

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.

 Oct 3, 2020

16 Online Users

avatar
avatar