同餘的概念

    首先讓我介紹得國數學家高斯在二百年前想出來的一個數學上很重要的概念:「同餘」(Congruence)

    給定一個正整數n,如果a-bn的倍數我們說兩個數ab是對模數n同餘。用符號 表示。

    比方說:74是對模3同餘,因為7-4=31652是對模6同餘,因為16-52=-36=6 (-6)2313是對模2,模5同餘,因為23-13=10=2 5寫成數學式子是7 4(mod 3)16 52(mod 6)23 13(mod 2)23 13(mod 5)。而

42(mod 3)

    我們現在令Z表示所有的整數集合,給定一個正整數n,我們看同餘 究竟有什麼性質?

    首先,對於任何整數a,我們琣豉 a(mod n)

    因為a-a=0=0 n,以上的性質就是「同餘具有反身性(Reflexive property)」

    因為由a b(mod n),我們得a-b=n k,k是一個整數,因此b-a=-(a-b)=n (-k),即b a(mod n)。我們說「同餘具有對稱性(Symmetry property)」。

    另外如果有a b(mod n),b c(mod n),則我們就可以得到a c(mod n)。

    這就是「同餘具有遞移性(Transitive Property)」。

由於同餘這三種特別的性質,我們可能把整數集Z分成n部分,我們用 …… 來表示這些部分,對於 包含所有使得a k(mod n)的整數a

    任我們看看底下的例子:

例1.          n=2,則我們把整術分成偶數和奇數,就是

      包含所有偶數。

      包含所有奇數。

2.  取n=3,則

     

    現在讓我問一個問題:「什麼數被2除餘1?」我想你一定會回答:是所有的奇數,奇數一般可以用2k+1來表示k=0 1 2……。就是在

    現在讓我再問一個問題:「什麼數被3除餘2」?

    我想你一定會回答:所有形如3k+2的數,這裡k可以等於0 ,這就是在

     這兩個問題都是很容易的。現在讓我們把這兩個問題合成一個問題:「什麼是被2除餘1,被3除餘2?」

     這時你就必須在 -7-1511……等等。(如果你學過初等集合論,你就是要找交集 的所有元素。)

     而這些所有的數可以寫成形如6k+1(k=0 )

因為  6k-1 1(mod 2)

      6k-1 2(mod 3)

    以上的問題寫成數學式子就是:「尋找x,使得x 1(mod 2),x (mod 3)。」

    而答案是:所有形如6k-1的數。