Chinese remainder theorem
- Chinese remainder theorem
-
ancient theorem that gives the conditions necessary for multiple equations to have a simultaneous integer solution. The theorem has its origin in the work of the 3rd-century-AD Chinese mathematician Sun Zi, although the complete theorem was first given in 1247 by
Qin Jiushao.
The Chinese remainder theorem addresses the following type of problem. One is asked to find a number that leaves a remainder of 0 when divided by 5, remainder 6 when divided by 7, and remainder 10 when divided by 12. The simplest solution is 370. Note that this solution is not unique, since any multiple of 5 × 7 × 12 (= 420) can be added to it and the result will still solve the problem.
The theorem can be expressed in modern general terms using congruence notation. (For an explanation of congruence,
see modular arithmetic.) Let
n1,
n2, …,
nk be integers that are greater than one and pairwise relatively prime (that is, the only common factor between any two of them is 1), and
let a1,
a2, …,
ak be any integers. Then there exists an integer solution
a such that
a ≡
ai (
mod ni) for each
i = 1, 2, …,
k. Furthermore, for any other integer
b that satisfies all the congruences,
b ≡
a (
mod N) where
N =
n1n2⋯
nk. The theorem also gives a formula for finding a solution. Note that in the example above, 5, 7, and 12 (
n1,
n2, and
n3 in congruence notation) are relatively prime. There is not necessarily any solution to such a system of equations when the moduli are not pairwise relatively prime.
* * *
Universalium.
2010.
Look at other dictionaries:
Chinese remainder theorem — The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra. In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers.… … Wikipedia
Remainder — In arithmetic, when the result of the division of two integers cannot be expressed with an integer quotient, the remainder is the amount left over. The remainder for natural numbers If a and d are natural numbers, with d non zero, it can be… … Wikipedia
Structure theorem for finitely generated modules over a principal ideal domain — In mathematics, in the field of abstract algebra, the structure theorem for finitely generated modules over a principal ideal domain is a generalization of the fundamental theorem of finitely generated abelian groups and roughly states that… … Wikipedia
Linear congruence theorem — In modular arithmetic, the question of when a linear congruence can be solved is answered by the linear congruence theorem. If a and b are any integers and n is a positive integer, then the congruence: ax equiv; b (mod n ) (1)has a solution for x … Wikipedia
Fermat's little theorem — (not to be confused with Fermat s last theorem) states that if p is a prime number, then for any integer a , a^p a will be evenly divisible by p . This can be expressed in the notation of modular arithmetic as follows::a^p equiv a pmod{p},!A… … Wikipedia
Gödel numbering for sequences — A Gödel numbering for sequences provides us an effective way to represent each finite sequence of natural numbers as a single natural number. Of course, the embedding is surely possible set theoretically, but the emphasis is on the effectiveness… … Wikipedia
Number theory — A Lehmer sieve an analog computer once used for finding primes and solving simple diophantine equations. Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers (the… … Wikipedia
Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… … Wikipedia
number theory — Math. the study of integers and their relation to one another. Also called theory of numbers. [1910 15] * * * Branch of mathematics concerned with properties of and relations among integers. It is a popular subject among amateur mathematicians… … Universalium
mathematics, East Asian — Introduction the discipline of mathematics as it developed in China and Japan. When speaking of mathematics in East Asia, it is necessary to take into account China, Japan, Korea, and Vietnam as a whole. At a very early time in their… … Universalium
