1.2同餘(Congruence)

	定義： 有兩整數a、b，有一正整數N，若(a-b)可被N整除， 則稱整數a、b為對模N同餘，記為a≡b  mod N (即a與b之差為N的整數倍)

 

例如：

　　　11≡2  mod 9        19≡5  mod14     23≡11  mod12

Q： x ≡ 5   mod 7   求x ?

Ans：  x=7N+5

重點：

對任意正整數同餘，可以把整數分為n個不相交的子集合，如下

N0= {x≡0  mod N}            N1= {x≡1  mod N}

N2= {x≡2  mod N}    ……    Nn-1= {x≡N-1  mod N}

例如：  N=4

N0= {x≡0  mod 4}            N1= {x≡1  mod 4}

N2= {x≡2  mod 4}            N3= {x≡3  mod 4}

※有關同餘的議題

1. 線性同餘    2. 二次剩餘   3. 指數同餘   4.多項式同餘

練習題：

1. 寫出一個線性同餘的方程式

2. 寫出一個二次剩餘的方程式

3. 寫出一個指數同餘的方程式

4. 寫出一個多項式同餘的方程式

Ans：

同餘方程式	一元方程式
ax≡b  mod N	ax=b
ax2+bx≡c   mod N	ax2+bx=c
ax≡b  mod N	ax=b
f(x)=anxn+an-1xn-1+…+a0≡b  mod N	f(x)=anxn+an-1xn-1+…+a0=b

1.2.1線性同餘(Linear Congruential)

Q： 何謂線性？

Ans： 滿足重疊定理的系統，稱為線性系統。

	定義： 給定兩整數a、b，與正整數N，則ax≡b  mod N就稱為線性同餘。 (1)若gcd(a,N)=d，且d不能整除於b，則ax≡b  mod N無解 (2)若gcd(a,N)=d，且d整除於b，則ax≡b mod N洽有d個不同剩餘的解 (3)若gcd(a,N)=1，則ax≡b  mod N有唯一解 若滿足ax≡1  mod N，且gcd(a,N)=1，a與N已知 則x稱為a對模數N的模反元素，記為x≡a-1  mod N 此外a稱為x對模數N的模反元素

 

※ 目前被廣泛使用且發展歷史最久的亂數產生方式，即為線性同餘法。最早是在1951年由Lehmer所提出。

練習題：解  (1)3x=1
                       (2)3x≡1  mod7

Ans：

(1)   x=1/3

(2)   x= (7n+1)/3 =2n+ (n+1)/3

     當n=2時  x=4+1=5

     故得  x≡5  mod7

HW#4

想辦法解 (1)101x≡5  mod1234

         (2)13x≡2   mod53

解答：

(1) x= 12n+ (22n+5)/101         令n1=(22n+5)/101

   n=4n1+(13n1-5)/22          令n2=(13n1-5)/22

   n1=n2+(9n2+5)/13           令n3=(9n2+5)/13

   n2=n3+(4n3-5)/9             令n4= (4n3-5)/9

  當n3=8時 → n2=11 → n1=19 → n=87 代入  得x=1063

  故得x≡1063  mod1234

(2) x= 4n+ (n+2)/13        

   當n=11時  可得x=44+1 =45

   故得x≡45   mod53

練習題：解 11x≡2  mod 45？

Ans：

　　 x= 4n+ (n+2)/11

     當N=9時   可得x=37
故得  x≡37   mod45

練習題：解 121x≡3  mod 1001？

Ans：

     x= 8n+ (33n+3)/121           令n1=(33n+5)/121

     n= 3n1+ (22n1-3)/33           令n2=(22n1-3)/33

     n1= n2+ (11n2+3)/22           令n3=(11n2+3)/22

     n2= 2n3+ 3/11           → 此題無解
因為121與1001不是互質

    

練習題：解 121x≡3  mod 1002？

Ans：

     x= 8n+ (34n+3)/121           令n1=(34n+5)/121

     n= 3n1+ (19n1-3)/34           令n2=(19n1-3)/34

     n1= n2+ (15n2+3)/19           令n3=(15n2+3)/19

 n2= n3+ (4n3-3)/15            令n4=(4n3-3)/15

 n3= 3n4+ (3n4+3)/4           令n5=(3n4+3)/4

 n4= n5+ (n5-3)/3          

當n5=3時 → n4=3 → n3=12 → n2=15 → n1=27 → n=96

    已知n=96  可得x= 8*96 +(34*96+3)121 =795

故得  x≡795  mod 1002

※ 以下依序列出上述所列出的式子，並觀察所產生式子的規則

(1) 121x≡3  mod 1002	(2) 34n≡-3   mod 121
(3) 19n1≡3  mod 34	(4) 15n2≡-3  mod 19
(5) 4n3≡3   mod 15	(6) 3n4≡-3   mod 1002
(7) n5≡3    mod 3

※ 由上表可發現式子的規律性，有點類似之前所學的輾轉相除法。