【文章內(nèi)容簡(jiǎn)介】 bad ? 即 )(moddba? 同余式性質(zhì)的應(yīng)用 20xx 年 5月 9日是星期五，問此后的第 20xx2 220xx天 是星期幾？ （解） )7( m o d52)2(52 2667320xx ??? )7(m od521 2667 ?? )7(mod9? )7(mod2? 設(shè)十進(jìn)制整數(shù) 011 aaaan kk ????? ? ?，則 n3 ? 0113 aaaa kk ???? ? ? n9 ? 0119 aaaa kk ???? ? ? （證）因 )3( m o d101010 0110111 aaaaaaaan kkkkkk ?????????? ??? ?? )9( m o d101010 0110111 aaaaaaaan kkkkkk ?????????? ??? ?? 設(shè)整數(shù) n 的 1000 進(jìn)制表示式為 0111 100010001000 aaaan kkkk ????? ?? ? 則 n)1311(7 ，或或 ? )()()1311(7 3120 ?? ????? aaaa，或或 （證）因 0111 100010001000 aaaan kkkk ????? ?? ? )7( m o d)1()1()1( 0111 aaaa kkkk ???????? ?? ? )11( m o d)1()1()1( 0111 aaaan kkkk ???????? ?? ? 南京師范大學(xué)泰州學(xué)院本科畢業(yè)論文 8 )13( m o d)1()1()1( 0111 aaaan kkkk ???????? ?? ? 判斷 12345678?n 能否被 )1311(7 ，或或 整除： 6 7 81 0 0 03 4 51 0 0 0121 2 3 4 5 6 7 8 2 ????? 而 3 4 53 4 5)6 7 812( ??? 不能被 1 13 整除 故 12345678 不能被這 3 個(gè)數(shù)整除。 設(shè)十進(jìn)制整數(shù) 011 aaaan kk ??? ，則 n11 ? )()(11 3120 ?? ????? aaaa n2 ? 02a n4 ? 104 aa ? 0124 aa ? n8 ? 2108 aaa ? 210 428 aaa ?? ni2 ? 01212 aaaa iii ??? 如，判斷 n＝ 981234576 能否被 1 16整除。 因 （ 6+5+3+1+9）－（ 7+4+2+8）＝ 3， 故 n 不能被 11 整除 。 因 62 ，故 n2 ）（ 76|4 或 22672|4 ??? ）（ ， 故 ）（ n4 。 因 40654|8 ??? ）（ ， 故 n8 。 因 ）（ 16m o d067105448 ??????? ， 故 n16 。 剩余 類 和完全剩余系 我們?cè)谏厦嬉M(jìn)了同余的概念，由于有了同余的概念，我們就可以把同余相同的數(shù)放在一起，這樣就產(chǎn)生了剩余類的概念。 設(shè) m 為正整數(shù)，記 ? ?)( m o d, mcaZccC a ??? ， aC 非空，至少 aCa? 設(shè) m 是一個(gè)正整數(shù)，則 )(i 任一整數(shù)必包含在某個(gè) rC 中， 10 ??? mr 南京師范大學(xué)泰州學(xué)院本科畢業(yè)論文 9 )(ii ba CC? ? )(modmba? )(iii ??baCC ? )(modmba? aC 叫做模 m 的 a 的剩余類 ,一個(gè)剩余類中的任一個(gè)數(shù)叫做該類的剩余或代表。 若 1,2,1,0 , ?mrrrr ? 是 m 個(gè)整數(shù)，且其中任何兩個(gè)都不在同一個(gè)剩余類中，則稱 1,2,1,0 , ?mrrrr ?為模 m 的一個(gè)完全剩余系。 【注】每個(gè)剩余類中都包含了無窮多個(gè)整數(shù)，而完全剩余系則恰好由 m 個(gè)數(shù)組成。 模 m 的剩余類共有 m 個(gè)，例如 1,2,1,0 , ?mCCCC ? 設(shè) m ＝ 10，則 aC ＝ ? ?Zkka ?? 10 ,是模 m ＝ 10 的剩余類。 模 10 的 完全 剩余系舉例： （ 1） 0， 1， 2， ? ， 9 （ 2） 1， 2， 3， ? ， 10 （ 3） 0，－ 1，－ 2， ? ，－ 9 （ 4） 0， 3， 6， 9， ? ， 27 （ 5） 10， 11， 22， 33， 44， ? ， 99 （ 6） 20， 1，－ 18， 13， 64，－ 55，－ 94，－ 3， 18， 9 剩余類和完全剩余系的相關(guān)性質(zhì)： 整數(shù) 1,2,1,0 , ?mrrrr ? 為 m 的一個(gè)完全剩余系 ? )(modmrr ji ? 。 其中 )10( ??? mji ? 如： m 的典型完全剩余系： 最小非負(fù)完全剩余系： 0， 1， ? ， m － 1 最小正完全剩余系： 1， 2， ? ， m 最大非正完全剩余系： 0，－ 1， ? ，－ (m － 1) 最大負(fù)完全剩余系：－ 1，－ 2， ? ，－ m 設(shè) a 是滿足 1),( ?ma 的整數(shù)， b 為任意整數(shù)。若 x 遍歷模 m 的一個(gè)完全剩余系，則 bax? 遍歷模 m 的一個(gè)完全剩余系。 （證）設(shè) 1,2,1,0 , ?mrrrr ? 為 m 的一個(gè)完全剩余系。 因?yàn)?)(modmrr ji ? )10( ??? mji ? 又 1),( ?ma ，故 )(mod marar ji ? 從而 )(m od mbarbar ji ??? 所以， barbarbar m ??? ?110 , ?，是模 m 的一個(gè)完全剩余系。 如 :設(shè) m ＝ 10，原剩余系為 0， 1， ? ， 9。 當(dāng) a ＝ 7， b ＝ 5時(shí)，新的剩余系為： 5， 12， 17， ? ， 68 當(dāng) a ＝ 3， b ＝ 6時(shí)，新的剩余系為： 6， 9， 12， ? ， 33 南京師范大學(xué)泰州學(xué)院本科畢業(yè)論文 10 設(shè) 21,mm 是兩個(gè)互素的正整數(shù)，若 21,xx 分別遍歷 21,mm 的完全剩余系，則1221 xmxm ? 遍歷模 21,mm 的完全剩余系。 （證）當(dāng) 21,xx 分別遍歷 21,mm 個(gè)整數(shù)時(shí)， 1221 xmxm ? 遍歷 21mm 個(gè)整數(shù)。 問題轉(zhuǎn)化為：證明 21mm 個(gè)整數(shù) 1221 xmxm ? 模 21mm 兩兩不同余。 用反證法：若存在 21,xx 和 21,yy 滿足 )( m o d 2112211221 mmymymxmxm ??? 則 由同余的性質(zhì) 知 )( m o d 112211221 mymymxmxm ??? 即 )( m o d 112121 mymxmm ? 而 1),( 21 ?mm ，故由同余的性質(zhì)知 )(mod 111 myx ? 同理可證 ， )(mod 222 myx ? 如： 設(shè) qp, 是兩個(gè)不同的素?cái)?shù)， pqn? ，則對(duì)任意整數(shù) c ，存在唯一的一對(duì)數(shù) x 和 y ，滿足 )(m od nqxpyc ?? ， px??0 ， qy??0 （證）首先知 qp, 互素。 再由定理 ，當(dāng) yx, 分別遍歷模 qp, 的完全剩余系時(shí)， qxpy? 遍歷模 pqn? 的完全剩余系。故存在唯一的一對(duì)整數(shù) yx, ，滿足上式。 簡(jiǎn)化剩余系和歐拉函數(shù) 歐拉函數(shù) 設(shè) n 為正整數(shù)，則 1,2,?, n 中與 n 互素的整數(shù)的個(gè)數(shù)，記作 )(n? ，叫做歐拉（ Euler）函數(shù)。 如： 設(shè) n ＝ 10，則 1,2,?,10 中與 10 互素的數(shù)為 1,2,7,9，故 4)10( ?? 再如： 1)1( ?? ， 1)2( ?? ， 2)3( ?? ， 2)4( ?? ， 2)6( ?? ，即 1,2,?,6 中與 6互素的數(shù)為 1， 5 8)20( ?? ，即 1,2,?,20 中與 20 互素的數(shù)為 1,3,7,9,11,13,17,19。 歐拉函數(shù)的性質(zhì) 設(shè) p 為素?cái)?shù)，則 1)( ?? pp? 。 南京師范大學(xué)泰州學(xué)院本科畢業(yè)論文 11 設(shè) p 為素?cái)?shù)，且整數(shù) 1?a ，則 )11()(ppp aa ??? 證明： （證） 1,2,?, ap 中與 p 不互素的數(shù)共有 1?ap 個(gè)，這些數(shù)是 p ， 2p ， 3p ， 4p ， ? ， 1?ap ， ap 由此即 )11()1()( 11ppppppp aaaaa ?????? ???。 設(shè)整數(shù) pqn? ，其中 qp, 為不同的素?cái)?shù)，則 )1)(1()()()()( ????? qpqppqn ???? （證）設(shè)整數(shù) a 滿足 na??1 ，若 1),( ?dna ? ，則必有 tqdspd ?? 或 （因?yàn)?n 的因數(shù)只有 npqqp ?,1 ） 即必有 dqdp 或 ，從而有 aqap 或 這說明與 n 不互素的數(shù) a 必為 tqaspa ?? 或 。 這樣的 a 為 p ， 2p ， 3p ， 4p ， ? ， pq )1( ? ， pq 和 q ， 2q ， 3q ， 4q ， ? ， qq )1( ? ， pq 共有 1??qp 個(gè) ∴ )()()1)(1()1()()( qpqpqppqpqn ???? ??????