首先這個是阿牛問的<---- 非常刻意的強調XD

要會中國剩餘要會找乘法反元素

首先是乘法反

簡單的乘法反像是這種題型

(乘法反，就是模n同於1也就是等價旁的數字為1，就好像下列題目)

3*x≡1 mod 5 求x

(這個題目中文描述他就像是，3乘上多少後再除5就會餘1，≡這個符號念等價於)

那為節省時間，x答案一定是0 or 1 or 2 or 3 or 4(就除於5的餘數可能答案)

那這個答案為x=2

所以當碰到像是4*x≡1 mod 7答案一定就在0 or 1 or 2 or 3 or 4 or 5 or 6

那一個一個帶得到x=2

想知道為什麼請去查書~要考試的前提下先記起來。

那說他是簡單的原因就在於真正難的題目都不會是這樣

都像是34*x≡1 mod 89

那你當然不可能用0阿1阿慢慢去帶入，代完已經考完了。

所以就要用歐幾里得法去求，沒聽過歐幾里得?就輾轉相除法啦~

步驟如下(很麻煩但卻是正式解法!)

34*x≡1 mod 89其實就是34*x+89*y=1(這個其實才是她真正的涵義，不懂在問我)(還有這個轉換步驟一定要記好!!!!)

所以其實就是找x跟y的最小解

那解法如下

89 = 34 * 2 + 21

34 = 21 * 1 + 13

21= 13 * 1 + 8

13= 8 * 1 + 5

8 = 5 * 1 + 3

5 = 3 * 1 + 2

3 = 2 * 1 +1...........停~~~~~~~~

然後倒推~(依照上方喔!)

1=3 - (2 * 1)

=3 - (5- 3 * 1)*1 [2換成5-3] = 3 * 2 - 5

=(8 - 5 * 1 ) * 2 - 5 [3換成8-5]= (8 * 2) - (5 * 3)

=(8 * 2) - ((13-8)*3) [5換成13-8] =(8 * 5) - (13 * 3 )

=((21-13)*5)- (13 * 3) [8換成21-13] =(21 * 5 ) - (13 * 8)

=(21 * 5) - ((34-21)*8 ) [13換成34-21]= (21 * 13) -(34 * 8)

=(89-34*2)*13 - (34 * 8) [21換成89-34*2] = (89 * 13) - (34 * 34)

所以你看我們要找的34*x+89*y=1就這樣找到了

x =-34 ，y = 13 那我們是要看34*x≡1 mod 89 所以看34的x就可以了所以x=- 34，但這邊有一件事情要注意，通常問這個答案都希望是最小正數

所以怎麼辦勒，簡單，就-34 + 89 (就是加上妳mod後面的數字)=55，所以最小正數x = 55

順便說，如果碰到 34*x≡2 mod 89 那怎麼辦? 其實就是先算34*x+89*y=1 然後在全體 乘上2 變成 34 * (2 * x) + 89 * (2 * y )=2

當然答案要寫(2 * x)的答案

同理34*x≡3 mod 89就是要寫(3 * x)的答案

接下來進入中國餘式定理