Modular Math

Using Chinese Remainder Theorem plus Modular Multiplicative Inverse, which are incorporated into this short computer code, we get the following:

i=0;j=0;m=0;t=0;a=(3, 5, 7,11, 13, 17, 19);r= (1, 2, 3, 4, 5, 6, 7);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

The above code readily gives: 4849845 m +  4383592 as the answer. The smaller N=4,383,592. The larger N=4,383,592 + [1*4,849,845 - which is the LCM of 3, 5, 7, 11, 13, 17, 19] =9,233,437.

There are two 7-digit integers that satisfy the following congruences:
N mod 3=1, N mod 5 =2, N mod 7 =3, N mod 11 =4, N mod 13 =5, N mod 17 =6 and N mod 19 =7.
What are the two 7-digit integers?

\(\begin{array}{|lrcll|} \hline (1) & N &\equiv& 1 \pmod{3} \\ (2) & N &\equiv& 2 \pmod{5} \\ (3) & N &\equiv& 3 \pmod{7} \\ (4) & N &\equiv& 4 \pmod{11} \\ (5) & N &\equiv& 5 \pmod{13} \\ (6) & N &\equiv& 6 \pmod{17} \\ (7) & N &\equiv& 7 \pmod{19} \\ \hline \end{array}\)

\(\begin{array}{|rcll|} \hline \left. \begin{array}{c} (1) & N &\equiv& 1 \pmod{3} \\ (7) & N &\equiv& 7 \pmod{19}\end{array} \right\}&(8)& N &\equiv& 7 \pmod{57} \\ \\ \left. \begin{array}{c} (3) & N &\equiv& 3 \pmod{7} \\(5) & N &\equiv& 5 \pmod{13}\end{array} \right\}&(9)& N &\equiv& 31 \pmod{91} \\ \\ \left. \begin{array}{c} (2) & N &\equiv& 2 \pmod{5} \\(4) & N &\equiv& 4 \pmod{11}\end{array} \right\}&(10)& N &\equiv& 37 \pmod{55} \\ \\ &(6)& N &\equiv& 6 \pmod{17} \\ \hline \end{array}\)

\(\begin{array}{|rcll|} \hline \left. \begin{array}{c}(8) & N &\equiv& 7 \pmod{57} \\ (9) & N &\equiv& 31 \pmod{91}\end{array} \right\}&(11)& N &\equiv& 577 \pmod{5187} \\ \\ \left. \begin{array}{c} (10) & N &\equiv& 37 \pmod{55} \\(6)& N &\equiv& 6 \pmod{17} \end{array} \right\}&(12)& N &\equiv& 312 \pmod{935} \\ \hline \end{array}\)

\(\begin{array}{|rcll|} \hline \left. \begin{array}{c}(11)& N &\equiv& 577 \pmod{5187} \\ (12)& N &\equiv& 312 \pmod{935}\end{array} \right\}&(13)& \mathbf{N} &\equiv& \mathbf{4383592 \pmod{4849845}} \\ \hline \end{array}\)

The two 7-digit integers are  4383592 and 4383592 + 4849845 = 9233437

Example:

\((1)\ N \equiv 1 \pmod{3} \\ (7)\ N \equiv 7 \pmod{19} \)

\(\begin{array}{|rcll|} \hline \left. \begin{array}{c} (1) & N &\equiv& 1 \pmod{3} \\ (7) & N &\equiv& 7 \pmod{19}\end{array} \right\} \begin{array}{c} & N-1 = 3a \quad a\in \mathbb{Z} \\ & N-7 =19b \quad b\in \mathbb{Z} \end{array} \\ \hline \\ \begin{array}{rclrcl} (N-1) - (N-7) &=& 3a-19b \\ 6 &=& 3a-19b \\ 3a &=& 6+19b \\ a &=& \dfrac{6+18b+b}{3} \\ a &=& 2+6b+\underbrace{\dfrac{b}{3}}_{=c} \\ a &=& 2+6b+c & c&=&\dfrac{b}{3} \quad c\in \mathbb{Z} \\ && & 3c &=&b \\ && & \mathbf{b} &=& \mathbf{3c} \\ a &=& 2+6(3c)+c \\ a &=& 2+18c+c \\ \mathbf{a} &=& \mathbf{2+19c} \\\\ N-1 &=& 3a \\ N-1 &=& 3(2+19c) \\ N-1 &=& 6 + 57c \\ N &=& 7+57c \\ \mathbf{N} &\equiv& \mathbf{7 \pmod{57}} \\ \end{array} \\ \hline \end{array}\)