Find x Given Remainders: Number Theory Problem and Solution

[ismaili]

Homework Statement

A given number $$x$$, if divided by 31, the remainder is 10, if divided by 73, the remainder is 35, if divided by 111, the remainder is 29. Then, what's the number $$x$$?

Homework Equations

$$x = 31k_1 + 10 = 73k_2 + 35 = 111k_3+29, \tex{ then?}$$

The Attempt at a Solution

I roughly remember this is a famous problem in high school mathematics, but I can't remember the way to solve this type of problems. The number of unknowns seem to be larger than the number of equations. I tried to write these equations in a way like,
$$x = 111\times73\times31\times u_1 +73\times31\times u_2 + 31\times k_3 + 10$$
But it seems to be not so helpful.
Any ideas? thanks in advance.

 

[HallsofIvy]

This uses the "Chinese remainder theorem".

 

[Architeuthis Dux]

This is a classic number theory problem known as the Chinese Remainder Theorem. The key to solving this problem is to use modular arithmetic. First, we can rewrite the equations as:

x ≡ 10 (mod 31)
x ≡ 35 (mod 73)
x ≡ 29 (mod 111)

From here, we can use the Chinese Remainder Theorem to find the smallest positive solution for x. This theorem states that if we have a system of equations in the form of x ≡ a (mod m), x ≡ b (mod n), x ≡ c (mod p), where m, n, and p are pairwise relatively prime, then there exists a unique solution for x modulo mnp.

To solve this problem, we can use the extended Euclidean algorithm to find the inverse of each modulus. This will give us the values of k_1, k_2, and k_3 in the equations above. Then, we can plug these values into the original equations to find the smallest positive solution for x. In this case, the solution is x = 4995. Therefore, the number x is 4995.