AAA解法:
解同餘式組:x≡1(mod5) x≡2(mod11)
解:中國剩餘定理的等效解法
令x=5a+11b +55t 亦即 x==5a+11b mod 5*11
代入原同餘式組得
11b==1 mod 5
5a==2 mod 11
解得b==1 mod 5, a=-4==7 mod 11
取任意一組特解如b=1,a=7代入得
x==5*7+11*1=46 mod 55
BBB解的數量之判定法:
對於多個模並非兩兩互質的情況,可以先確立一組兩兩互質的分解基數集(質數集是一個常用的特例),將這些模用分解基數表示成為多個因數項,將其中相關於同一個分解基數的項進行歸併。如果有矛盾,則無解。
否則有解。
例:同餘式組
x=2 mod 16
x=3 mod 5
x=6 mod 12
取4, 3, 5作為分解基。變成
x=2 mod 4^2
x=6 mod 4
x=6 mod 3
其中相關於同一個分解基數的情況,僅有x=2 mod 16與x=6 mod 4是相關於分解基數"4"的,它們沒有矛盾。取兩相容解集的交集,即其中解集較小的那個:x=2 mod 16.
再與x=3 mod 5及x=6==0 mod 3聯立求解。
另例:
x=2 mod 18
x=8 mod 12
以3,2為分解基。
相關於分解基數3的轉化式有x=2 mod 3^2, x=2 mod 3, 取前者。
相關於分解基數2的轉化式有x=0 mod 2, x=0 mod 4, 取後者。
另例:同餘式組
x=3 mod 12
以2,3為分解基集,於是原同餘式組變成
x==3 mod 2^2
x==3 mod 3
x==2 mod 3^2
x==2 mod 2
矛盾。故此同餘式無解。
如果是形如
ax=b mod m形狀的同餘式聯立的,
則可能出現無解、一解、多解的情況。一個基本的例子如下:
12x=18 mod 27 注:相當於12x=9+18k
自然就等價於同餘式
4x=3 mod 9
解得x=3 mod 9, 轉化為模27的同餘式,為
x=3,12,21 mod 27
AAAAAA快速計算法
例如同餘式組(以下用==表示同餘號)
x==
2 mod 5
-2 mod 6
-3 mod 7
對中國剩餘定理一個簡單的改進可以是這樣:
令
x=5*6*7*(a/5+b/6+c/7) mod 5*6*7
即x=6*7*a+5*7*b+5*6* c+ 5*6*7 t
代入原題即得
6*7*a==2 mod 5
5*7*b==-2 mod 6
5*6*c==-3 mod 7
求得
a==1 mod 3, 或者說是形如-1+3u的任意整數。
b=2 mod 5, ...
c=2 mod 7
剩下的就是如果計算出x來了。下面也給了簡化方法。
從下面這個式子上看
=5*6*7*(a/5+b/6+c/7 mod 1) 注意,這個式子極具有啟發性!
我們看到,我們需要的x的值,只要取以5*6*7作分母時的分數(a/5+b/6+c/7) 的分子就行了,
如果我們將 a/5+b/6+c/7表示成帶分數,即整數加真分數的形式。
還可以發現,如果要取最小正整數解,就取這個真分數的分子就形子。。
在計算過程中,
任意加減一個整數,造成數的增大和變小,並不影響我們的結果。
同時,任意交換加項,也不影響。
下面我們來計算:
1/5+2/6+2/7 mod 1=16/30+2/7=172/210
再例:這是我剛答的一道題,講的較為明確精煉,請參考。
一個數÷5餘1,÷7餘3,÷9餘2,這個數最小是幾?
題目轉化為同餘式組
x==1 mod 5
x==3 mod 7
x==2 mod 9
解:
令x==7*9*a+5*9*b+5*7*c mod 5*7*9
即x=7*9*a+5*9*b+5*7*c+5*7*9*t
即x==5*7*9*(a/5+b/7+c/9 mod 1)
即x=5*7*9*(a/5+b/7+c/9+t)
7*9*a==1 mod 5 , 於是a==2 mod 5, 取其特值2為代表。
5*9*b ==3 mod 7,於是b==1 mod 7,取其特值1為代表。
5*7*c==2 mod 9,於是c==-2 mod 9,取其特值-2為代表。
再以
x==5*7*9*(a/5+b/7+c/9 mod 1)為求值式,進行計算。
先計算(a/5+b/7+c/9 mod 1)
注意,計算過程中,任一個加項或整體值上可以加減任一個整數,不影響。同時,在計算時,可以充分運用加法的交換律與結合律,隨意調整加法項的位置與加法過程的順序。
其中,mod 1這個提法一定要理解,這樣可以為解同餘式組帶來極大的方便。
mod 1表示兩個物件相差一個整數值。如果mod用來表示求餘,則表示求一個數的小數部分;如果N==0 mod 1,即說明N為整數。
2/5+1/7-2/9 mod 1 ==2/5-2/9+1/7==8/45+1/7==101/45*7==101/315
於是x==101 mod 315
這個數最小為 101
AAA解法:
解同餘式組:x≡1(mod5) x≡2(mod11)
解:中國剩餘定理的等效解法
令x=5a+11b +55t 亦即 x==5a+11b mod 5*11
代入原同餘式組得
11b==1 mod 5
5a==2 mod 11
解得b==1 mod 5, a=-4==7 mod 11
取任意一組特解如b=1,a=7代入得
x==5*7+11*1=46 mod 55
BBB解的數量之判定法:
對於多個模並非兩兩互質的情況,可以先確立一組兩兩互質的分解基數集(質數集是一個常用的特例),將這些模用分解基數表示成為多個因數項,將其中相關於同一個分解基數的項進行歸併。如果有矛盾,則無解。
否則有解。
例:同餘式組
x=2 mod 16
x=3 mod 5
x=6 mod 12
取4, 3, 5作為分解基。變成
x=2 mod 4^2
x=3 mod 5
x=6 mod 4
x=6 mod 3
其中相關於同一個分解基數的情況,僅有x=2 mod 16與x=6 mod 4是相關於分解基數"4"的,它們沒有矛盾。取兩相容解集的交集,即其中解集較小的那個:x=2 mod 16.
再與x=3 mod 5及x=6==0 mod 3聯立求解。
另例:
x=2 mod 18
x=8 mod 12
以3,2為分解基。
相關於分解基數3的轉化式有x=2 mod 3^2, x=2 mod 3, 取前者。
相關於分解基數2的轉化式有x=0 mod 2, x=0 mod 4, 取後者。
另例:同餘式組
x=3 mod 12
x=2 mod 18
以2,3為分解基集,於是原同餘式組變成
x==3 mod 2^2
x==3 mod 3
x==2 mod 3^2
x==2 mod 2
矛盾。故此同餘式無解。
如果是形如
ax=b mod m形狀的同餘式聯立的,
則可能出現無解、一解、多解的情況。一個基本的例子如下:
12x=18 mod 27 注:相當於12x=9+18k
自然就等價於同餘式
4x=3 mod 9
解得x=3 mod 9, 轉化為模27的同餘式,為
x=3,12,21 mod 27
AAAAAA快速計算法
例如同餘式組(以下用==表示同餘號)
x==
2 mod 5
-2 mod 6
-3 mod 7
對中國剩餘定理一個簡單的改進可以是這樣:
令
x=5*6*7*(a/5+b/6+c/7) mod 5*6*7
即x=6*7*a+5*7*b+5*6* c+ 5*6*7 t
代入原題即得
6*7*a==2 mod 5
5*7*b==-2 mod 6
5*6*c==-3 mod 7
求得
a==1 mod 3, 或者說是形如-1+3u的任意整數。
b=2 mod 5, ...
c=2 mod 7
剩下的就是如果計算出x來了。下面也給了簡化方法。
從下面這個式子上看
x=5*6*7*(a/5+b/6+c/7) mod 5*6*7
=5*6*7*(a/5+b/6+c/7 mod 1) 注意,這個式子極具有啟發性!
我們看到,我們需要的x的值,只要取以5*6*7作分母時的分數(a/5+b/6+c/7) 的分子就行了,
如果我們將 a/5+b/6+c/7表示成帶分數,即整數加真分數的形式。
還可以發現,如果要取最小正整數解,就取這個真分數的分子就形子。。
在計算過程中,
任意加減一個整數,造成數的增大和變小,並不影響我們的結果。
同時,任意交換加項,也不影響。
下面我們來計算:
1/5+2/6+2/7 mod 1=16/30+2/7=172/210
再例:這是我剛答的一道題,講的較為明確精煉,請參考。
一個數÷5餘1,÷7餘3,÷9餘2,這個數最小是幾?
題目轉化為同餘式組
x==1 mod 5
x==3 mod 7
x==2 mod 9
解:
令x==7*9*a+5*9*b+5*7*c mod 5*7*9
即x=7*9*a+5*9*b+5*7*c+5*7*9*t
即x==5*7*9*(a/5+b/7+c/9 mod 1)
即x=5*7*9*(a/5+b/7+c/9+t)
代入原同餘式組得
7*9*a==1 mod 5 , 於是a==2 mod 5, 取其特值2為代表。
5*9*b ==3 mod 7,於是b==1 mod 7,取其特值1為代表。
5*7*c==2 mod 9,於是c==-2 mod 9,取其特值-2為代表。
再以
x==5*7*9*(a/5+b/7+c/9 mod 1)為求值式,進行計算。
先計算(a/5+b/7+c/9 mod 1)
注意,計算過程中,任一個加項或整體值上可以加減任一個整數,不影響。同時,在計算時,可以充分運用加法的交換律與結合律,隨意調整加法項的位置與加法過程的順序。
其中,mod 1這個提法一定要理解,這樣可以為解同餘式組帶來極大的方便。
mod 1表示兩個物件相差一個整數值。如果mod用來表示求餘,則表示求一個數的小數部分;如果N==0 mod 1,即說明N為整數。
2/5+1/7-2/9 mod 1 ==2/5-2/9+1/7==8/45+1/7==101/45*7==101/315
於是x==101 mod 315
這個數最小為 101