模11的简化剩余系

《初等数论》试卷一、 单项选择题：（1分/题×20题=20分） １．设x 为实数，[]x 为x 的整数部分，则( ) Ａ．[][]1x x x ≤<+； Ｂ．[][]1x x x <≤+； Ｃ．[][]1x x x ≤≤+； Ｄ．[][]1x x x <<+． ２．下列命题中不正确的是( ) Ａ．整数12,,,n a a a 的公因数中最大的称为最大公因数； Ｂ．整数12,,,n a a a 的公倍数中最小的称为最小公倍数Ｃ．整数a 与它的绝对值有相同的倍数 Ｄ．整数a 与它的绝对值有相同的约数３．设二元一次不定方程ax by c +=（其中,,a b c 是整数，且,a b 不全为零）有一整数解()00,,,x y d a b =，则此方程的一切解可表为( )Ａ．00,,0,1,2,;abx x t y y t t d d =-=+=±± Ｂ．00,,0,1,2,;abx x t y y t t d d =+=-=±± Ｃ．00,,0,1,2,;bax x t y y t t d d =+=-=±± Ｄ．00,,0,1,2,;bax x t y y t t dd =-=-=±±４．下列各组数中不构成勾股数的是( )Ａ．５，１２，１３； Ｂ．７，２４，２５； Ｃ．３，４，５； Ｄ．８，１６，１７ ５．下列推导中不正确的是( )Ａ．()()()11221212mod ,mod mod ;a b m a b m a a b b m ≡≡⇒+≡+ Ｂ．()()()11221212mod ,mod mod ;a b m a b m a a bb m ≡≡⇒≡ Ｃ．()()111212mod mod ;a b m a a b a m ≡⇒≡ Ｄ．()()112211mod mod .a b m a b m ≡⇒≡ ６．模１０的一个简化剩余系是( ) Ａ．0,1,2,,9; Ｂ．1,2,3,,10;Ｃ．5,4,3,2,1,0,1,2,3,4;----- Ｄ．1,3,7,9. ７．()mod a b m ≡的充分必要条件是( ) Ａ．;m a b - Ｂ．;a b m - Ｃ．;m a b + Ｄ．.a b m +８．设()43289f x x x x =+++，同余式()()0mod5f x ≡的所有解为( ) Ａ．1x =或1;- Ｂ．1x =或4; Ｃ．1x ≡或()1mod5;- Ｄ．无解． 9、设f(x)=10n n a x a x a +++其中()0,mod i a x x p ≡是奇数若为f(x)()0mod p ≡的一个解，则:( )A ．()()mod ()0mod ,1p f x p χχ∂≡≡∂>一定为的一个解 B ．()()0mod ,1,()0mod p f x p χχ∂∂≡∂>≡一定为的一个解C ．()()()00(),()0mod mod ,mod p f x f x p x x p x x p ααα≡≡≡当不整除时一定有解其中 D ．()()()00mod ()0mod ,mod x x p f x p x x p ααα≡≡≡若为的一个解则有 10．()10(),,0mod ,,n n i n f x a x a x a a a p n p =+++≡>/设其中为奇数则同余式()()0mod f x p ≡的解数：（ ） A ．有时大于p 但不大于n; B ．可超过pC ．等于pD ．等于n11．若2为模p 的平方剩余，则p 只能为下列质数中的 :( )A ．3B ．11C ．13D ．23 12．若雅可比符号1a m ⎛⎫=⎪⎝⎭，则 ( ) A ．()2mod ,x a m ≡同余式一定有解B ．()()2,1,mod a m x a p =≡当时同余式有解;C ．()2(,mod m p x a p =≡当奇数)时同余式有解;D ．()2(),mod a p x a p =≡当奇数时同余式有解．13．()()2mod 2,3,2,1,x a a αα≡≥=若同余式有解则解数等于( )A ． 4B ．3C ． 2D ． 1 14． 模12的所有可能的指数为;( )A ．1，2，4B ．1，2，4，6，12C ．1，2，3，4，6，12D ．无法确定 15． 若模m 的单根存在，下列数中，m 可能等于: ( ) A ． 2 B ．3 C ． 4 D ． 12 16．对于模5，下列式子成立的是: ( )A ．322ind =B ．323ind =C ．350ind =D ．3331025ind ind ind =+ 17．下列函数中不是可乘函数的是: ( ) A ．茂陛鸟斯(mobius)函数w(a) ; B ． 欧拉函数()a φ；C ．不超过x 的质数的个数()x π；D ．除数函数()a τ；18． 若x 对模m 的指数是ab ，a >0，ab >0，则x α对模m 的指数是( ) A ．a B ．b C ．ab D ．无法确定 19．()f a ，()g a 均为可乘函数，则( ) A ．()()f a g a 为可乘函数； B ．()()f ag a 为可乘函数 C ．()()f a g a +为可乘函数； D ．()()f a g a -为可乘函数 20．设()a μ为茂陛乌斯函数，则有( )不成立A ．()11μ=B ．()11μ-=C ．()21μ=-D ．()90μ= 二．填空题：（每小题1分，共10分）21． 3在45!中的最高次n ＝ ____________________； 22． 多元一次不定方程：1122n n a x a x a x N +++=，其中1a ，2a ，…，n a ，N 均为整数，2n ≥，有整数解的充分必要条件是___________________；23．有理数ab，0a b <<，)(,1a b =，能表成纯循环小数的充分必要条件是_______________________；24． 设()0mod x x m ≡为一次同余式()mod ax b m ≡，a ≡()0mod m 的一个解，则它的所有解为_________________________；25． 威尔生（wilson ）定理：________________________________________； 26． 勒让德符号5031013⎛⎫⎪⎝⎭=________________________________________； 27． 若)(,1a p =，则a 是模p 的平方剩余的充分必要条件是_____________(欧拉判别条件)； 28． 在模m 的简化剩余系中，原根的个数是_______________________； 29． 设1α≥，g 为模p α的一个原根，则模2p α的一个原根为_____________； 30．()48ϕ=_________________________________。

习题71.证明：当a≡b(mod m)时，对任何正整数，a n≡b n(mod m)。

证明当a≡b(mod m)时，a-b是m的倍数，故从a n-b n＝(a-b)(a n-1＋…＋b n-1)可知也是m的倍数，所以a n≡b n(mod m)。

2.设a、b是非零整数，m是满足m＞|a|＋|b|的正整数，证明：当a≡b(mod m)时，必有a＝b。

证明当a≡b(mod m)时，则存在整数k使得a-b＝mk，于是m＞|a|＋|b|≣|a-b|＝m|k|，有|k|＜1，因而k＝0，故a＝b。

3.用弃九法证明：(1)4568×7391＝30746529；(2)16×937×1559＝23373528。

证明 (1)因为4568≡4＋5＋6＋8≡5(mod 9)，7391≡7＋3＋9＋1≡2(mod 9)，30746529≡3＋7＋4＋6＋5＋2＋9≡0(mod 9)，而2×5≡/0(mod 9)，所以原式计算错误。

(2)因为16≡1＋6≡7(mod 9)，937≡9＋3＋7≡1(mod 9)，1559≡1＋5＋5＋9≡2(mod 9)，23373528≡2＋3＋3＋7＋3＋5＋2＋8≡6(mod 9)，而7×1×2≡/6(mod 9)，所以原式计算错误。

4.完成定理7.9的证明。

证明（1）由定义立得。

（2）若a i＋b≡a j＋b(mod m)（0≢i＜j≢m-1)，则m|(a i-a j)，由(1)知此式不成立。

所以a i＋b≡/a j＋b(mod m)（0≢i＜j≢m-1)，故a0＋b、a1＋b、…、a n-1＋b也是模m的一完全剩余系。

（3）若ba i≡ba j(mod m)（0≢i＜j≢m-1)，则m|b(a i-a j)，而(b，m)＝1，于是m|b(a i-a j)，由(1)知此式不成立。

所以ba i≡/ba j(mod m)（0≢i＜j≢m-1)，故ba0、ba1、…、ba n-1也是模m的一完全剩余系。

模11的简化剩余系
模11的简化剩余系是一种对模11的拓展，为了更好地处理和简化差分过程，可以将数学上的困难转化为更简单的问题。

它的特点主要有以下几点：
1.模11的简化剩余系可以将不同的modulo系采用模11组合起来，从而实现差分最简;
2.其中一个modulo对另一个modulo采用相同的取模方法，从而加快传播，有效减少差分过程;
3.模11简化剩余系可以优化求解精度，从而解决迭代循环卡死的问题;
4.差分过程可以通过简化剩余系利用模11快速传播，并且运算精度可以有效提高，其中最大优势就在于可以把复杂的运算转变成简单的运算，从而提升运算的效率；
5.模11的简化剩余系十分灵活，可以根据应用需要，按照不同的设定来配置，以适应不同的计算环境;
6.模11简化剩余系可以减少系统中消耗太多内存的计算以及调用操作；
7.利用模11简化剩余系可以用更少的数据存储量来进行运算，更加有效的利用存储空间;
8.模11的简化剩余系可以从更高的层次上把复杂的差分运算过程简化，减少了大量的中间变量的存储和运算.。

§3 简化剩余系与欧拉函数定义 欧拉函数()n ϕ是一个定义在正整数集上的函数，()n ϕ的值等于系列0,1,,1n -中与n 互质的整数的个数。

()()()()11,21,32,42,ϕϕϕϕ====当1n >时，()0.n n ϕ<<当p 为质数时，() 1.p p ϕ=-定义 如果一个模m 的剩余类里的数与m 互质（在模m 的一个剩余类中，只要有其中一个数和m 互质，则该剩余类中所有的数就都与m 互质），就把它叫做一个与m 互质的剩余类. 在与m 互质的全部剩余类中，各取一个数所组成的一组数，叫做模m 的一个简化剩余系.定理1 模m 的一个简化剩余系含有()m ϕ个数. 证 模m 的全部剩余类是011,,,m K K K -. 因为,0,1,,1r r K r m ∈=-，所以对每个()01r r m ≤≤-，r K 是一个与m 互质的剩余类的充要条件是(), 1.r m =因此，在模m 的全部剩余类011,,,m K K K -中，与m 互质的全部剩余类是满足条件()01,,1r m r m ≤≤-=的所有剩余类r K . 这样的剩余类公有()m ϕ个，故由简化剩余系的定义知，模m 的简化剩余系含有()m ϕ个数.定理2 若()1,,m a a ϕ是()m ϕ个与m 互质的整数，则()1,,m a a ϕ是模m 的一个简化剩余系的充要条件是它们两两对模m 不同余.证 必要性 设()12,,,m a a a ϕ是模m 的一个简化剩余系，则由简化剩余系的定义，这()m ϕ个数是取自模m 的不同剩余类的，故这()m ϕ个数两两对模m 不同余.充分性 设与m 互质的()m ϕ个整数()12,,,m a a a ϕ两两对模不同余. 因每个整数都与m 互质，故每个整数都属于一个与m 互质的剩余类. 因这()m ϕ个整数两两对模m 不同余，故这()m ϕ个整数分别属于不同的与m 互质的剩余类. 另一方面，与m 互质的剩余类共有()m ϕ个，故()12,,,m a a a ϕ分别属于这()m ϕ个与m 互质的剩余类，故()12,,,m a a a ϕ是模m 的一个简化剩余系.定理3 若(),1,a m x =通过模m 的简化剩余系，则ax 也通过模m 的简化剩余系。

完系、简系、剩余类定义1．剩余类：把关于模m同余的数归于一类，每类称为一个模m的剩余类. 即由关于模m同余的数组成的集合，每一个集合叫做关于模m的一个剩余类(又叫同余类)．共有m个剩余类.设K r是余数为r的剩余类, 则K r＝{qm＋r| m是模, r是余数, q∈Z}＝{a |a∈Z且a≡r(mod m)}.剩余类的性质：⑴Z＝K0∪K1∪K2∪…∪K m−1，当i≠j时，K i∩K j＝Ø；⑵对于∨−n∈Z，有唯一的r∈{0, 1, 2, …, m−1}，使得n∈K r；⑶对∨−a, b∈Z，a, b∈K r ⇔a≡b (mod m)定义2.完系：设K0，K1，…，K m−1是模m的m个剩余类，从K r中各取一数a r 作为代表，则这样的m个数a0，a1，…，a m−1称为模m的一个完全剩余系，简称m的完系. 例如：1, 2, 3, …, m.若一组数y1, y2, …, y s满足：对任意整数a有且仅有一个y j，使得a≡y j (mod m)，则y1, y2, …, y s是模m的完全剩余系.模m的完全剩余系有无穷多个，但最常用的是下面两个：①最小非负剩余系：0, 1, 2, 3, …, m−1；②最小绝对值剩余系：(随m的奇偶性略有区别) 当m＝2k+1时，为−k, −k+1, …, −1, 0, 1, 2, …, k−1, k；当m＝2k时，为−k+1, −k+2, …, −1, 0, 1, 2, …, k或−k, −k+1, …, −1, 0, 1, 2, …, k−2, k−1.例如，集合{0, 6, 7, 13, 24}是模5的一个完全剩余系，集合{0, 1, 2, 3, 4}是模5的最小非负完全剩余系.性质：(i) m个整数构成模m的一完全剩余系⇔两两对模m不同余；(ii) 若(a, m)＝1，则x与ax＋b同时跑遍模m的完全剩余系.完全剩余系的判断方法：定理1：a1, a2,…, a m是模m的一个完全剩余系⇔a i≡／a j (mod m), i≠j；定理2：设(a, m)＝1, b∈Z, 若x1, x2, , x m是模m的一个完全剩余系，则ax1＋b, ax2＋b, …, ax m＋b也是模m的一个完全剩余系；特别地，m个连续的整数构成模m的一个完系.设K r是模的一个剩余类, 若a, b∈K r，则a≡b(mod m), 于是(a, m)＝(b, m).因此，若(a, m)＝1，则K r中的任一数均与m互质, 这样，又可给出如下定义：定义3.简系：如果r与m互质，那么K r中每一个数均与m互质，称K r为与模m互质的剩余类．这样的剩余类共有φ(m)个，从中各取一个代表(共取φ(m)个)，它们称为模m的简化剩余系，简称简系．当m为质数p时，简系由p−1个数组成．又如：m＝6，在模6的六个剩余类中：K1＝{…, −11, −5, 1, 7, 13,…} K5＝{…, −7, −1, 5, 11, 17,…}是与模6互质的剩余类，数组1, 5；7, −7；1, −1；等等都是模6的简系.性质：①K r与模m互质⇔K r中有一个数与m互质；②与模m互质的剩余类的个数等于φ(m)；③若(a, m)＝1, 则x与ax同时跑遍模m的简化剩余系.简化剩余系的判断方法：定理3：a1，a2，…，aφ(m)是模m的简化剩余系⇔(a i, m)＝1, 且a i≡／a j(mod m) (i≠j, i, j＝1, 2, …, φ(m)).定理4：在模m的一个完全剩余系中,取出所有与m互质的数组成的数组,就是一个模m的简化剩余系.定理5：设(k, m)＝1, 若a1, a2, …, aφ(m)是模m的简系, 则ka1, ka2, …, kaφ(m)也是模m的简系.这三个定理中，定理3与定理5是简化剩余系的判别方法，定理4是它的构造方法. 显然，模m的简化剩余系有无穷多个，但常用的是“最小简化剩余系”，即由1，2，…，m －1中与m 互质的那些数组成的数组.说明：由于任何整数都属于模m 的某一剩余类，所以，在研究某些整数性质时，选取适当的(模)m ，然后在模m 的每个剩余类中取一个“代表数”(即组成一个完全剩余系)，当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.例1、设n 为偶数，a 1, a 2,…, a n 与b 1, b 2,…, b n 均为模n 的完全剩余系，试证：a 1＋b 1, a 2＋b 2,…, a n ＋b n 不是模的完全剩余系.证明：假设a 1＋b 1, a 2＋b 2,…, a n ＋b n 是模的完全剩余系. ∴1(1)()1+2++(mod )22n i i i n n n a b n n =++≡≡≡∑ ∵a 1, a 2,…, a n 也是模的完全剩余系. ∴11(1)(mod )22n n i i i n n n a i n ==+≡=≡∑∑，同理有：1(mod )2n i i n b n =≡∑ 1()0(mod )n i i i a b n n =∴+≡≡∑，∴n |n2, 矛盾！故假设不成立，从而原命题成立.例2、设m ＞1, (a , m )＝1，b ∈Z , 求和：∑-=+⋅10}{m i mb i a , 其中{x }为x 的小数部分. 解：∵i 取遍模m 的完系，令x i ＝a ·i ＋b ，则也取遍模m 的完系.故11110000111{}{}{}(1)22m m m m i i i k k x a i b k k m m m m m m m m ----====⋅+-====⨯-=∑∑∑∑总结：若a 1, a 2,…, a m 是模m 的一个完系，则①a 1＋a 2＋…＋a m ≡1＋2＋…＋m (mod m )；②a 1·a 2·……·a m ≡1·2·…·m (mod m )； ③(a 1)n ＋(a 2)n ＋…＋(a m )n ≡1n ＋2n ＋…＋m n (mod m ).例3、已知m , n 为正整数, 且m 为奇数, (m , 2n －1)＝1. 证明：m |∑=m k n k1.证明：∵1, 2, …, m 构成模m 的完系, (m , 2)＝1，∴2, 4, …, 2m 也构成模m 的完系.∴)(mod )2(11m k k m k n m k n ∑∑==≡，即)(mod 0)12(1m k m k n n ≡-∑=. ∵(m , 2n －1)＝1，∴∑=m k n k m 1|得证. 例4、求八个整数n 1, n 2,…, n 8满足：对每个整数k (－2014＜k ＜2014)，有八个整数a 1, a 2,…, a n ∈{−1, 0, 1},使得k ＝a 1n 1＋a 2n 2＋…＋a 8n 8解：令G ＝{k | k ＝a 1＋a 2·2＋a 3·32＋…＋a n +1·3n ，a i ∈{−1, 0, 1}，i ＝1，2，…，n ＋1}.显然max G ＝1＋3＋32＋…＋3n ＝3n +1－12(记为H )，min G ＝－1－3－32＋…－3n ＝－H . 且G 中的元素个数有3n +1＝2H ＋1个， 又∵G 中任意两数之差的绝对值不超过2H ，∴G 中的数对模2H ＋1不同余，∴G 的元素恰好是模2H ＋1的一个绝对值最小的完系，于是凡满足－H ≢k ≢H 的任意整数都属于G ，且可唯一地表示为a 1＋a 2·2＋a 3·32＋…＋a n +1·3n 形式，当n ＝7时，H ＝3208＞2014，而n ＝6时，H ＝1043＜2014，故n 1＝1，n 2＝3，…，n 8＝37为所求.例5、已知p 为大于3的质数，且112＋122＋132＋…＋1(p －1)2＝a b，a ，b ∈N *. (a , b )＝1，证明：p a . 证明：对于不超过p −1的自然数k ，由于(k , p )＝1，所以存在唯一的不超过p −1的自然数x ，满足1(mod )kx p ≡而且，当k ＝1或p −1有x ＝1或p −1，当22k p ≤≤-时，有22,x p x k ≤≤-≠，故当k 取遍1，2，……，p −1时，x 也取遍1，2，……，p −1，因为(,(1)!)1,1(mod )p p kx p -=≡由可得到(1)!(1)!(1)!(mod )(1)!(mod ),p p kx p p p x p k--≡--≡或所以 2211222211((1)!)((1)!)(1)(21)((1)!)((1)!)(mod )6p p k x p a p p p p p x p p b k --==----=≡-≡-∑∑ 因为p 是大于3的素数，所以p −1不小于4，所以(p −1)!含有因数6， 从而2(1)(21)((1)!)0(mod )6p p p p p ---≡，即2((1)!)0(mod )p a p b -≡， 因为(,(1)!)1p p -=，所以2(,((1)!))1p p -=，从而0(mod )0(mod )a p a p b≡⇒≡ 例6、(2003克罗地亚奥林匹克) 对于所有奇质数p 和正整数n (n ≣p )，试证：p n C ≡[n p] (mod p)例7、(第26届IMO) 设n 为正整数，整数k 与n 互质，且0＜k ＜n . 令M ＝{1, 2, …, n −1}(n ≣3), 给M 中每个数染上黑白两种染色中的一种，染法如下：⑴对M 中的每个i ，i 与n −i 同色，⑵对M 中每个i ，i ≠k ，i 与|k −i |同色，试证：M 中所有的数必为同色.证明：∵(k , n )＝1且0，1，2，…，n −1是一个模n 的最小非负完系，∴0·k ，1·k ，2·k ，…，(n −1)·k 也是一个模n 的完全剩余系.若设r j ≡j ·k (mod n )(其中1≢r j ≢n －1，j ＝1，2，…，n －1) ，则M ＝{1，2，…，n −1}＝{121,,,-n r r r } 下面只要证明r j 与r j +1(j ＝1，2，…，n −2)同色即可. 因为若如此，当r 1颜色确定后，M 中所有的数都r 1与同色. 由于(j ＋1)k ≡r j +1(mod n )，则r j ＋k ≡r j +1(mod n )，因此若r j ＋k ＜n ，则r j +1＝r j +k ，由条件⑵知r j +1与| r j +1－k |＝r j 同色；若r j ＋k ＞n ，由r j +1＝r j +k －n ，由条件⑴知k －r j +1＝n —r j 与n －(n —r j )＝r j 同色，即k －r j +1与r j 同色， 由条件⑵知k －r j +1与|k －(k －r j +1)|＝r j +1同色，因此r j +1与r j 同色.综上：此r j +1与r j 同色. 故M 中所有的数必为同色.例8、(2001第42届IMO)设n 为奇数且大于1，k 1, k 2,…, k n 为给定的整数，对于1, 2, …, n 的n !个排列中的每一个排列a ＝(a 1, a 2,…, a n )，记S (a )＝∑=n i i ia k 1，试证：有两个排列b 和c ，使得n !| S (b )－S (c ).证明：假设对任意两个不同的b 和c ，均有S (b )≡／S (c )(mod n !)，则当a 取遍所有1，2，…，n 的n !个排列时， S (a )也取遍模n !的一个完全剩余系，且每个剩余系恰好经过一次，所以()aS a ∑≡1+2+3+…+n !(mod n !)≡12(n !+1)n !≡n !2×n !＋n !2≡n !2(mod n !) (n ＞1)其中()a S a ∑表示对取遍个排列求和(下同)，下面用另一种方法计算1()()ni i a a i S a k a ==∑∑∑：对于k 1，i ∈{1，2，…，n }，a i ＝1时，剩n －1个数，有(n －1)!个排列，a i ＝2时，有(n －1)!个排列，…∴k 1的系数为(n －1)!·(1+2+…+n )＝12(n +1)!. ∴()a S a ∑＝(1)!2n +1n i i k =∑ 但()a S a ∑＝(1)!2n +1n i i k =∑≡0(mod n !) (∵n 为奇数)，∴n !2≡0(mod n !), 矛盾. ∴n !| S (b )－S (c ).例9、设m 是给定的整数. 求证：存在整数a ，b 和k . 其中a ，b 均为奇数，k ≣0，使得2m ＝a 19＋b 99＋k ·21999.另解：设x ，y 为奇数，若x ≡／y (mod 21999)，则x 19－y 19＝(x －y )(x 18＋x 17y ＋…＋xy 17＋y 18)，∵x 18＋x 17y ＋…＋xy 17＋y 18为奇数，∴x 18＋x 17y ＋…＋xy 17＋y 18与21999互质，∴x 19≡／y 19(mod 21999)故当a 取遍模21999的简化剩余系时，a 19也取遍模21999的简化剩余系，∴一定存在a ，使得a 19≡2m －1(mod 21999)，并且有无穷多个这样的a ，故2m －1－a 19＝k ·21999令b ＝1，则2m ＝a 19＋b 99＋k ·21999. 当a 足够小时，不难知k ≣0.。

精心整理王进明初等数论习题及作业解答P17习题1-11，2(2)(3),3，7，11，12为作业。

1．已知两整数相除，得商12，余数26，又知被除数、除数、商及余数之和为454．求被除数.解：1226,1226454,a b a b=++++=12261226454,b b++++=(121)454122626390,b+=---=b=30,被除数a=12b+26=360+26=386.这题的后面部分是小学数学的典型问题之一——“和倍”问题。

2若若(2)证(21)n n-为3(3)证明：利用11n+2+122n+1=121×11n+12×144n=133×11n+12×(144n－11n)及例5的结论．(4)当m，n，l∈N+时，()!!!!m n lm n l++的值总是整数证明：()!m n l++=()(1)(1)()(1)(1)!m n l m n l n l n l n l l l++++-++++-+⋅由k!必整除k个连续整数知：!|()(1)(1)m m n l m n l n l++++-++,n!|()(1)(1)n l n l l++-+，从而由和的整除性即证得命题。

(5)当a ，b ∈Z 且a ≠－b ，n 是双数时，()|()n n a b a b +-；(6)当a ，b ∈Z 且a ≠－b ，n 是单数时，()|()n n a b a b ++．解：利用例5结论：若a≠b ，则()|()n n a b a b --．令b=－b*,即得。

或解： a=(a+b)－b ，(5) 当n 为双数时，由二项式展开()()()()1111n n n n a b n a b b n a b b ---=+-+++-+，证得。

(6)当n 为单数时类似可得。

3．已知a 1，a 2，a 3，a 4，a 5，b ∈Z,且522i a b =，说明这六个数不能都是奇数．51i i a =∑51i i a=∑4由。

剩余类、剩余系、完全剩余系和简化剩余系学习笔记经常在⼀些数论题题解中看到剩余类、剩余系、完全剩余系、简化剩余系这⼏个名词，但总感觉⾃⼰对它们的概念理解得不是很深，⽽且还经常混淆，故写篇博客记录下⾃⼰所理解的剩余系相关知识，如有错误，欢迎路过的⼤佬指正。

剩余类（同余类）定义n n r∈[0,n−1]n C r=n∗x+r,x∈Znn=1145,r=14C14=1145x+141145−1131,14,1159性质剩余系定义n n n x x xnn=1145r={11,4,5,14}114514性质完全剩余系（完系）定义n n n n nnn=5{0,1,2,3,4}5{5,1,8,−3,14}5性质n r a∈Z,b∈Z gcd(n,a)=1a∗r i+b (i∈[0,n−1])n证明：命题 1 ：如果r是⼀个模n的剩余系，那r i+b⼀定也构成⼀个模n的完全剩余系。

反证法，若r i+b不构成⼀个模n的完全剩余系，则存在两个元素同余n，即有r x+b≡r y+b(mod n)，同余式两边同时减去b，有r x≡r y(mod n)，与r是⼀个模n的剩余系这⼀前提⽭盾，命题 1 得证。

命题 2：若r是⼀个模n的完全剩余系，对于任意的整数a，若有gcd(a,n)=1，则a∗r i也构成⼀个模n的完全剩余系。

同样是反证法，若结论不成⽴，则有a∗r x≡a∗r y(mod n)，因为gcd(a,n)=1，所以⼀定存在a mod p的逆元inv(a)，同余式两边同时乘以inv(a)，则有r x≡r y(mod n)，与前提⽭盾，命题 2 得证。

这俩个命题都得证，所以a∗r i构成⼀个模n的完全剩余系，a∗r i+b也构成⼀个模n的完全剩余系，故性质得证。

简化剩余系（既约剩余系、缩系）定义nφ(n)n r nφ(n)φ(n)nn=10{1,3,7,9}10n=5{1,8,7,14}5n n性质n r a∈Z gcd(n,a)=1a∗r i n 参考资料国际惯例。

初 等 数 论 （16）（第二章 同余 第七节 简化剩余系（2））一、复习 二、例题例2 什么样的正整数满足ϕ (2x ) = ϕ (3x )解 设x =2a 3b y ，其中ab 为非负整数，y |6/。

若b > 0，（a 、b 大于或等于0）则ϕ (2x ) =ϕ (2a +1) ϕ (3b ) ϕ (y ) =2a ×3b -1×(3-1)ϕ (y ) ϕ (3x ) =ϕ (2a ) ϕ (3b +1) ϕ (y ) =2a -1×3b ×(3-1)ϕ (y )这时ϕ (2x )和ϕ (3x )不会相等。

所以在ϕ (2x ) =ϕ (3x )时，b = 0，x =2a y 。

这时，ϕ (2x ) =2a ×ϕ (y )，ϕ (3x ) =2×ϕ (2a )×ϕ (y )由ϕ (2x ) = ϕ (3x )得 ϕ (2a ) =2a -1， (a > 0)故 x =2a y ，a 为正整数，y |6/。

例如 x = 215×35，则ϕ (2×215×35) =215×ϕ (35)ϕ (3×215×35) =（3 - 1）×214×ϕ (35)例3 证明：n n 41)(=ϕ不可能成立。

证明 若n n 41)(=ϕ，则n 4。

设k p p p n αααα 21212=，其中p i为奇质数，a ≥ 2，则k k p p p n αααα 21212241-=)1()1(2)(111211121--=----k k p p p p p n k ααααϕ，于是)1()1)(1(22121---=k k p p p p p p上式右边为偶数，左边为奇数，矛盾。

故不存在n ，使得n n 41)(=ϕ。

例4 设m 与n 是正整数，证明：ϕ (mn )ϕ ((m ，n )) = (m ，n )ϕ (m )ϕ (n )。

在模11的剩余类的阶模11的剩余类的阶是指一个整数在模11的剩余类中循环的长度。

下面将以一种生动、全面且有指导意义的方式来解释模11的剩余类的阶。

首先，让我们来看一下如何求模11的剩余类的阶。

以整数5为例，我们可以从5开始，不断地将其乘以自身，并对11取余。

我们可以观察到，当我们得到1时，这个序列就开始循环了。

具体来说，我们会得到如下的序列：5, 3, 4, 9, 1, 5, 3, 4, 9, 1...... 这个序列循环的长度就是5的模11剩余类的阶。

接下来，让我们探讨一下为什么模11的剩余类的阶对我们有指导意义。

首先，了解一个数在模11剩余类中的阶，可以帮助我们理解这个数之间的关系。

例如，在上述序列中，我们可以看出5和1是等价的，它们在模11的剩余类中是相同的。

这意味着，对于模11来说，5和1可以互相替代，具有相同的性质。

这种等价关系在数论和代数中经常出现，对于解决一些数学问题具有重要作用。

其次，模11的剩余类的阶还可以帮助我们解决一些关于模11的问题。

例如，我们可以用模11的剩余类的阶来确定一个数是否是11的倍数。

根据模11中剩余类的阶的定义，如果一个数的模11剩余类的阶是1，则其是11的倍数。

这种方法可以帮助我们快速判断一个数是否是11的倍数，而无需进行繁琐的除法运算。

最后，模11的剩余类的阶还可以让我们更好地理解模11的结构。

通过观察模11的剩余类的阶，我们可以发现模11的剩余类可以划分为几个不同的循环。

在上述序列中，我们可以看到，剩余类5、3、4和9彼此循环，形成了一个循环结构。

这种结构可以帮助我们更好地理解模11的运算规律，并应用到更复杂的问题中。

综上所述，模11的剩余类的阶是一个重要的数学概念。

它不仅可以帮助我们理解数之间的关系，解决数学问题，还可以让我们更深入地了解模11的结构。

在学习数论和代数时，我们应该重视模11的剩余类的阶，并将其运用到实际问题中，以拓宽我们的数学视野。