【文章內(nèi)容簡介】 r m a m r m??? ? ? ? ?對 模 有 個 剩 余 類 在 中,.mmm1 、 定 義 ： 如 果 一 個 模 的 剩 余 類 里 面 的 數(shù) 與 互 質(zhì)就 把 它 叫 做 一 個 與 模 互 質(zhì) 的 剩 余 類15156 , , , ( , 6) ( 1 , 6) 1 ,( , 6) ( 5 , 6) 1 , ( , ) 1.m a K K aa a m K K? ? ? ?? ? ?例 當(dāng) 時 有 若即 此 時 的 與 ， 有0 , 1 , , 1mmm?注 ： 由 定 義 ， 要 找 出 所 有 與 模 互 質(zhì) 的 剩 余 類 ，只 需 找 出 序 列 中 所 有 與 互 質(zhì) 的 數(shù) 即 可得 到 ， 而 與 模 互 質(zhì) 的 數(shù) 的 個 數(shù) 則 可 通 過 歐 拉 函 數(shù) 來計 算 。()0 , 1 , , 1aaaa??2 、 定 義 ： 歐 拉 函 數(shù) 是 定 義 在 正 整 數(shù) 上 的函 數(shù) ， 它 在 正 整 數(shù) 上 的 值 等 于 序 列 中 與互 質(zhì) 的 數(shù) 的 個 數(shù) ., ( ) 1 .m p p p?? ? ?注 ： 當(dāng) 時mm3 、 定 義 ： 在 與 模 互 質(zhì) 的 全 部 剩 余 類 中 ， 從 每 一 類各 取 一 數(shù) 所 作 成 的 數(shù) 的 集 合 ， 叫 做 模 的 一 個 簡 化 剩 余 系 .1 2 ( )1 2 ( )2 , , , ( ), , ,.mma a a m mm a a a m???定 理 、 若 是 個 與 模 互 質(zhì) 的 整 數(shù) ，并 且 兩 兩 對 模 不 同 余 ， 則 是 模 的 一 個 簡化 剩 余 系4 , 8 , 1 6 , 2 8 , 3 2 , 4 4 , 5 2 , 5 6 1 5例 ： 判 定 是 否 為 模 的 簡 化 剩 余 系 ？簡化剩余系的判定定理 8 4 4 , 8 8 ,1 6 1 , 2 8 1 3 , 3 2 2 , 4 4 1 4 , 5 2 7 , 5 6 1 1 ( m o d 1 5 ) ,15? ??? ? ? ? ? ?解 ： 此 序 列 包 含 (15)= 個 數(shù) ， 而均 與 模 互 質(zhì) ， 并 且 兩 兩 不 同 余 ， 故 可 作 成 模 15的 一 個 簡 化 剩 余 系 .5 2 ( , ) 1 , ,.a m x ma x m?、 定 理 ： 若 通 過 模 的 簡 化 剩 余 系 則通 過 的 簡 化 剩 余 系1 2 1 21 2 2 1 1 2 1 26 4 , , +.m m x xm m m x m x m m、 定 理 ： 若 是 兩 個 互 質(zhì) 的 正 整 數(shù) ， ，分 別 通 過 模 的 簡 化 剩 余 系 則 通 過的 簡 化 剩 余 系1 2 1 22 1 1 2 1 212( ) ( ) ( )m m m mm x m x m mmm? ? ??分 析 ： 若 要 根 據(jù) 簡 化 剩 余 系 的 條 件 來 判 定 ， 則 要討 論 與 的 數(shù) 量 關(guān) 系 ， 但 此 為 未 知 關(guān)系 ， 故 問 題 轉(zhuǎn) 換 為 證 明 通 過 模 的 一 個 完全 剩 余 系 中 一 切 與 模 互 質(zhì) 的 整 數(shù) 即 可 。1 2 1 21 2 2 1 1 212, , ,( , ) 1 , 1x x m mm m m x m xmm??證 ： ① 若 分 別 通 過 模 的 完 全 剩 余 系則 （ ）通 過 的 完 全 剩 余 系 .1 1 2 21 2 1 2 2 1 12 1 1 2 1 1 2 2 1 22 1 1 2 1 21 ( , ) 1 , ( , ) 1 , 1( ) 1( + ) 1 ( + ) 1( + ) 1x m x mx x m m m x mm x m x m m x m x mm x m x m m????? ? ??在 （ ） 中 ， 若 即 集 合 （ ） 中 的， 通 過 模 ， 的 簡 化 剩 余 系 ， 則 ， ， 同 理 ，2 1 1 2 2 1 1 2 1 21 1 2 2 1 2 1 2+ ( + ) 1( , ) 1 , ( , ) 1 ,m x m x m x m x m mx m x m x x m m???② 反 之 ， 在 中 ， 若 ， ，則 即 ， 通 過 模 ， 的 簡化 剩 余 系 .1 2 1 2 1 2( , ) 1 ( ) ( ) ( )m m m m m m? ? ???推 論 ： 若 ， 則1212127 5 ,1 1 1( ) 1 1 1kkka p p paap p p???????? ? ? ?? ? ? ???? ? ? ?? ? ? ? ??、 定 理 ： 設(shè) 則? ? ? ? ? ?1212() kka p p p ???? ? ? ??證 ： ①? ? 1 , 21 , 2p p p pp p pp? ? ? ????② 等 于 從 減 去 ， ， 中 與 不 互 質(zhì) 的數(shù) 的 個 數(shù) ， 亦 等 于 從 減 去 ， ， 中 與 不 互 質(zhì)（ 即 被 整 除 ） 的 數(shù) 的 個 數(shù) .11 , 2 ,pp p pp??? ??? ?????而 ， ， 中 被 整 除 的 數(shù) 的 個 數(shù) 是? ? 1=.p p p? ? ?? ??故? ? ? ? ? ?1 1 2 2 1111 1 2 212()1 1 11 1 1kkkkka p p p p p pap p p??? ? ? ?????? ? ? ???? ? ? ?? ? ? ???? ? ? ?? ? ? ? ??③ 由 ① 、 ② 得8 、 下 面 給 出 歐 拉 函 數(shù) 的 一 些 性 質(zhì)1 = 2 = 1 , 3 2mm? ? ??① （ ） （ ） 當(dāng) 時 ， （ ）( ) ( )n m n m???②( ) ( )( , ) ( )()d m nm n d mnd??????③ 當(dāng) 時 ， 有( , )11111( ) 111p m p np m np m nppm n m n m npp?? ? ? ???? ? ? ??? ? ? ? ?? ? ????????????????證 ：( , )1111( , ) 11( , )p m p np m nmnppmnm n p? ? ? ???? ? ? ?? ? ? ????????????( ) ( ) ( ) ( )1 ()()m n d m nddd? ? ? ?????( ) ( )2 nn n n n n??? ? ?④ ， 當(dāng) 為 合 數(shù) 時 ，1( 4 ) 2 ( )( ) 22( ) 2 3 ,316 , ( )3kklnZn n nnn n k Znn n k l Zn n n??????????? ? ?? ? ??例 、 設(shè) ， 證 明 ：① 若 是 奇 數(shù) ， 則② 的 充 要 條 件 是 ，③ 的 充 要 條 件 是 ，④ 若 則( 4 ) ( 4 ) ( ) 2 ( )n n n? ? ? ???證 ： ①111( ) 2 , ( 2 ) 2 1 222k k k knn ? ???? ? ? ? ? ?????② 若 則111111 1 1( ) ( )11222( ) , 1 2kknnnnnnn n n n?????? ? ? ?所 以 ， 即1111 1 11( ) , 2 ,21( ) ( 2 ) ( 2 ) ( ) 2 ( )2kk k kn n n n nn n n n n?? ? ? ? ??? ? ?? ? ? ?（ ） 若 設(shè) 為 奇 數(shù) . 則 由( ) 2 3 , ( 2 ) ( 3 )1 1 12 1 3 12 3 3k l k lklnnn? ? ???? ? ? ?? ? ? ?? ? ? ?? ? ? ?③ 若 則 ( ) =111111 1 11( ) , 2 3 , ( 6 ,3()11( ) ( 2 ) ( 3 ) ( )33( ) , 1 , 2 3klklkln n n n nnn n n nnn n n n??? ? ? ??? ? ?? ?