首頁>Club>
6
回覆列表
  • 1 # 洛洛

    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

  • 中秋節和大豐收的關聯?
  • iphone如何算啟用?