中国剩余定理，英文为 Chinese Remainder Theorem \text{Chinese Remainder Theorem} Chinese Remainder Theorem，简称 CRT \text{CRT} CRT。最早见于《孙子算经》中：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”故又称孙子定理。
中国剩余定理可求解如下的一元线性同余方程组，其中 m 1 , m 2 , ⋯ , m n m_1,m_2,\cdots,m_n m1,m2,⋯,mn 两两互质。 ( S ) : { x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⋮ x ≡ a n ( m o d m n ) (S):\left\{\begin{array}{c} x \equiv a_{1}\left(\bmod m_{1}\right) \\ x \equiv a_{2}\left(\bmod m_{2}\right) \\ \vdots \\ x \equiv a_{n}\left(\bmod m_{n}\right) \end{array}\right. (S):⎩⎪⎪⎪⎨⎪⎪⎪⎧x≡a1(modm1)x≡a2(modm2)⋮x≡an(modmn)
假设整数 m 1 , m 2 , ⋯ , m n m_1,m_2,\cdots ,m_n m1,m2,⋯,mn 两两互质，则对任意的整数 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an，方程组 ( S ) (S) (S) 有解。可以通过如下方式构造得到：
设 M = ∏ i = 1 n m i M=\prod\limits_{i=1}^n m_i M=i=1∏nmi， M i = M m i M_i=\frac{M}{m_i} Mi=miM。设整数 t i t_i ti 为模 m i m_i mi 意义下 M i M_i Mi 的逆元，即 M i t i ≡ 1 ( m o d m i ) M_it_i\equiv1\quad(\bmod m_i) Miti≡1(modmi)。方程组 ( S ) (S) (S) 的通解为 x = k M + ∑ i = 1 n a i t i M i , k ∈ Z x=kM+\sum\limits_{i=1}^n a_it_iM_i,k\in Z x=kM+i=1∑naitiMi,k∈Z；在模 M M M 的意义下，方程组只有一个解 x = ( ∑ i = 1 n a i t i M i ) m o d M x=\left(\sum\limits_{i=1}^n a_it_iM_i\right)\bmod M x=(i=1∑naitiMi)modM。从假设可知，对任何 i ∈ { 1 , 2 , ⋯ , n } i\in\{1,2,\cdots,n\} i∈{1,2,⋯,n}，由于 ∀ j ∈ { 1 , 2 , ⋯ , n } , j ≠ i \forall j\in\{1,2,\cdots,n\},j\ne i ∀j∈{1,2,⋯,n},j=i，有 gcd ( m i , m j ) = 1 \gcd(m_i,m_j)=1 gcd(mi,mj)=1，所以 gcd ( m i , M i ) = 1 \gcd(m_i,M_i)=1 gcd(mi,Mi)=1。根据裴蜀定理，存在整数 t i t_i ti，使得 M i t i ≡ 1 ( m o d m i ) M_it_i\equiv1\quad(\bmod m_i) Miti≡1(modmi)。 由于 M i t i ≡ 1 ( m o d m i ) M_it_i\equiv1(\bmod m_i) Miti≡1(modmi)，故 a i t i M i ≡ a i ⋅ 1 ≡ a i ( m o d m i ) a_it_iM_i\equiv a_i\cdot1\equiv a_i(\bmod m_i) aitiMi≡ai⋅1≡ai(modmi)；又 ∀ i ∈ { 1 , 2 , ⋯ , n } \forall i\in\{1,2,\cdots,n\} ∀i∈{1,2,⋯,n}，且 i ≠ j i\ne j i=j， a j t j M j ≡ 0 ( m o d m i ) a_jt_jM_j\equiv0(\bmod m_i) ajtjMj≡0(modmi)。所以 ∑ i = 1 n a i t i M i ≡ \sum\limits_{i=1}^n a_it_iM_i\equiv i=1∑naitiMi≡ a i t i M i + ∑ j = 1 i − 1 a j t j M j + ∑ j = i + 1 n a j t j M j a_it_iM_i+\sum\limits_{j=1}^{i-1}a_jt_jM_j+\sum\limits_{j=i+1}^n a_jt_jM_j aitiMi+j=1∑i−1ajtjMj+j=i+1∑najtjMj ≡ \equiv ≡ a i + ∑ j = 1 i − 1 0 a_i+\sum\limits_{j=1}^{i-1}0 ai+j=1∑i−10 ∑ j = i + 1 n 0 ≡ a i ( m o d m i ) \sum\limits_{j=i+1}^n 0\equiv a_i\quad(\bmod m_i) j=i+1∑n0≡ai(modmi)。 以上已经证明： x = ∑ i = 1 n a i t i M i x=\sum\limits_{i=1}^n a_it_iM_i x=i=1∑naitiMi 是方程组的一个解。 假设方程组存在两个解 x 1 , x 2 x_1,x_2 x1,x2，那么 ∀ i ∈ \forall i\in ∀i∈ { 1 , 2 , ⋯ , n } \{1,2,\cdots,n\} {1,2,⋯,n}，有 x 1 − x 2 ≡ 0 ( m o d m i ) x_1-x_2\equiv0\quad(\bmod m_i) x1−x2≡0(modmi)；又 m 1 , m 2 , ⋯ , m n m_1,m_2,\cdots,m_n m1,m2,⋯,mn 两两互质，说明 M ∣ ( x 1 − x 2 ) M\mid(x_1-x_2) M∣(x1−x2)；所以方程组 ( S ) (S) (S) 的两个解必然相差 M M M 的整数倍。由于存在一个特解 x = x= x= ∑ i = 1 n a i t i M i \sum\limits_{i=1}^n a_it_iM_i i=1∑naitiMi，所以方程组 ( S ) (S) (S) 的通解为 x = k M + ∑ i = 1 n a i t i M i , k ∈ Z x=kM+\sum\limits_{i=1}^n a_it_iM_i,k\in Z x=kM+i=1∑naitiMi,k∈Z。 证毕。 （定理描述和证明部分引用维基百科词条：中国剩余定理）
自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有 16 16 16 头母猪，如果建了 3 3 3 个猪圈，剩下 1 1 1 头猪就没有地方安家了。如果建造了 5 5 5 个猪圈，但是仍然有 1 1 1 头猪没有地方去，然后如果建造了 7 7 7 个猪圈，还有 2 2 2 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？
第一行包含一个整数 n n n——建立猪圈的次数，接下来 n n n 行，每行两个整数 a i a_i ai， b i b_i bi， 表示建立了 a i a_i ai 个猪圈，有 b i b_i bi 头猪没有去处。你可以假定 a i a_i ai， a j a_j aj 互质。
输出包含一个正整数，即为曹冲至少养母猪的数目。
3 3 1 5 1 7 2
16
1 ≤ n ≤ 10 1 \leq n\le10 1≤n≤10， 1 ≤ b i ≤ a i ≤ 100000 1 \leq b_i\le a_i\le100000 1≤bi≤ai≤100000， 1 ≤ ∏ i = 1 n a i ≤ 1 0 18 1 \leq \prod\limits_{i=1}^n a_i \leq 10^{18} 1≤i=1∏nai≤1018。
由题意得一元线性同余方程组 { x ≡ b 1 ( m o d a 1 ) x ≡ b 2 ( m o d a 2 ) ⋮ x ≡ b n ( m o d a n ) \left\{\begin{array}{c}x \equiv b_{1}\left(\bmod a_{1}\right) \\x \equiv b_{2}\left(\bmod a_{2}\right) \\\vdots \\x \equiv b_{n}\left(\bmod a_{n}\right)\end{array}\right. ⎩⎪⎪⎪⎨⎪⎪⎪⎧x≡b1(moda1)x≡b2(moda2)⋮x≡bn(modan)，题干中已经说明 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an 两两互质，因此可用中国剩余定理求解这个方程组。 设 M = ∑ i = 1 n a i M=\sum\limits_{i=1}^n a_i M=i=1∑nai， M i = M a i M_i=\frac{M}{a_i} Mi=aiM；那么一定存在正整数 t i t_i ti 使得 M i t i ≡ 1 ( m o d a i ) M_it_i\equiv1\quad(\bmod a_i) Miti≡1(modai)。 方程组的最小正整数解为 x = ( ∑ i = 1 n b i t i M i ) m o d M x=\left(\sum\limits_{i=1}^n b_it_iM_i\right)\bmod M x=(i=1∑nbitiMi)modM。
