未完成:等價類的應用
-
重溫例子:
設Z為整數集合,R為模n同餘關係。則商集Z/Rn={[ x ] | xZ}={
[0], [1], [2], ..... , [n-1] },記為Zn。其實這個商集總共有n個不相同的等價類。每個等價類分別代表所有被n除後有相同餘數的整數集合。由定理得知:這n個等價類給出Z的一個劃分。
-
設n為一個正整數,記(amam-1....a1a0)10為n的十進制表示式,記S(n)=am+
am-1+ ....+a0稱為n的數字和。在小學我們已認識到以下的
-
定理:n能被9整除當且僅當n的數字和S(n)能被9整除。證:
-
已知(10)m=(9+1)m=9m+9m-1mCm-1+....+9mC1+mC01
=9(9m-1+9m-2mCm-1+....+mC1)
+1=9km+1,
其實km=(10m-1)/9=(10m-1)/(10-1)是個整數。
-
n=(amam-1....a1a0)10
=(10)mam+ (10)m-1am-1+
....+(10)a1+a0
=(9+1)mam+ (9+1)m-1am-1+
....+(9+1)a1+a0
=(9km+1)am+ (9km-1+1)am-1+
....+(9k1+1)a1+a0
=9(kmam+km-1am-1+...+k1a1)+(am+am-1+
....+a1+a0)
=9N(n)+S(n);
其中N(n)=kmam+km-1am-1+...+k1a1。
所以n能被9整除當且僅當S(n)能被9整除。
註:同樣地,證明:
n=(amam-1....a1a0)10能被11整除當且僅當
A(n)=(-1)mam+ (-1)m-1am-1+
....+(-1)a1+a0能被11除。
-
以上的定理表面上是非常難於表達。特別要用到兩項式定理,當然9的整除性是比較簡單,但似乎對於11的整除性二項式定理是不可缺少的。
-
思考問題:能否用類似的方法來決整數n=(amam-1....a1a0)10能被7整除的充要條件?
提示:費馬小定理。
-
其實可以利用Zn=Z/Rn來給出一個較為簡單的證明。
已知整數集合Z上有自然的算術運算,首先要在商集Z/Rn引入另種自然的算術運算。它能簡化以上定理的煩複計算,但仍能追縱到被9、11後之餘數。
(未寫入用等價類來計算)
-
(a)設Z為整數集合,固定一正整數n。在Z上定義一個關係:模n同餘的關係:
設a、b為整數,記 (a , b ) Rn整數|
b-a | 能被n整除。
-
證明:模n同餘關係Rn是等價關係。
-
試給出等價類[1]、[7]相同的充要條件。
-
對於模n同餘關係Rn,試求商集Z/Rn有多少個等價類?
(b)現在考慮方程8x+15y=50。
-
試用反證法來證明:方程8x+15y=50沒有正整數解對。
-
試求方程8x+15y=50的所有整數解對。
-