同余问题的讨论-应用数学毕业论文(编辑修改稿)

同余问题的讨论-应用数学毕业论文(编辑修改稿)内容摘要：

bad  即 )(moddba 同余式性质的应用 20xx 年 5月 9日是星期五，问此后的第 20xx2 220xx天 是星期几。 （解） )7( m o d52)2(52 2667320xx  )7(m od521 2667  )7(mod9 )7(mod2 设十进制整数 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    设整数 n 的 1000 进制表示式为 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    南京师范大学泰州学院本科毕业论文 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 个数整除。 设十进制整数 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。 剩余 类 和完全剩余系 我们在上面引进了同余的概念，由于有了同余的概念，我们就可以把同余相同的数放在一起，这样就产生了剩余类的概念。 设 m 为正整数，记  )( m o d, mcaZccC a  ， aC 非空，至少 aCa 设 m 是一个正整数，则 )(i 任一整数必包含在某个 rC 中， 10  mr 南京师范大学泰州学院本科毕业论文 9 )(ii ba CC  )(modmba )(iii baCC  )(modmba aC 叫做模 m 的 a 的剩余类 ,一个剩余类中的任一个数叫做该类的剩余或代表。 若 1,2,1,0 , mrrrr  是 m 个整数，且其中任何两个都不在同一个剩余类中，则称 1,2,1,0 , mrrrr 为模 m 的一个完全剩余系。 【注】每个剩余类中都包含了无穷多个整数，而完全剩余系则恰好由 m 个数组成。 模 m 的剩余类共有 m 个，例如 1,2,1,0 , mCCCC  设 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 剩余类和完全剩余系的相关性质： 整数 1,2,1,0 , mrrrr  为 m 的一个完全剩余系  )(modmrr ji 。 其中 )10(  mji  如： m 的典型完全剩余系： 最小非负完全剩余系： 0， 1， „ ， m － 1 最小正完全剩余系： 1， 2， „ ， m 最大非正完全剩余系： 0，－ 1， „ ，－ (m － 1) 最大负完全剩余系：－ 1，－ 2， „ ，－ m 设 a 是满足 1),( ma 的整数， b 为任意整数。 若 x 遍历模 m 的一个完全剩余系，则 bax 遍历模 m 的一个完全剩余系。 （证）设 1,2,1,0 , mrrrr  为 m 的一个完全剩余系。 因为 )(modmrr ji  )10(  mji  又 1),( ma ，故 )(mod marar ji  从而 )(m od mbarbar ji  所以， barbarbar m  110 , ，是模 m 的一个完全剩余系。 如 :设 m ＝ 10，原剩余系为 0， 1， „ ， 9。 当 a ＝ 7， b ＝ 5时，新的剩余系为： 5， 12， 17， „ ， 68 当 a ＝ 3， b ＝ 6时，新的剩余系为： 6， 9， 12， „ ， 33 南京师范大学泰州学院本科毕业论文 10 设 21,mm 是两个互素的正整数，若 21,xx 分别遍历 21,mm 的完全剩余系，则1221 xmxm  遍历模 21,mm 的完全剩余系。 （证）当 21,xx 分别遍历 21,mm 个整数时， 1221 xmxm  遍历 21mm 个整数。 问题转化为：证明 21mm 个整数 1221 xmxm  模 21mm 两两不同余。 用反证法：若存在 21,xx 和 21,yy 满足 )( m o d 2112211221 mmymymxmxm  则 由同余的性质 知 )( m o d 112211221 mymymxmxm  即 )( m o d 112121 mymxmm  而 1),( 21 mm ，故由同余的性质知 )(mod 111 myx  同理可证 ， )(mod 222 myx  如： 设 qp, 是两个不同的素数， pqn ，则对任意整数 c ，存在唯一的一对数 x 和 y ，满足 )(m od nqxpyc  ， px0 ， qy0 （证）首先知 qp, 互素。 再由定理 ，当 yx, 分别遍历模 qp, 的完全剩余系时， qxpy 遍历模 pqn 的完全剩余系。 故存在唯一的一对整数 yx, ，满足上式。 简化剩余系和欧拉函数 欧拉函数 设 n 为正整数，则 1,2,„, n 中与 n 互素的整数的个数，记作 )(n ，叫做欧拉（ Euler）函数。 如： 设 n ＝ 10，则 1,2,„,10 中与 10 互素的数为 1,2,7,9，故 4)10(  再如： 1)1(  ， 1)2(  ， 2)3(  ， 2)4(  ， 2)6(  ，即 1,2,„,6 中与 6互素的数为 1， 5 8)20(  ，即 1,2,„,20 中与 20 互素的数为 1,3,7,9,11,13,17,19。 欧拉函数的性质 设 p 为素数，则 1)(  pp。 南京师范大学泰州学院本科毕业论文 11 设 p 为素数，且整数 1a ，则 )11()(ppp aa  证明： （证） 1,2,„, ap 中与 p 不互素的数共有 1ap 个，这些数是 p ， 2p ， 3p ， 4p ， „ ， 1ap ， ap 由此即 )11()1()( 11ppppppp aaaaa  。 设整数 pqn ，其中 qp, 为不同的素数，则 )1)(1()()()()(  qpqppqn  （证）设整数 a 满足 na1 ，若 1),( dna  ，则必有 tqdspd  或 （因为 n 的因数只有 npqqp ,1 ） 即必有 dqdp 或 ，从而有 aqap 或 这说明与 n 不互素的数 a 必为 tqaspa  或。 这样的 a 为 p ， 2p ， 3p ， 4p ， „ ， pq )1(  ， pq 和 q ， 2q ， 3q ， 4q ， „ ， qq )1(  ， pq 共有 1qp 个 ∴ )()()1)(1()1()()( qpqpqppqpqn  。