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.

Need to prove two parts and must follow the ChineseRemainderTheorem.
Let be polynomials with integer coefficients of the same degree d. Let be integers which are relatively prime in pairs (i.e., ( for i j). Use the ChineseRemainderTheorem to prove there exists a polynomial f(x) with integer coefficients and of degre

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

The idea of this problem is to investigate solutions to x2≡1(mod pq) where p and q are distinct odd primes.
(a) Show that if p is an odd prime, then there are exactly two solutions modulo p to x2≡1(mod p).
(b) Find all pairs (a,b) Є Zp x Zq such that a2≡1(mod p) and b2≡1(mod q).
(c) Let p=17 an

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

Topics usually include the Euclidean algorithm, primes and unique factorization, congruences, ChineseRemainderTheorem, Hensel's Lemma, Diophantine equations, arithmetic in polynomial rings, primitive roots, quadratic reciprocity and quadratic fields.
(See attached file for full problem description)