find the least positive integer that leaves a remainder of 1,2 and 3 when divided by 3,5 and 7
————————————————————————————————————
I am assuming you want the least n for n = 1 mod 3, n = 2 mod 5, and n = 3 mod 7.
—
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.)
—
Let n be the number.
Start with largest modulus and write as a regular equation:
n = 7j + 3 (1)
Next write that equation in terms of the next-highest modulus :
7j + 3 = 2 mod 5
7j = -1 mod 5
7j = 4 mod 5 (-1 and 4 are the same, mod 5)
Solve for j:
j = 2 mod 5 ( find this by listing multiples of 7: 7, 14, 21, etc, look for the one that gives remainder 4
when divided by 5)
Re-write as equation:
j = 5k + 2 (2)
Now substitute for j from (2) into (1):
n = 7(5k + 2) + 3
n = 35k + 17 (3)
Finally, write (3) as a congruence for the 3rd modulus:
35k + 17 = 1 mod 3
35k = -16 mod 3
35k = 2 mod 3
Solve for k:
k = 1 mod 3
Re-write as regular equation:
k = 3m + 1 (4)
Substitute for k from (4) into (3):
n = 35(3m+1) + 17
n = 105m + 52
So n = 52 mod 105 and 52 is the answer.
—
Ans:
—
Check:
x mod 3 = 1: 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, ...
x mod 5 = 2: 2, 7, 12, 17, 22, 27, 32, 37, 42, 47, 52, 57, 62, …
x mod 7 = 3: 3, 10, 17, 24, 31, 38, 45, 52, 59, 66, …
We can see that 52 is the smallest number that appears on all 3 lists.