Discrete Math : History, Appearance and Application of Chinese Remainder Theorem in Chinese and Hindu Writings

1. Describe the history of the Chinese Remainder Theorem. Describe some of the relevant problems posed in Chinese and Hindu writings and how the Chinese Remainder Theorem applies to them. Please show references.

Solution Preview

According to D.Wells, the following problem was posed by Sun Tsu Suan-Ching (4th century AD):
There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number?

Oystein Ore mentions another puzzle with a dramatic element from Brahma-Sphuta-Siddhanta (Brahma's Correct System) by Brahmagupta (born 598 AD):
An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?

Problems of this kind are all examples of what universally became known as the Chinese Remainder Theorem. In mathematical parlance the problems can be stated as finding n, given its remainders of division by several numbers m1, m2, ..., mk:
n = n1 (mod m1)
n = n2 (mod m2)
...
n = nk (mod mk)

The modern day theorem is best stated with a couple of useful notations. For non-negative integers m1, m2, ..., mk, their greatest common divisor is ...

Solution Summary

History, Appearance and Application of Chinese Remainder Theorem in Chinese and Hindu Writings is discussed. The solution is detailed and well presented.

I would appreciate it if someone could provide the solutions to QB5 of the attatched exam paper.
Please see the attached file for the fully formatted problems.
B5.
(a) (1) State and prove the ChineseRemainderTheorem.
(ii) Find the 2 smallest positive integer solutions of the simultaneous set of congruence equations:
2x

Solve the egg problem used to illustrate the ChineseRemainderTheorem if the remainders on division by 2,3,4,5,6 and 7 are all 1 by
(i) the given procedure (ii) the "easier" way
(i) the given procedure
X=1(Mod2)
X=1(Mod3)
X=1(Mod4)
X=1(Mod5)
X=1(Mod6)
X=1(Mod7)
If andand then . We will use this r

I need help to writing a program "VC++.net"with the specified input and output.
Please, Implement the ChineseRemainderTheorem. Allowing at least 3 pairwise relatively prime positive integers.
Please attention
This program must run in the Visual C++.NET. Some time I have problem with that, so, please the whole project in

I need help to writing a program "VC++.net"with the specified input and output.
Please, Implement the ChineseRemainderTheorem. Allowing at least 3 pairwise relatively prime positive integers.
Example:
Problem #1
Solve
p1: x = 2 (mod 3)
p2: x = 3 (mod 5)
p3: x = 2 (mod 7)
From p1, x = 3t + 2, for some in

The ChineseRemainderTheorem (CRT) applies when the moduli ni in the system of equations x≡ a1 (mod n1) ... x≡ ar (mod nr) are pairwise relatively prime. When they are not, solutions x may or may not exist. However, the related homogeneous system (2'), in which all ai=0, always has a solution, namely the trivial

1) Derive a formula to find all numbers that meet the following conditions:
• Divide by 3 the remainder is 1
• Divide by 29 the remainder is 6
2) What are the first 20 solutions to Sun Tsu's ChineseRemainder problem?
3) Derive a formula to find all numbers that meet the following conditions:
• Divide by 3 the r

In basic algebra the following Theorem is used frequently.
If x,y and z are any three real numbers and if x + z = y + z then x = y.
The analogous statement for sets would read:
Let A, B, and C be any three sets.
If A union B = A union C then B = C.
Prove in detail that this statement is false. (Hint: Giv

(a) Proof. Let f be onto. Consider any C is a subset of Y. Let y E f(f^-1(C)). Then y=f(x) for some x E F^-1(C). But the fact that x E f^-1(C) implies that f(x) E C. Moreover, f(x)=y. Therefore y E C. Thus we have proved that f(f^-1(C)) is a subset of C. For the converse, consider any c E C. Since f is onto, there exists a