【正文】 ，故 ， 使 得（ ） 式 獲 證1212()( , ) 1 , ( , ) ( , ) 1 ,1 ( m o d )( ) ( )kiiiiik i ipiia m m p p p a p a pappm??????????? ? ? ??設(shè) 得從 而 有 ，再 結(jié) 合 可 得() 1 ( m o d )im iap ?? ?1()1()( , ) 1 , 1 ,1 ( m o d [ , , ] )1 ( m o d )jikijmkmp p i j ka p pam??????? ? ???又 ，所 以即11 1 00 1 101015 20214,():( 1 ) , , ,( 2) ( 2), , ,( ) ( ) ( ) ( )nnnnkknnf x x a x a x aa a am k kr r rf m f r f r f r????? ? ? ? ???例 、 （ 年 全 國(guó) 數(shù) 學(xué) 聯(lián) 合 競(jìng) 賽 加 試 題 ）證 明 ： 對(duì) 任 意 整 數(shù) 存 在 一 個(gè) 次 多 項(xiàng) 式具 有 如 下 性 質(zhì)均 為 正 整 數(shù) ；對(duì) 任 意 正 整 數(shù) ， 及 任 意 個(gè) 互 不 相 同 的正 整 數(shù) ， 均 有( ) ( 1 ) ( 2 ) ( ) 2f x x x x n? ? ? ? ?證 明 ： 令①( ) 1fxn將 ① 的 右 邊 展 開 即 知 是 一 個(gè) 首 項(xiàng) 系 數(shù) 為 的 正整 數(shù) 系 數(shù) 的 次 多 項(xiàng) 式 。第三節(jié) 簡(jiǎn)化剩余系與歐拉函數(shù) 0 1 11 , , , , , , ( m o d ) ( , ) ( , ) .mrrm K K K Ka K a r m a m r m??? ? ? ? ?對(duì) 模 有 個(gè) 剩 余 類 在 中,.mmm1 、 定 義 ： 如 果 一 個(gè) 模 的 剩 余 類 里 面 的 數(shù) 與 互 質(zhì)就 把 它 叫 做 一 個(gè) 與 模 互 質(zhì) 的 剩 余 類15156 , , , ( , 6) ( 1 , 6) 1 ,( , 6) ( 5 , 6) 1 , ( , ) 1.m a K K aa a m K K? ? ? ?? ? ?例 當(dāng) 時(shí) 有 若即 此 時(shí) 的 與 ， 有0 , 1 , , 1mmm?注 ： 由 定 義 ， 要 找 出 所 有 與 模 互 質(zhì) 的 剩 余 類 ，只 需 找 出 序 列 中 所 有 與 互 質(zhì) 的 數(shù) 即 可得 到 ， 而 與 模 互 質(zhì) 的 數(shù) 的 個(gè) 數(shù) 則 可 通 過 歐 拉 函 數(shù) 來(lái)計(jì) 算 。 （ 再 由模 2H+1 的 絕 對(duì) 最 小 完 全 剩 余 系 具 有 唯 一 性 得 到 結(jié) 論 ）11 1 0111 1 03 3 3 11 , 0 , 1 ( 0 , 1 , , 1 ) 3 33 3 3 3nnnniiin n nnnx x x x nx i n xx x x x?????? ? ? ? ?? ? ? ?? ? ? ?① 共 有 項(xiàng) ， 當(dāng)時(shí) ， 每 一 項(xiàng) 各 取 個(gè) 值 ，故 共 通 過 個(gè) 數(shù) ；1111 1 0 1 1 010 0 1 1 1 10 0 0 033 3 3 = 3 3 33 ( ) 3 ( ) 3 ( )3nn n n nn n n nnnn n n nx x x x x x x xx x x x x x x xx x x x????????? ? ? ?? ? ? ? ? ? ? ?? ? ? ?? ? ? ? ? ? ? ???? ? ? ?② 在 這 個(gè) 數(shù) 中 ， 若 有則121 1 1 11 1 1 122+13 ( ) 3 ( ) ( ) = 03===3nnn n n nnnnx x x x x xx x x xx x x x????? ? ?? ? ? ? ? ???? ? ????從 而同 理 ， ， ，即 此 個(gè) 數(shù) 中 ， 兩 兩 互 不 相 同 ；+111111 1 03133 3 1133 3 13 3 3 [ , ]21nnnnnnnnnnHHx x x x H HH??????? ? ? ? ??? ? ? ? ?? ? ? ? ??③ 此 個(gè) 數(shù) 中 ， 最 大 值 為3最 小 值 為 3即 通 過 中 的個(gè) 整 數(shù) ， 結(jié) 論 成 立 。 0 1 11, , , , ( 0 , 1 , , 1 )( 0 , 1 , 2 , )mrmm K K K K r mq m r q???? ? ? ?定 理 若 是 一 個(gè) 給 定 的 正 整 數(shù) ， 則 全 部 整 數(shù) 可 分 成個(gè) 集 合 ， 記 作 其 中 是一 切 形 如 的 整 數(shù) 所 組 成 ， 這 些 集 合具 有 下 列 性 質(zhì) ：(i)每一整數(shù)必包含在且僅在上述的一個(gè)集合里面， (ii)兩個(gè)整數(shù)同在一個(gè)集合的充要條件是這兩個(gè)整數(shù) 對(duì)模 m同余 0 1 10 1 1111 , , , , ,mmmK K K ma a a ma a m???定 義 定 理 中 的 叫 做 模 的 剩 余 類 ，一 個(gè) 剩 余 類 中 任 一 數(shù) 叫 做 它 同 類 的 數(shù) 的 剩 余 . 若是 個(gè) 整 數(shù) ， 并 且 其 中 任 何 兩 數(shù) 都 不 同在 一 個(gè) 剩 余 類 里 ， 則 叫 做 模 的 一 個(gè) 完 全 剩余 系 .推論： m個(gè)整數(shù)做成模 m的一個(gè)完全剩余系的充要條 件是兩兩對(duì)模 m不同余 0 ,1 , , 1 ,mm?注 ： 最 常 見 的 完 全 剩 余 系 是 它 們稱 為 模 的 非 負(fù) 最 小 完 全 剩 余 系 .下面例 1給出模 m的另外完全剩余系 —— 絕對(duì)最小完 全剩余系 . , 1 , , 1 , 0 , 1 , , 1 。第二節(jié) 剩余類及完全剩余系 由帶余數(shù)除法我們知道，對(duì)于給定的正整數(shù) m，可以 將所有的整數(shù)按照被 m除的余數(shù)分成 m類。同余的一個(gè)應(yīng)用 —— 檢查因數(shù)的一些方法 110,1 0 1 0 , 0 1 0 .nnn n ia Z aa a a a a?????? ? ? ? ? ?證 ： 將 寫 成 十 進(jìn) 位 數(shù) 的 形 式 ：A、一整數(shù)能被 3（ 9）整除的充要條件是它的十進(jìn)位 數(shù)碼的和能被 3（ 9）整除。222 2 2,1 ( m o d 4 ) 1 ( m o d 4 )2 ( m o d 4 )ababa b c??? ? ?于 是 都 是 奇 數(shù) 。3 3 31 , 3 , , 0 , 1 , 2 .2 1 ( m o d 7 ) 2 1 ( m o d 7 ) 2 1 0 ( m o d 7 ) ,3 , 7 2 1mmnn Z m k m N knm?? ? ? ? ?? ? ? ???解 ： （ ） 都 可 寫 成 的 形 式 其 中因 為 ， 所 以 ， 即從 而 當(dāng) ；3 1 3 22 2 ( m o d 7) 2 4 ( m o d 7) ,3 , 7 2 1mmnnm??????又 ，從 而 當(dāng) 且 僅 當(dāng) 時(shí) .3 3 1 3 22 1 2 ( m o d 7 ) 2 1 3 ( m o d 7 ) , 2 1 5 ( m o d 7 ) , 2 1 7m m mnn??? ? ? ? ? ??（ 2 ） 由 ，可 知 ， 對(duì) 任 何 正 整 數(shù) 不 能 被 整 除 .4 4 , 1 2 3 4 5n n n nnn? ? ?例 、 證 明 當(dāng) 且 僅 當(dāng) 不 能 被 整 除 時(shí) 能 被整 除 ， 其 中 是 正 整 數(shù) 。 （ ）2 ( ) ( ) ( m od )p p pp a b a b p? ? ?例 、 設(shè) 是 素 數(shù) ， 證 明 。( m od ) , ( m od )a b m a b ma a b b ma b m ak bk m?????若 ， 則若 則1111111111111 0 1 05 ( m o d ) , ( m o d ) , 1 , 2 , ,( m o d )( m o d ) , 0 , 1 , , ,( m o d )kkkkkkkkii