Çinlilerin kalan teoremi

Çinlilerin kalan teoremi, "3'e bölündüğünde 2, 5'e bölündüğünde 3, 7'ye bölündüğünde 4 kalanını veren sayıyı bulun" tipinden problemleri çözmek için kullanılan teorem. buna göre: 3'e bölündüğünde 2 kalanını veren sayılar 3.k+2 şeklindedir. (2, 5, 8, ...) 5'e bölündüğünde 3 kalanını veren sayılar 5.l+3 şeklindedir. (3, 8, 13, ...) bu durumda sayımız 15m+8 şeklindedir. (8, 23, 38, 53, ...) 7'ye bölündüğünde 4 kalanını veren sayılar 7.n+4 şeklindedir. (4, 11, 18, ..., 46, 53, ...) bu durumda da sayımız 105.p+53 şeklindedir.

n₁, n₂, …, n_k pozitif, çiftli aralarında asal Tamsayı olsun. Bu durumda, Verilen herhangi a₁,a₂, …, a_k,tamsayıları için bir x tamsayısı vardır ki sistemin eşzamanlı uygun bir çözümüdür.

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}}$

Bundan başka, Tüm Çözümler x Bu sistem uyumlu olan modulo N = n₁n₂…n_k.

Böylece ${\displaystyle x\equiv y{\pmod {n_{i}}}}$ tüm ${\displaystyle 1\leq i\leq k}$, ancak ve ancak ${\displaystyle x\equiv y{\pmod {N}}}$.

Sometimes, the simultaneous congruences can be solved even if the n_i's are not pairwise coprime. A solution x exists if and only if:

${\displaystyle a_{i}\equiv a_{j}{\pmod {\gcd(n_{i},n_{j})}}\qquad {\mbox{for all }}i{\mbox{ and }}j.\,\!}$

All solutions x are then congruent modulo the least common multiple of the n_i.

Versions of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).

Çözümü Bulmak için Yapıcı bir algoritma

Aşağıdaki algoritma sadece aralarında ikili asal olan ${\displaystyle n_{i}}$ sayıları için geçerlidir. (Eşzamanlı kongrüanslar için modül asal ikili değilse, peşpeşe ekleme yöntemi kullanarak çözüme ulaşılabilir.)

Aşağıdaki gibi verilmiş olan kongrüanslar sistemi için bir çözümün gerekli olduğunu varsayalım:

${\displaystyle x\equiv a_{i}{\pmod {n_{i}}}\quad \mathrm {for} \;i=1,\ldots ,k.}$

İlk adım olarak ${\displaystyle N=n_{1}n_{2}\ldots n_{k}}$ çarpımı tanımlanır. Sonra aşağıdaki yöntem izlenerek bir x çözümü bulunabilir.

Bütün i değerleri için ${\displaystyle n_{i}}$ ve ${\displaystyle N/n_{i}}$ sayılarının asal olduğunu biliyoruz. Genişletilmiş Öklid algoritması yardımıyla ${\displaystyle r_{i}n_{i}+s_{i}N/n_{i}=1}$ eşitliğini sağlayan ${\displaystyle r_{i}}$ ve ${\displaystyle s_{i}}$ sayılarını bulabiliriz. Ardından ${\displaystyle e_{i}=s_{i}N/n_{i}}$ değerine ulaşılır ve yukarıda verilen eşitlik şu hale getirilir:

${\displaystyle r_{i}n_{i}+e_{i}=1\,\!}$

${\displaystyle e_{i}}$ sayısı göz önünde bulundurulursa, yukarıdaki eşitliğin ${\displaystyle n_{i}}$ ile bölünmesi halinde kalanın 1 olması gerektiğini görürüz. Diğer taraftan, ${\displaystyle s_{i}N/n_{i}}$ şeklinde ifade edildiğinden, elimizdeki $N$ değeri ${\displaystyle j\neq i}$ olduğu sürece bu eşitliğin ${\displaystyle n_{j}}$ ile eşit olarak bölüneceğini garanti eder.

${\displaystyle e_{i}\equiv 1{\pmod {n_{i}}}\quad \mathrm {ve} \quad e_{i}\equiv 0{\pmod {n_{j}}}\quad \mathrm {eger} ~i\neq j}$

Bu nedenle, kongrüanslar için kullanılan çarpım kuralları da göz önünde bulundurularak, bu kongrüans sistemine bulunabilecek çözümlerden bir tanesi:

${\displaystyle x=\sum _{i=1}^{k}a_{i}e_{i}.\!}$

Örneğin, aşağıda verilen kongrüans sistemi için bir x tamsayısı bulmaya çalışalım:

${\displaystyle x\equiv 2{\pmod {3}},\,\!}$

${\displaystyle x\equiv 3{\pmod {4}},\,\!}$

${\displaystyle x\equiv 1{\pmod {5}}.\,\!}$

Genişletilmi Öklid algoritması yardımıyla x için mod 3 ve 20 [4×5] kullanarak (−13) × 3 + 2 × 20 = 1, yani e₁ = 40 değeri bulunur. Aynı yöntemle x için mod 4 ve 15 [3×5] kullanarak (−11) × 4 + 3 × 15 = 1, yani e₂ = 45 değeri bulunur. Son olarak, x için mod 5 ve 12 [3×4] kullanarak 5 × 5 + (−2) × 12 = 1, yani e₃ = −24 değerini elde ederiz. Bulduklarımızı birleştirecek olursak muhtemeel x sayılarından bir tanesi 2 × 40 + 3 × 45 + 1 × (−24) = 191 olur. Diğer bütün çözümler 191'in mod 60 [3 × 4 × 5 = 60] değerine eşleniktir, bir diğer ifadeyle olası x değerlerinin hepsi 11'in mod 60 değeriyle eşleniktir.

NOT: Genişletilmi Öklid algoritması çeşitli yaklaşımlarla uygulanabilir. Bu soru için farklı uygulamalar kullanılarak ${\displaystyle e_{1}=-20}$, ${\displaystyle e_{2}=-15}$, ve ${\displaystyle e_{3}=-24}$ değerleri elde edilebilir. Fakat, bunlar da bizi aynı sonuca ulaştıracaktır, yani (-20)2+(-15)3+(-24)1=-109=11 mod 60.

Temel ideal bölgeler için Açıklama

For a principal ideal domain R the Chinese remainder theorem takes the following form: If u₁, ..., u_k are elements of R which are pairwise coprime, and u denotes the product u₁...u_k, then the quotient ring R/uR and the product ring R/u₁R× ... × R/u_kR are isomorphic via the isomorphism

${\displaystyle f:R/uR\rightarrow R/u_{1}R\times \cdots \times R/u_{k}R}$

such that

${\displaystyle f(x+uR)=(x+u_{1}R,\ldots ,x+u_{k}R)\quad {\mbox{ for every }}x\in R.}$

This isomorphism is unique; the inverse isomorphism can be constructed as follows. For each i, the elements u_i and u/u_i are coprime, and therefore there exist elements r and s in R with

${\displaystyle ru_{i}+su/u_{i}=1.\,\!}$

Set e_i = s u/u_i. Then the inverse of f is the map

${\displaystyle g:R/u_{1}R\times \cdots \times R/u_{k}R\rightarrow R/uR}$

such that

${\displaystyle g(a_{1}+u_{1}R,\ldots ,a_{k}+u_{k}R)=\left(\sum _{i=1}^{k}a_{i}e_{i}\right)+uR\quad {\mbox{ for all }}a_{1},\ldots ,a_{k}\in R.}$

Note that this statement is a straightforward generalization of the above theorem about integer congruences: the ring Z of integers is a principal ideal domain, the surjectivity of the map f shows that every system of congruences of the form

${\displaystyle x\equiv a_{i}{\pmod {u_{i}}}\quad \mathrm {for} \;i=1,\ldots ,k}$

can be solved for x, and the injectivity of the map f shows that all the solutions x are congruent modulo u.

Genel halkaları için Açıklama

The general form of the Chinese remainder theorem, which implies all the statements given above, can be formulated for commutative rings and ideals. If R is a commutative ring and I₁, ..., I_k are ideals of R which are pairwise coprime (meaning that I_i + I_j = R whenever i ≠ j), then the product I of these ideals is equal to their intersection, and the quotient ring R/I is isomorphic to the product ring R/I₁ x R/I₂ x ... x R/I_k via the isomorphism

${\displaystyle f:R/I\rightarrow R/I_{1}\times \cdots \times R/I_{k}}$

such that

${\displaystyle f(x+I)=(x+I_{1},\ldots ,x+I_{k})\quad {\mbox{ for all }}x\in R.}$

Uygulamalar

• In the RSA algorithm calculations are made modulo ${\displaystyle n}$, where ${\displaystyle n}$ is a product of two large prime numbers ${\displaystyle p}$ and ${\displaystyle q}$. 1024-, 2048- or 4096-bit integers ${\displaystyle n}$ are commonly used, making calculations in ${\displaystyle {\mathbb {Z}}/n{\mathbb {Z}}}$ very time-consuming. By the Chinese Remainder Theorem, however, these calculations can be done in the isomorphic ring ${\displaystyle {\mathbb {Z}}/p{\mathbb {Z}}\oplus {\mathbb {Z}}/q{\mathbb {Z}}}$ instead. Since ${\displaystyle p}$ and ${\displaystyle q}$ are normally of about the same size, that is about ${\displaystyle {\sqrt {n}}}$, calculations in the latter representation are much faster. Note that RSA algorithm implementations using this isomorphism are more susceptible to fault injection attacks.
• The Chinese Remainder Theorem may also be used to construct an elegant Gödel numbering for sequences, which is needed to prove Gödel's incompleteness theorems.
• The following example shows a connection with the classic polynomial interpolation theory. Let r complex points ("interpolation nodes") ${\displaystyle \textstyle \lambda _{1},\cdots ,\lambda _{r}}$ be given, together with the complex data ${\displaystyle a_{j,k}\ }$, for all ${\displaystyle \textstyle 1\leq j\leq r}$ and ${\displaystyle \textstyle 0\leq k<\nu _{j}}$. The general Hermite interpolation problem asks for a polynomial ${\displaystyle \textstyle P(x)\in \mathbb {C} [x]}$ taking the prescribed derivatives in each node ${\displaystyle \lambda _{j}\ }$:

${\displaystyle P^{(k)}(\lambda _{j})=a_{j,k}\quad \forall 1\leq j\leq r\ ,0\leq k<\nu _{j}}$.

Introducing the polynomials ${\displaystyle \textstyle A_{j}(x):=\sum _{k=0}^{\nu _{j}}{\frac {a_{j,k}}{k!}}(x-\lambda _{j})^{k}}$, the problem may be equivalently reformulated as a system of ${\displaystyle r\ }$ simultaneous congruences:

${\displaystyle P(x)\equiv A_{j}(x){\pmod {(x-\lambda _{j})^{\nu _{j}}}},\quad \forall 1\leq j\leq r\ }$.

By the Chinese remainder theorem in the principal ideal domain ${\displaystyle \textstyle \mathbb {C} [x]}$, there is a unique such polynomial ${\displaystyle \textstyle P(x)}$ with degree ${\displaystyle \textstyle \deg(P)<n:=\sum _{j}\nu _{j}}$. A direct construction, in analogy with the above proof for the integer number case, can be performed as follows. Define the polynomials ${\displaystyle \textstyle Q:=\prod _{i=1}^{r}(x-\lambda _{i})^{\nu _{i}}}$ and ${\displaystyle \textstyle Q_{j}:={\frac {Q}{(x-\lambda _{j})^{\nu _{j}}}}}$. The partial fraction decomposition of ${\displaystyle \textstyle {\frac {1}{Q}}}$ gives r polynomials ${\displaystyle \textstyle S_{j}}$ with degrees ${\displaystyle \textstyle \deg(S_{j})<\nu _{j}}$ such that

${\displaystyle {\frac {1}{Q}}=\sum _{i=1}^{r}{\frac {S_{i}}{(x-\lambda _{i})^{\nu _{i}}}}}$,

so that ${\displaystyle \textstyle 1=\sum _{i=1}^{r}S_{i}Q_{i}}$. Then a solution of the simultaneous congruence system is given by the polynomial

${\displaystyle \sum _{i=1}^{r}A_{i}S_{i}Q_{i}=A_{j}+\sum _{i=1}^{r}(A_{i}-A_{j})S_{i}Q_{i}\equiv A_{j}{\pmod {(x-\lambda _{j})^{\nu _{j}}}}\quad \forall 1\leq j\leq r\ }$;

and the minimal degree solution is this one reduced modulo ${\displaystyle \textstyle Q}$, that is the unique with degree less than n.

• The Chinese Remainder Theorem can also be used in Secret sharing, which consists of distributing a set of shares among a group of people who, all together (but no one alone), can recover a certain secret from the given set of shares. Each of the shares is represented in a congruence, and the solution of the system of congruences using the Chinese remainder theorem is the secret to be recovered. Secret Sharing using the Chinese Remainder Theorem uses, along with the Chinese remainder theorem, special sequences of integers that guarantee the impossibility of recovering the secret from a set of shares with less than a certain cardinality.

Non-commutative case: a counter-example

The Chinese remainder theorem does not hold in the non-commutative case. Consider the ring ${\displaystyle R}$ of non-commutative real polynomials in ${\displaystyle x}$ and ${\displaystyle y}$. Let ${\displaystyle I}$ be the principal two-sided ideal generated by ${\displaystyle x}$ and ${\displaystyle J}$ the principal two-sided ideal generated by ${\displaystyle xy+1.}$ Then ${\displaystyle I+J=R}$ but ${\displaystyle I\cap J\neq IJ.}$

ISPAT:

Observe that ${\displaystyle I}$ is formed by all polynomials with an ${\displaystyle x}$ in every term and that every polynomial in ${\displaystyle J}$ vanishes under the substitution ${\displaystyle y=-1/x}$. Consider the polynomial ${\displaystyle p=(xy+1)x}$. Clearly ${\displaystyle p\in I\cap J}$. Define a term in ${\displaystyle R}$ as an element of the multiplicative monoid of ${\displaystyle R}$ generated by ${\displaystyle x}$ and ${\displaystyle y}$. Define the degree of a term as the usual degree of the term after the substitution ${\displaystyle y=x}$. On the other hand, suppose ${\displaystyle q\in J}$. Observe that a term in ${\displaystyle q}$ of maximum degree depends on ${\displaystyle y}$ otherwise ${\displaystyle q}$ under the substitution ${\displaystyle y=-1/x}$ can not vanish. The same happens then for an element ${\displaystyle q\in IJ}$. Observe that the last ${\displaystyle y}$, from left to right, in a term of maximum degree in an element of ${\displaystyle IJ}$ is preceded by more than one ${\displaystyle x}$. (We are counting here all the preceding ${\displaystyle x}$s. e.g. in ${\displaystyle x^{2}yxyx^{5}}$ the last ${\displaystyle y}$ is preceded by ${\displaystyle 3}$ ${\displaystyle x}$s.) This proves that ${\displaystyle (xy+1)x\notin IJ}$ since that last ${\displaystyle y}$ in a term of maximum degree (${\displaystyle xyx}$) is preceded by only one ${\displaystyle x}$. Hence ${\displaystyle I\cap J\neq IJ}$.

On the other hand, it is true in general that ${\displaystyle I+J=R}$ implies ${\displaystyle I\cap J=IJ+JI}$. To see this, note that ${\displaystyle I\cap J=(I\cap J)(I+J)\subset IJ+JI}$, while the opposite inclusion is obvious. Also, we have in general that, provided ${\displaystyle I_{1},\ldots ,I_{m}}$ are pairwise coprime two-sided ideals in ${\displaystyle R}$, the natural map

${\displaystyle R/(I_{1}\cap I_{2}\cap \ldots \cap I_{m})\rightarrow R/I_{1}\oplus R/I_{2}\oplus \cdots \oplus R/I_{m}}$

is an isomorphism. Note that ${\displaystyle I_{1}\cap I_{2}\cap \ldots \cap I_{m}}$ can be replaced by a sum over all orderings of ${\displaystyle I_{1},\ldots ,I_{m}}$ of their product (or just a sum over enough orderings, using inductively that ${\displaystyle I\cap J=IJ+JI}$ for coprime ideals ${\displaystyle I,J}$).

Bunlara da bakınız

• Covering system
• Hasse principle
• Residue number system
• Secret Sharing using the Chinese Remainder Theorem

Referanslar

• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.3.2 (pp. 286–291), exercise 4.6.2–3 (page 456).
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.5: The Chinese remainder theorem, pp. 873–876.
• Sigler, Laurence E. (trans.) (2002). Fibonacci's Liber Abaci. Springer-Verlag. s. 402–403. ISBN 0-387-95419-8. 

Dış bağlantılar

• Chinese remainder theorem at cut-the-knot
• "Chinese Remainder Theorem" by Ed Pegg, Jr., Wolfram Demonstrations Project, 2007.
• Eric W. Weisstein, Chinese Remainder Theorem (MathWorld)
• C# program and discussion at codeproject
• University of Hawaii System CRT by Lee Lady