document.write( "Question 1089879: find the least positive integer that leaves a remainder of 1,2 and 3 when divided by 3,5 and 7 \n" ); document.write( "
Algebra.Com's Answer #704244 by math_helper(2461)\"\" \"About 
You can put this solution on YOUR website!
find the least positive integer that leaves a remainder of 1,2 and 3 when divided by 3,5 and 7
\n" ); document.write( "————————————————————————————————————\r
\n" ); document.write( "\n" ); document.write( "I am assuming you want the least n for n = 1 mod 3, n = 2 mod 5, and n = 3 mod 7.
\n" ); document.write( "—\r
\n" ); document.write( "\n" ); document.write( "One way to solve it is to apply the Chinese Remainder Theorem (see https://brilliant.org/wiki/chinese-remainder-theorem/ for a description on how it works. It even has an example similar to this problem.)
\n" ); document.write( "—
\n" ); document.write( "
\r\n" );
document.write( "Let n be the number.\r\n" );
document.write( "\r\n" );
document.write( "Start with largest modulus and write as a regular equation:\r\n" );
document.write( "n = 7j + 3     (1)\r\n" );
document.write( "\r\n" );
document.write( "Next write that equation in terms of the next-highest modulus :  \r\n" );
document.write( "7j + 3 = 2 mod 5\r\n" );
document.write( "7j = -1 mod 5 \r\n" );
document.write( "7j = 4 mod 5     (-1 and 4 are the same, mod 5)\r\n" );
document.write( "\r\n" );
document.write( "Solve for j:   \r\n" );
document.write( "  j = 2 mod 5   ( find this by listing multiples of 7:  7, 14, 21, etc, look for the one that gives remainder 4 \r\n" );
document.write( "                          when divided by 5)\r\n" );
document.write( "\r\n" );
document.write( "Re-write as equation: \r\n" );
document.write( "   j = 5k + 2    (2)\r\n" );
document.write( "\r\n" );
document.write( "Now substitute  for j from (2)  into (1):\r\n" );
document.write( "   n = 7(5k + 2) + 3     \r\n" );
document.write( "   n = 35k + 17        (3)\r\n" );
document.write( "\r\n" );
document.write( "Finally, write (3) as a congruence for the 3rd modulus:\r\n" );
document.write( "\r\n" );
document.write( "     35k + 17  = 1 mod 3\r\n" );
document.write( "        35k = -16 mod 3\r\n" );
document.write( "        35k = 2 mod 3\r\n" );
document.write( "\r\n" );
document.write( "Solve for k:\r\n" );
document.write( "        k = 1 mod 3 \r\n" );
document.write( " \r\n" );
document.write( "Re-write as regular equation:\r\n" );
document.write( "         k = 3m + 1     (4)\r\n" );
document.write( "\r\n" );
document.write( "Substitute for k from (4) into (3):\r\n" );
document.write( "            \r\n" );
document.write( "          n = 35(3m+1) + 17\r\n" );
document.write( "          n = 105m + 52\r\n" );
document.write( "  \r\n" );
document.write( "So  n = 52 mod 105    and 52 is the answer.\r\n" );
document.write( "

\n" ); document.write( "—
\n" ); document.write( "Ans: \"+highlight%2852%29+\"
\n" ); document.write( "—\r
\n" ); document.write( "\n" ); document.write( "

\n" );
document.write( "Check: \r
\n" );
document.write( "\n" );
document.write( "  x mod 3 = 1:   1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49,  52, 55, 58, ...
\n" );
document.write( "  x mod 5 = 2:   2, 7, 12, 17, 22, 27, 32, 37, 42, 47, 52, 57, 62, …
\n" );
document.write( "  x mod 7 = 3:   3, 10, 17, 24, 31, 38, 45, 52, 59, 66, …
\n" );
document.write( " 
\n" );
document.write( "We can see that 52 is the smallest number that appears on all 3 lists.\r
\n" );
document.write( "
\n" );
document.write( "
\n" );
document.write( "
\n" );
document.write( "
\n" );
document.write( "\n" );
document.write( " \n" );
document.write( "
\n" );