This problem from China is almost 2000 years old: Find a number that when divided by 3 gives a remainder of 2, when divided by 5 gives a remainder of 3, and when divided by 7 gives a remainder of 4.
Thank you so much for the help!
To solve this problem, we can use the method of Chinese Remainder Theorem. The Chinese Remainder Theorem states that given a set of simultaneous congruences, there exists a unique solution modulo the product of the moduli if the moduli are pairwise coprime.
In this case, we have three congruences:
1. x ≡ 2 (mod 3)
2. x ≡ 3 (mod 5)
3. x ≡ 4 (mod 7)
To find the solution, we first need to check if the moduli (3, 5, and 7) are pairwise coprime, which means that they have no common factors.
In this case, the moduli are pairwise coprime, so we can proceed with finding the solution.
Step 1: Calculate the product of the moduli:
M = 3 × 5 × 7 = 105
Step 2: Solve each congruence modulo its modulus:
For congruence 1 (x ≡ 2 (mod 3)):
- Multiply the other two moduli: 5 × 7 = 35
- Find the modular inverse of 35 modulo 3:
35⁻¹ ≡ 2 (mod 3)
- Multiply the modular inverse by the remainder: 2 × 35 × 2 ≡ 70 ≡ 2 (mod 3)
For congruence 2 (x ≡ 3 (mod 5)):
- Multiply the other two moduli: 3 × 7 = 21
- Find the modular inverse of 21 modulo 5:
21⁻¹ ≡ 1 (mod 5)
- Multiply the modular inverse by the remainder: 1 × 21 × 3 ≡ 63 ≡ 3 (mod 5)
For congruence 3 (x ≡ 4 (mod 7)):
- Multiply the other two moduli: 3 × 5 = 15
- Find the modular inverse of 15 modulo 7:
15⁻¹ ≡ 1 (mod 7)
- Multiply the modular inverse by the remainder: 1 × 15 × 4 ≡ 60 ≡ 4 (mod 7)
Step 3: Add up the solutions obtained from each congruence:
x = (2 × 35 × 2) + (3 × 21 × 1) + (4 × 15 × 4)
Simplifying the expression, we get:
x = 140 + 63 + 240
Adding up the numbers results in:
x = 443
Therefore, the solution to the problem is x = 443.
look up "Chinese Remainder Theorem"
and you will find many pages for this kind of problem
You will have to know how to do arithmetic in "modular arithmetic" , and this forum is not suitable to teach you that.
I just worked out the above problem using that method and got
263
If you have enough patience, here is another way to do that question which is very easy to understand:
divided by 3 gives a remainder of 1 :
4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 ..... 263
when divided by 5 gives a remainder of 4 :
4 9 14 19 24 29 34 39 43 49 53 59 ..... 263
when divided by 7 gives a remainder of 2 :
2 9 16 23 30 37 44 51 58 ...... 263
ignore the 2nd part of my answer to the above, the numbers don't even match. I cut and pasted from a previous solution but the numbers were not even the same
Also note that even though 263 is a solution, it is one of an infinite number. But it said to find "a number", so the answer of 263 is a correct answer.
If you want others, especially the smallest such number, proceed as follows
looking the the divisiors of 3, 5, and 7, we would have a LCM of 105
so 263 - 105 = 158 is another solution
158 - 105 = 53 is another, and the smallest.
the long and tedious way would be"
divided by 3 gives a remainder of 2 :
2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 ..... 263
when divided by 5 gives a remainder of 3 :
3 8 13 18 23 28 33 38 43 48 53 58 ..... 263
when divided by 7 gives a remainder of 4 :
4 11 18 25 32 39 46 53 60 ...... 263
notice that 53 is the first such number.