设有代数系统U=，试证明:恒等关系是U上的同余关系。离散数学

所谓同余关系，顾名思义：相同余数，用数学语言描述就是：x,y∈s， 当且仅当 x≡y （mod）n（x≡y （mod）n 表示x，y除以n的余数相同）称此关系为模n的同余关系。举例：5和1除以2都余1 ，300和2除以2都余0，这些都叫同余。

同余关系是代数系统的集合中的等价关系，并且在运算的作用下，能够保持关系的等价类。以二元运算为例，在a1*a2中，如果用集合S中与a1等价的任何其他元素b1代换a1，并且用与a2等价的任何其他元素b2代换a2，则所求的结果b1*b2与a1*a2位于同一等价类之中。此外，同余关系与运算密切相关。如果一个代数结构中有多个运算，则需要考察等价关系对于所有这些运算是否都有代换性质。如果等价关系在一个运算上不满足代换性质，该等价关系就不是代数系统上的同余关系。

同余，指的是同余定理，数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。数学上，两个整数除以同一个整数，若得相同余数，则二整数同余（英文：Modular arithmetic，德文：Kongruenz）。同余理论常被用于数论中。最先引用同余的概念与符号者为德国数学家高斯。同余理论是初等数论的重要组成部分，是研究整数问题的重要工具之一，利用同余来论证某些整除性的问题是很简便的。同余是数学竞赛的重要组成部分。1、同余符号两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。记作：a≡b (mod m)，读作：a同余于b模m，或读作a与b对模m同余，例如26≡2(mod 12)。2、定义设m是大于1的正整数，a、b是整数，如果m|(a-b)，则称a与b关于模m同余，记作a≡b(mod m)，读作a与b对模m同余。显然,有如下事实（1）若a≡0(mod m)，则m|a；（2）a≡b(mod m)等价于a与b分别用m去除，余数相同。

同余式的意义：表示同余关系的数学表达式，与等式相似。将等式中的等号“=”换成同余符号“≡”，必要时在式尾缀以(mod m) 注明模m（即除数），就是同余式。含有未知数的同余式叫做同余方程，通常要求整数解。定义：如果两个正整数 a和 b之差能被 n整除，那么我们就说 a和 b对模n同余，记作：a ≡b  (mod n)运算：同余式运算类似于等式的运算，在等号两边可进行加减乘除的算术运算。如 a≡b (mod n) ，则有：a + c ≡b + c  (mod n)a -  c ≡b - c  (mod n)a ·c ≡b ·c  (mod n)但在应用除法运算时应特别注意:若c与n互质,则有 a / c ≡ b / c ( mod n )简单解释: 如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m) （就是说同余式两边可以同时除以一个和模数互质的数）。证明：条件告诉我们，ac-mp = bc-mq，移项可得ac-bc = mp-mq，也就是说(a-b)c = m(p-q)。这表明，(a-b)c里需要含有因子m，但c和m互质，因此只有可能是a-b被m整除，也即a≡b(mod m)。若a / c ≡ b / c ( mod n ) , 则不一定有c与n互质.反例: 4 ≡ 64 (mod 10)   两边同除以c = 2 (n = 10)2 ≡ 32 (mod 10)

正整数集S，x，y∈S，定义关系R：＜x，y＞∈R 当且仅当 x≡y （mod）n（x≡y （mod）n 表示x，y除以n的余数相同）称此关系为模n的同余关系。可以验证此关系是一个等价关系

当然算是同余关系。余数都是0，也是余数相同，所以也是关于这个数的同余关系。例如4；6；8都能被2整除。所以4；6；8关于2同余。

一个关系满足自反、对称、传递叫做等价关系。模M同余关系作为关系的一种，也满足以上三条，当然是同余关系了。比如10与10模3同余，这是自反；10与4模3同余，则4与10模3同余，即模3同余有等价性。10与4模3同余，4与7模3同余，则10与7模3同余，这是传递性。

在群的特殊情况下，同余关系可以用基本术语描述为: 如果 G 是群(带有单位元 e)并且 ~ 是在 G 上的二元关系，则 ~ 是同余只要:给定 G 的任何元素 a，a ~ a (自反关系)。给定 G 任何的元素 a 和 b，如果 a ~ b，则 b ~ a (对称关系)。给定 G 的任何元素 a, b 和 c，如果 a ~ b 并且 b ~ c，则 a ~ c (传递关系)。给定 G 的任何元素 a, a" , b 和 b" ，如果 a ~ a" 并且 b ~ b" ， 则 a * b ~ a" * b" 。给定 G 的任何元素 a 和 a" ，如果 a ~ a" ，则 a^(-1) ~ a"^(-1) (这个条件可以从其他四个条件证明，所以严格上是冗余的)。

同余式是表示同余关系的数学表达式，与等式相似。将等式中的等号“=”换成同余符号“≡”，必要时在式尾缀以(mod m) 注明模m（即除数），就是同余式。

Z={3k|k属于Z}U{3k+1|k属于Z}U{3k+2|k属于Z}

同余 ~ 完全确定自 G 的同余于单位元的那些元素的集合 {a ∈ G : a ~ e}，而这个集合是正规子群。特别是，a ~ b 当且仅当 b * a ~ e。所以替代谈论在群上同余，人们通常以正规子群的方式谈论它们；事实上，所有同余都唯一的对应于 G 的某个正规子群。

如同任何同余关系，对于模同余是一种等价关系，整数的等价类是一个集合，标记为。由对于模同余的所有整数组成的这个集合称为同余类（congruence class或residue class）；假若从上下文知道模，则也可标记为。同余类中的每个元素都可以拿来代表该同余类，称为该同余类的代表数。

这不是数学函数的吧，绕道

我不太清楚同余关系的定义, 按我的理解给个定义:G上的一个等价关系"≡", 若满足对任意a ≡ b, c ≡ d, 恒有ab ≡ cd, 则称"≡"为G上的一个同余关系.如果是这种定义, 那么G上的同余关系与G的正规子群是一一对应的.设"≡"是G上的一个同余关系, e为G的单位元.考虑G的子集H = {h ∈ G | h ≡ e}.可以验证H是G的一个子群:1. 任意a, b ∈ H, 有a ≡ e, b ≡ e, 由"≡"是同余关系, 得ab ≡ e, 即有ab ∈ H.2. 任意a ∈ H, 有a ≡ e, 而由"≡"是等价关系, 有a^(-1) ≡ a^(-1), 于是e = a·a^(-1) ≡ a^(-1).即a^(-1) ≡ e, 也即a^(-1) ∈ H.进而可以验证H是G的正规子群:对任意a ∈ H, g ∈ G, 有g^(-1) ≡ g^(-1), a ≡ e, g ≡ g, 于是g^(-1)·a·g ≡ g^(-1)·g = e.即g^(-1)·a·g ∈ H.设H是G的一个正规子群.定义G上的关系: a ≡ b当且仅当a^(-1)·b ∈ H (其实就是按左陪集分类).可以验证"≡"是一个等价关系:1. 对任意a ∈ G, 有a^(-1)·a = e ∈ H (H是子群, 故包含单位元), 即有a ≡ a.2. 若a, b ∈ G满足a ≡ b, 即有a^(-1)·b ∈ H.由H是子群, 有b^(-1)·a = (a^(-1)·b)^(-1) ∈ H, 即有b ≡ a.3, 若a, b, c ∈ G满足a ≡ b, b ≡ c, 即有a^(-1)·b, b^(-1)·c ∈ H.由H是子群, 有a^(-1)·c = (a^(-1)·b)·(b^(-1)·c) ∈ H, 即有a ≡ c.进而可以验证"≡"是一个同余关系:若a, b, c, d ∈ G满足a ≡ b, c ≡ d, 即有a^(-1)·b, c^(-1)·d ∈ H.由H是正规, 有c^(-1)·(a^(-1)·b)·c ∈ H.于是(ac)^(-1)·(bd) = (c^(-1)·a^(-1)·b·c)·(c^(-1)·d) ∈ H, 即有ac ≡ bd.上述由同余关系构造正规子群以及由正规子群构造同余关系的过程是互逆的.给定同余关系"≡", 可构造正规子群H = {h ∈ G | h ≡ e}.可知a ≡ b当且仅当a^(-1)·b ∈ H (即a^(-1)·b ≡ e).反之, 给定正规子群H, 可构造同余关系: a ≡ b当且仅当a^(-1)·b ∈ H.可知H = {h ∈ G | h ≡ e}.综上, G上的同余关系与正规子群可以建立一一对应.当一个有限时另一个也有限且二者个数相等.

其实说穿了特别简单就是除以4余数相同的数的集合[2]R = {2,6}

集合A={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}，R是A上的模5同余关系。商集 A/R 表示的是 A 中所有元素所对应的等价类，也就是模5同余的元素所组成的集合。A/R = { [1], [2], [3], [4] }其中 [1] 表示模5余1的元素{1,6,11,16}，[2] 表示模5余2的元素{2,7,12}，[3] 表示模5余3的元素{3,8,13}， [4] 表示模5余4的元素{4,9,14}。因此商集 A/R = { [1], [2], [3], [4] }.

我觉得是的，说白了其实就是等价交换。

同余理论和k次剩余理论都属于数论的分支，它们都涉及到了模运算的概念，但是它们的具体应用场景有所区别。同余理论主要研究了整数之间的模运算，即两个整数除以一个模数所得到的余数是否相等。在同余理论中，我们可以利用同余关系将整数划分为若干个同余类，这在数学中的应用非常广泛。例如，在密码学中，同余理论可以用来生成公钥和私钥，保证密码的安全性。而k次剩余理论则更加关注的是某个数在模意义下是否有平方根，即是否存在一个数b，使得b的k次方在模意义下等于给定的数a。k次剩余理论的应用非常广泛，例如在密码学中，RSA加密算法就是基于k次剩余理论的基础上发展出来的。因此，同余理论和k次剩余理论虽然都涉及到了模运算，但由于其研究的具体内容和应用场景不同，所以两者有所区别。

同余类定义：对给定的模m,整数的同余关系是一个等价关系，故整数集合可以根据对模m的同余关系，构造整数集合的一个划分。关于集合的划分与等价关系之间的关系详细阐述如下。定义：R是 A上的关系，a A ,b A, c A,若aRb且bRc,有aRc，则R是传递的。定义：自反的、对称的、传递的关系，称为等价关系。定义：设A是非空集合，P是A的非空子集构成的集合，并且满足以下条件：1.A的每个元素属于P中某个集合；定理1：设P是集合A的一个划分，A上关系R定义为:aRb当且仅当a,b属于P的同一块,则R是A上的等价关系。

(1)证明：A==R mod 3<=>A-R |: 3 这里用以等价地表示 3 |A-R从而R-A |: 3<=> R==Amod 3这就证明了互反性。同时易证A==A mod 3， 即自反性。另外再证：A==R , R==B mod 3 可以推出A==B mod 3前提即存在x,y使得 A=R+xm, R=B+ym, 于是A=B+xm+ym=B+(x+y)m, 于是A==B mod 3于是传递性成立。于是，A,R是同余关系即是等价关系。(2)不懂怎么回答(3)余0：{3}余1：{1,4}余2：{2,5}PS:表示我就大学水平，貌似没学过这个，以上答案根据度娘得出的，希望能够帮到你

因y=xmoda,则y=ka+x,（k为整数），x=y-ka，所以逆函数为y=x-ka,y=(-k)a+x,y=sa+x(s=-k),故逆函数可以写成y=xmoda（从同余关系的角度出发，y=xmoda就是X,模a同余，即x,y属于一个同余类，因此逆函数就是自身）

1.R是实数集，A集合里面的任何两个元素的乘积仍在R中，所以R是A上的全域关系。即：{ab,ac,ad,ae,af,ag,bc,bd,be,bf,bg,cd,ce,cf,cg,de,df,dg,ef,dg,fg}=R2.{(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(g,g)}=R3.R={2ka+1,2kb+1,2kc+1,2kd+1,2kf+1,2ke+1,2kg+1|k取任意数}

设 R 是非空集合 A 上的关系, 如果 R 是自反的、对称的、传递的，则称 R 为 A 上的等 价关系(equivalent relation). 设 n 为正整数，定义整数集合 Z 上的以 n 为模的同余关系 R = {< x, y > |n|(x − y)}, 证 明 R 是一个等价关系 设 R 是非空集合 A 上的等价关系，对任意 x ∈ A，称集合 [x]R = {y|y ∈ A, < x, y >∈ R}为 x 关于 R 的等价类(equivalence class)，或叫作由 x 生成的一个 R 等价类，其中 x 称为 [x]R 的生成元(代表元或典型元)(generator). 设 R 是非空集合 A 上的等价关系，由 R 确定的一切等价类的集合，称为集合 A 上关于R 的商集(quotient set)，记为A/R，即 A/R = {[x]R|x ∈ A}. 在等价关系中我们已经发现, 同一个等价类中的元素具有相同的属性，因而可将集合 中的元素分成不同的类别，对应于集合的划分。 设 R 是非空集合 A 上的等价关系，则 A 对 R 的商集 A/R 是 A 的一个划分，称为由 R 所导出的等价划分. 给定集合 A 的一个划分 π = {S1, S2, · · · , Sm}, 则由该划分确定的关系 R = (S1 × S1) ∪ (S2 × S2) ∪ · · · ∪ (Sm × Sm) 是 A 上的等价关系。我们称该关系 R 为由划分 π 所导出的等价关系。 设 R 是非空集合 A 上的关系, 如果 R 是自反的、反对称的、传递的，则称 R 为 A 上 的偏序关系(partial order relation), 记为“⩽”. 读作“小于等于”, 并将“< a, b >∈⩽”记为 a ⩽ b. 序偶 < A, ⩽> 称为偏序集 (partial order set).

数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即m|(a-b)，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。1 反身性 a≡a (mod m)2 对称性 若a≡b(mod m)，则b≡a (mod m)3 传递性 若a≡b (mod m)，b≡c (mod m)，则a≡c (mod m)4 同余式相加 若a≡b (mod m)，c≡d(mod m)，则a+-c≡b+-d (mod m)5 同余式相乘 若a≡b (mod m)，c≡d(mod m)，则ac≡bd (mod m)【证明】上述性质很容易证明,下面仅证明(3).∵a≡b(mod m)∴m|(a-b) 同理m|(b-c),∴m|[(a-b)+(b-c)]∴m|(a-c).故a≡c(mod m).4 线性运算如果a ≡ b (mod m)，c ≡ d (mod m),那么(1)a ± c ≡ b ± d (mod m)，(2)a * c ≡ b * d (mod m)【证明】(1)∵a≡b(mod m),∴m|(a-b) 同理 m|(c-d)∴m|[(a-b)±(c-d)] ∴m|[(a±c)-(b±d)]∴a ± c ≡ b ± d (mod m)(2)∵ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)又 m|(a-b) , m|(c-d) ∴m|(ac-bd)∴a * c ≡ b * d (mod m)5 除法若ac ≡ bc (mod m) c1=0 则 a≡ b (mod m/(c,m)) 其中(c,m)表示c,m的最大公约数特殊地 (c,m)=1 则a ≡ b (mod m)6 乘方如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)7 若a ≡ b (mod m)，n|m,则 a ≡ b (mod n)8 若a ≡ b (mod mi） i=1,2...n 则 a ≡ b (mod [m1,m2,...mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍数9 欧拉定理设a,m∈N,(a,m)=1,则a^(φ(m))≡1(mod m)(注:φ(m)指模m的简系个数， φ(m)=m-1, 如果m是素数；φ(m=q1^r1 * q2^r2 * ...*qi^ri)=m (1-1/q1)(1-1/q2)...(1-1/qi))推论: 费马小定理: 若p为质数，则a^p ≡ a (mod p) 即a^(p-1) ≡ 1 (mod p)（但是当p|a时不等价）10 中国剩余定理设整数m1,m2,m3,......,mn 两两互素，令m=m1m2m3m4m5...mn（mi的连乘）。则对于任意的J在（1,n)整数，下列联立的同余式有解：{xj≡1(mod mj){xj≡0(mod mi) i不等于j令x为从1到najxj的和，则x适合下列联立同余式x≡aj（mod mj）, j=1,2,3,.....,n另：求自然数a的个位数字，就是求a与哪一个一位数对于模10同余

等我今天上午考完了就给你说部分答案

同余两边不一定能平方。同余是指两个数除以同一个数的余数相等，它是一种等价关系，在数论中非常有用。但是，同余关系并不意味着平方后的结果也是相等的。例如，5和7模3同余，但52和72模3并不相等。当然也有一些特殊情况，比如当模数为2或3时同余两边可以平方，但这并不是绝对的，需要具体问题具体分析。

3x==4 mod 7解一乘以-2得-6x==-8 mod 7因为-6x==x mod 7依下面所讲到的同余式的传递性，即有：-6x==-8==x mod 7即x==-8==-1==6 mod 7解二：3x==4==-3 mod 7据下面讲到的消去律得x==-1 mod 7 ==6 mod 7下面是我最近的一个答题内容。供参考。1。同余号的性质。(0)在同余式两侧，与各个平行的加号平行的那个等号，可以换成同余号。如a=b, 则对于任何模m, a==b mod m.(1)等价性。反身性(自对称性)，互反性(互对称性)，传递性(滑移对称性)。即a==a; a==b则b==a; a==b,b==c，则a==c, 或写作a==b==c.等号，同余号，对应于相等关系，同余关系，均为等价关系。具有上面三类性质。 2。等价式的性质。即同余式类似于等式的性质。(1)同时乘以一组等价项之一，或除以一组非零的等价项之一，同余式成立。如a==b mod m , A ==B mod m则aA==bB mod m.其中非零项这样解释，若a不==0 mod m，则a为非零项。　　　　　　　　外一则，反一则：0==mk mod m, 零项就是形如mk这样的项。这个性质有几个重要的特例。(11)消去律。对于ax==ab mod m, 如a不==0 mod m, 则x==b mod m.(12)取负或取幂的情况。(121)取倒数的情况。例如3x ==1 mod 16，那么x称为模16之下，3的同余倒数，或称同余逆，或模逆，或乘率。洪伯阳先生推荐写成：x==1/3 mod 16. == 5 mod 16.(2)同时加减一组等价项之一，同余式仍成立。其中有一个情况要注意，0==mk mod 0，因此 mk这样的项，可以任意地在与==同级的整体项或任意部分项上，任意添加或删减。 2。模的性质。a==b mod m这个mod m，实际就是一个可以在同余式的同余号==两侧平行移动的一个代数和项，即是m的一个任意整数倍数，只要晓得它是存在的就行，不必计较它对于m的倍数的大小与正负，不必计较是加法还是减法，只要知道是代数和的形式就行。在此理解下，同余式是一种更自由的不定方程而已，并且与不定方程是完全可以等价的，只是我们的着眼的关键点在于a与b二者，相对于模m的滑移对称性。而模m这个东东，这个m的不定倍数，就是一个自由变化的绳圈，将a,b和诸如此类的珠子串起来了而已。 3。心法。简单的同余式，可以按我上面的举例，注意不要拘泥于正负号。复杂的同余式，将它作为等式或比例式，使用比例式的性质，分数的性质，利用洪伯阳方法来解。网上可搜 wsktuuyth 洪伯阳方法。举例：13x==5 mod 23x==5/13==10/26==10/3==33/3==11 mod 13 5x==13 mod 23x==13/5==65/25==65/2==42/2==21 mod 23或 x==13/5==2+3/5==2-20/5=2-4=-2==21 mod 23 也可以用不定方程来解。对于不定方程，我也提出了一种个人认为很是巧妙的方法，这种方法的过程，恰好表现的同余式与不定方程的等效性，并互为利用。将二者的形式统而为一，十分简明。以下是我在百度答题与博文中提到的不定方程解法，可搜索wsktuuytyh 不定方程或wsktuuytyh 同余式可以这样解得到。其中wsktuuytyh是我的百度账号，来自于我的现用名字 的五笔编码。wsk 何 tuu 冬 ytyh 州当然了解了其中的过程之后，可以用来尝试解不定方程13x=5+23y及5x=13+23y这样就是利用不定方程来解同余式。 举例：47x=89+111y两边mod 47，或者说将47的倍数集中，得47a==-5+17y (两式相减知x-a=2+2y)同理mod17得，-4a==-5+17b （两式相减知 3a=y-b)取b=1,顺次逆求：a=-3, y=-8, x=2-16-3=-17==94 mod 111

AAA 百度可以搜到大衍求一术、乘率等相关内容。乘率，同余逆，同余倒数，模逆，都是说的同一概念。例如，ax==1 mod m其中的　a与x互称为基于(关于、对于)模m的乘率，简称乘率。若已知a求x,　就说求a关于模m的乘率，或简单地说求a的乘率.这个同余式也相当于ax+my=1，于是my==1 mod a, 此时m与y也互为关于模a的乘率。其中为打字方便，用双等号==取代三线等号≡表示同余。BBB 注意事项：一、求乘率，就是求解同余式，该同余式有一侧为定值1；或者是求解含有常数1作为和项的二元一次三项不定方程。否则一般不称为求乘率。二、利用中国剩余定理同余式组，利用到乘率。但是，不利用乘率也可以直接解同余式组的，就像解多元方程组的矩阵方法，并不是一定要求逆矩阵一样。中国剩余定理解同余式，与解多元一次方程组或矩阵方程中用到的线性叠加方法原理是一样的，我们应当利用线性叠加原理而灵活变化。CCC 求乘率的例子CCC 例1(求乘率)： 13x==1 mod 23方法1-1：13x==1 mod 23两边乘2得26x==2 mod 233x==-21 mod 23x==-7==16 mod 23用洪伯阳同余记法，可用分数形式表示同余，再转换为整数形式，如下：x==1/13==2/26==-21/3==-7==16 mod 23方法1-2：13x==1 mod 23-10x==1 mod 23-10x==70x==-7==16用洪伯阳同余记法，即x==1/13==1/-10==70/-10==-7==16 mod 23方法2-1：使用不定方程。对于较复杂的情况，很适用。下面是经我改写了的一种解不定方程的方法，较常规教科书思路略有不同，计算较为方便。后文有略微复杂的几个例子，作了详细说明。13x==1 mod 2313x=1+23y 将13的倍数合并到13x这一项上并使用新的变量，得13z=1-3y 易见可取特值y=-4，代入即得 x=-7。于是x==-7==16 mod 23.DDD 注意对mod的一个重要认识：由13z==1-3y 也可直接解出 y=-4 mod 13，或写成 y=-4+13t 代入13x=1+23y 立即得 x= -7+ 23t == -7 mod 23 　事实上，我们应当认为 mod 13 与 +13t 地位相当本质相同。（mod 13） 本质上即是 +13 的任意倍数，我常常写成 +13**或13**+（放在左边时用13**+）， 表明不使用具体的符号来表示出这个任意的倍数。将mod13看作成+13**，于是立即知道它可以在同余式的代数和项或乘积的因数项上任意加减、滑移（包括等式左右两边移项）而不影响式子的性质。任意加减与滑移，只是这个任意倍数**发生了变值（包括改变正负号），而我们不关心因子**的值，故不需要去管它的形式，照样用**代替即是。使用 （mod 13）这种形式，就已经不再注意这个任意倍数了，其加减与滑移特性赋予了它极大的自由；使得它成为一个平台，相当于物理学中的“以太”一样了；而同时让我们将着眼点更好的放在其他变量的分析上。而使用 （+13 t ）这样的形式，则便于对变量进行称名引用。这种形式下，同余式即是不定方程，，方便于对模13的倍数进行定量跟踪分析，还可以在转换到（即重定位到）其它模与变量时不致混淆关注点（视点）。而转换模与变量，在解复杂的、难于计算的不定方程（包括同余式转化来的不定方程）是很好的方便的手段之一。方法2-213x==1 mod 2313x=1+23y13z=1+10y易见可取z=7, y=9，代入得x=16 mod 23这个代入计算的过程略微不便计算，可以这样简化：将两式比较，得x-z=y, 故 x=z+y=16 mod 23CCC例2(求乘率)：103x==1(mod211)解：206x==2 -5x==2*1-5x==2*-210x==84洪伯阳表示法：x==1/103==2/206==2*1/-5==2*-210/-5==84CCC例3(求乘率)开譆历上元积年377873x≡1(mod499067)的乘率解：用洪伯阳记号解，由于不便于重定位模对象，故此在不做为首选方法，见后文。先用我改写了的不定方程解法来解。这种不定方程解法的要点：要点1，其中使用双等号==取代等号=，以保证在使用同余关系时的扩展，从而使用了连等式，连等式各项使用同余关系相关联。一个连等式系列之中，取最前与最后二者，可改用等号连接形成等式，以此为依据进行变量的定量化分析。要点2，辗转相除法求最大公约数或求乘率、大衍求一术求乘率均可以用我这种思路改写成为不定方程。要点3，使用连等式，可保留中间计算过程，利于辅助记忆。如果笔算或口算或心算，记忆起来轻松一些，下面的过程主体是我一边打字一边心算完成的。要点4，其中变量便于称名引用，过程中的对象位置能够方便的对应，思路很为连续方便。要点5，在不定方程中使用了具体的变量名，因而转换到（即重定位到）其它模与变量时不致混淆关注点（视点）。而转换模与变量，在解复杂的、难于计算的不定方程（包括同余式转化来的不定方程）是很好的方便的手段之一。这一点前文也讲到过了。要点6，开始步骤与中间步骤都是对上一个不定方程式按较小的模进行并项得到下一个不定方程，并使用新的变量而不使用累次的代换关系，也不涉及复杂的分式，简洁明快。要点7，最后反推步骤，利用到了最后一个显然易解的不定方程，及所得到的所有相邻不定方程之间相比较得到的关系式，使计算涉及到的数值总体减小。在求值时，可以使用具体值参予计算，也可以继续使用变量，很自由方便。377873x==1+499067y 377873z==1+121194y 注：即将377873的倍数集中到原来的377873x这一项上并改用新变量。014291z==1+121194a014291b==1-021716a==1+6866a 注意，与前一式相比，14291的因子变量被改写。注意，此处使用了连等式，连等式对模14291构成同余等价关系。在连等式中以最前与最后二者以等号连接构成等式而进行定量分析。559b==1+6866c 559d==1+1276c==1+158c 注意，此处连等式对模559构成同余等价关系。-73d==1+158e-73f==1+12e取e=6, 逆求之可得解。过程可以如下：{将保留下来的各个算式，相邻两式两两比较，顺次得到：x-z=y3z=y-az-b=8a2b=a-cb-d=12c4d=c-e-d+f=2e 将e=6,f=-1代入，逆求。原先发文曾略去计算过程。此次补充，逆求如下：d=-13,c=-46,b=d+12c,a=2b+c=2d+25cz=b+8a=17d+212cy=3z+a=53d+661c,x=z+y=70d+873c=(-910+873*(-46))将上面的项复制到windows计算器(在windows操作系统开始菜单-运行：calc.exe-科学型)，算得x==-41068 mod 499067x==457999}用计算器检验，457999*377873 mod 499067 ==1检验正确.一般取正数为乘率，取负数也是不影响计算的，故二者均均可做为乘率。CCC例3续：以下用洪伯阳记号来解377873x==1(mod499067)用洪伯阳记号来解，可以有一个相当于下面的过程：-121194x==1-484776x==414291x==4（#1#）142910x==4021716x==41（#2#）（#1#）*-3+（#2#）*2得 （这在洪伯阳表示式，即分数形式的同余表示中，相当于对分数连等式使合比定理，以下类似。）559x==70（#3#）由（#2,3#）得 注：21716=559*39-85 -85x==41-70*39==-2689 （#4#）由 （#4,3#）得 注：559=85*6+4949x==70+-2689*6=-16064 （#4#）由 （#4,5#）得-36x==-18753故12x==6251==-492816x==-41068x==457999用洪伯阳表示，写作：x==1/377873 ==1/-121194==4/-484776==4/14291==41/21716==70/559==-2689/-85==-16064/49==-18753/-36=6251/12==-492816/12==-41068==457999注：用洪伯阳记号解，由于不便于重定位模与变量对象，中途利用合比定理略嫌复杂，故此在不做为首选方法，以不定方程法为最佳。CCC例4(求乘率)907X≡2107（mod731）的两个乘率注：后文将另行求解同余式907X≡2107（mod731），使用不定方程 907x+731y=2107来解。由前面讲过的乘率的概念，我们认为此题求乘率即是求解两个同余式： 907x==1 mod 731 及 731y==1 mod 907，这两个同余式是等价的，可互相转换的，仅是着眼点不同。同时也相当于不定方程 907x+731y=1.解：907x+731y=1176x+731z=1176a+27z=114a+27b=1取a=2，反推即可求出x,y。下面采用另一种方式以简捷计算。比较上述各式之两邻相式，分别得x+y-z=0x-a+4z=06a+z-b=0下面已知a=2,b=-1,故z=-13,x=54,y=-67也可以这样： 907x+731y=1176x+731z=1176a+27z=1-13a+27b=1，由a=2反推。比较上述各式之两邻两式分别得x+y-z=0, x-a+4z=0,7a+z-b=0, 由a=2,b=1得z=-13,x=54,y=67CCC例5（求乘率）3800k≡1（mod27）注：转化为解不定方程3800x+27y=120x+27z=1易见或取z=3,x=-4; 两式比较得140x+y-z=0，故y=-140x+z=563EEE 非求乘率型的同余式的求解EEE 例6 方法1103x==57(mod211)x==57/103==114/-5==325/-5==-65 mod 211方法2:不定方程法：103x=57+211y 将103x的倍数集中到103x上并使用新的变量:103z=57+5y易见可取z=-1, y=-32，这时可以代入计算出x,也可以用下面的思路简化计算。上述两式比较，易见 x-z=2y, 故x=z+2y=-65. 即原同余式解为 x==-65 mod 211.EEE 例7 解同余式 907X≡2107（mod731）相当于求解不定方程 907x+731y=2107解：176x+731z=-86176a+27z=-86-13a+27b=-5(-13c+b=-5)取b=-5,c=0逆求即可。当然也可以由-13a+27b=-5这一步直接看出可取b=-5，a=-10进行逆求。但引入-13c+b=-5会减轻心算之记忆负担。比较上述各式之两两相邻式子，得x+y-z=3x-a+4z=07a+z-b=-3(-a+c+2b=0)于是由c=0,b=-5,a=-10得 z=-7a+b-3=62,x=a-4z=-258,y=-x+z+3=258+62+3=323

当然是代表一类数。 只不过，你可以从每一类数里选一个代表元。 就用这个代表元来称呼整个这一类数。 这是近世代数最基本内容。楼主如果初学，可以看丁石孙写的《近世代数》。此书通俗易懂，最适合初学者。从代数角度看，同余关系是等价关系，所以整数集合可以按照等价关系分成互不相交等价类的并。 从每个等价类中随便选一个元素做代表元。这些代表元组成的集合上仍有加减乘运算。 对某些代表元，它还有逆元。

-1=-1*8+7-1除以8，商-1,余7.外一则：取余运算是模运算的特例，因为我们所谈及的余数，绝对值比模(除数)小；而模运算，考虑同余关系，无数的大小的限制。a除以m余r，建议记成 a mod m =r,或 mod(a,m)=r.a与r对模(除数)m同余,一般写作：a==r mod m 也可写作 a mod m==r. 其中==一般写成≡,称作同余号，读作同余。有时也记作=.有时略去 mod m.如-1==7 mod 8; -1 mod 8 =7

≡ 恒等于或同余 同余：数论中的重要概念.给定一个正整数m,如果二整数α、b)满足m│α-b)(α-b)被m整除),就称整数α、b)对模m同余,记作α呏b)(mod m).对模m同余是整数的一个等价关系.

整数关系中2/x+y等价关系，等价关系是从“等于”、“相似”、“平行”、“同余”等等关系中提炼它们的共同点得到的。这也是数学中比较精髓的一点—抽象。

3-2=1多一本所以有一个抽屉必有1+1=2

59x+153y=107此不定方程与一次同余式59x==107 mod 153 或 153y==107 mod 59等价。中国剩余定理(Chinese Remainder Theorem)，即孙子定理，用于解同余式组(即同一未知元的多个一次同余式)。而本题只涉及一个同余式，故不必用到中国剩余定理。下面用我设计的一种新方法解此不定方程，十分方便。59x+153y=107 （#1#）将59的倍数集中到59x这一项上面，并改用新变量，（注：相当于原式mod59）, 如下：59a-24y=48==-9 （注：48==-9 mod 59; 着眼于 59的倍数已集中到59a之上，不必写出 mod 59; 将全式作为等式处理时，使用最后一个==后面的项，即59a-24y=-9）同理，再将24的倍数集中到24y，改用新变量。此时发现使用59a-24y=48 更好。故重新申明：59a-24y=48 （#2#）即有11a-24b=0 （#3#）于是取b=11, 逆推，a=24, y=57（注：在用心算算不出来时，结果笔算，用到一个小技巧是比较前后相邻的式子，得到未知数之间的关系）比较 （#1,2#）两式，得到x-a+3y=1，故x=a-3y+1=24-171+1 =-146验算：开始菜单-运行-calc.exe-科学型-输入或复制下面一行到计算器输入框59*(-146)+ 153*57=得到结果为107，即检验无误。

AES是分组密钥，算法输入128位数据，密钥长度也是128位。用Nr表示对一个数据分组加密的轮数（加密轮数与密钥长度的关系如表1所列）。每一轮都需要一个与输入分组具有相同长度的扩展密钥Expandedkey(i)的参与。由于外部输入的加密密钥K长度有限,所以在算法中要用一个密钥扩展程序(Keyexpansion)把外部密钥K扩展成更长的比特串,以生成各轮的加密和解密密钥。x0dx0a1.1圈变化x0dx0aAES每一个圈变换由以下三个层组成:x0dx0a非线性层——进行Subbyte变换；x0dx0a线行混合层——进行ShiftRow和MixColumn运算；x0dx0a密钥加层——进行AddRoundKey运算。x0dx0a① Subbyte变换是作用在状态中每个字节上的一种非线性字节转换,可以通过计算出来的S盒进行映射。x0dx0ax0dx0a② ShiftRow是一个字节换位。它将状态中的行按照不同的偏移量进行循环移位，而这个偏移量也是根据Nb的不同而选择的[3]。x0dx0ax0dx0a③ 在MixColumn变换中,把状态中的每一列看作GF(28)上的多项式a(x)与固定多项式c(x)相乘的结果。 b(x)=c(x)*a(x)的系数这样计算:x0dx0a*运算不是普通的乘法运算,而是特殊的运算，即 b(x)=c(x)·a(x)(mod x4+1) 对于这个运算 b0=02。a0+03。a1+a2+a3 令xtime(a0)=02。a0x0dx0a其中，符号“。”表示模一个八次不可约多项式的同余乘法[3]。x0dx0ax0dx0a对于逆变化,其矩阵C要改变成相应的D,即b(x)=d(x)＊a(x)。x0dx0a④ 密钥加层运算(addround)是将圈密钥状态中的对应字节按位“异或”。x0dx0ax0dx0a⑤ 根据线性变化的性质[1],解密运算是加密变化的逆变化。

十一世纪，阿拉伯的阿尔·卡尔希第一次解出了二次方程的根。十一世纪，阿拉伯的卡牙姆完成了一部系统研究三次方程的书《代数学》。十一世纪，埃及的阿尔·海赛姆解决了“海赛姆”问题，即要在圆的平面上两点作两条线相交于圆周上一点，并与在该点的法线成等角。十一世纪中叶，中国宋朝的贾宪在《黄帝九章算术细草》中，创造了开任意高次幂的“增乘开方法”，并列出了二项式定理系数表，这是现代“组合数学”的早期发现。后人所称的“杨辉三角”即指此法。 十三世纪，印度的拜斯迦罗著《立刺瓦提》一书，这是东方算术和计算方面的重要著作。1202年，意大利的裴波那契发表《计算之书》，把印度—阿拉伯记数法介绍到西方。1220年，意大利的裴波那契发表《几何学实习》一书，介绍了许多阿拉伯资料中没有的示例。1247年，中国宋朝的秦九韶著《数书九章》共十八卷，推广了“增乘开方法”。书中提出的联立一次同余式的解法，比西方早五百七十余年。1248年，中国宋朝的李治著《测圆海镜》十二卷，这是第一部系统论述“天元术”的著作。1261年，中国宋朝的杨辉著《详解九章算法》，用“垛积术”求出几类高阶等差级数之和。1274年，中国宋朝的杨辉发表《乘除通变本末》，叙述“九归”捷法，介绍了筹算乘除的各种运算法。1280年，元朝《授时历》用招差法编制日月的方位表(中国 王恂、郭守敬等)。十四世纪中叶前，中国开始应用珠算盘。 1464年，德国的约·米勒在《论各种三角形》(1533年出版)中，系统地总结了三角学。1494年，意大利的帕奇欧里发表《算术集成》，反映了当时所知道的关于算术、代数和三角学的知识。 1545年，意大利的卡尔达诺、费尔诺在《大法》中发表了求三次方程一般代数解的公式。1550～1572年，意大利的邦别利出版《代数学》，其中引入了虚数，完全解决了三次方程的代数解问题。1591年左右，德国的韦达在《美妙的代数》中首次使用字母表示数字系数的一般符号，推进了代数问题的一般讨论。1596～1613年，德国的奥脱、皮提斯库斯完成了六个三角函数的每间隔10秒的十五位小数表。 1614年，英国的耐普尔制定了对数。1615年，德国的开卜勒发表《酒桶的立体几何学》，研究了圆锥曲线旋转体的体积。1635年，意大利的卡瓦列利发表《不可分连续量的几何学》，书中避免无穷小量，用不可分量制定了一种简单形式的微积分。1637年，法国的笛卡尔出版《几何学》，提出了解析几何，把变量引进数学，成为“数学中的转折点”。1638年，法国的费尔玛开始用微分法求极大、极小问题。1638年，意大利的伽里略发表《关于两种新科学的数学证明的论说》，研究距离、速度和加速度之间的关系，提出了无穷集合的概念，这本书被认为是伽里略重要的科学成就。1639年，法国的迪沙格发表了《企图研究圆锥和平面的相交所发生的事的草案》，这是近世射影几何学的早期工作。1641年，法国的帕斯卡发现关于圆锥内接六边形的“帕斯卡定理”。1649年，法国的帕斯卡制成帕斯卡计算器，它是近代计算机的先驱。1654年，法国的帕斯卡、费尔玛研究了概率论的基础。1655年，英国的瓦里斯出版《无穷算术》一书，第一次把代数学扩展到分析学。1657年，荷兰的惠更斯发表了关于概率论的早期论文《论机会游戏的演算》。1658年，法国的帕斯卡出版《摆线通论》，对“摆线”进行了充分的研究。1665～1676年，牛顿(1665～1666年)先于莱布尼茨(1673～1676年)制定了微积分，莱布尼茨(1684～1686年)早于牛顿(1704～1736年)发表了微积分。1669年，英国的牛顿、雷夫逊发明解非线性方程的牛顿—雷夫逊方法。1670年，法国的费尔玛提出“费尔玛大定理”。1673年，荷兰的惠更斯发表了《摆动的时钟》，其中研究了平面曲线的渐屈线和渐伸线。1684年，德国的莱布尼茨发表了关于微分法的著作《关于极大极小以及切线的新方法》。1686年，德国的莱布尼茨发表了关于积分法的著作。1691年，瑞士的约·贝努利出版《微分学初步》，这促进了微积分在物理学和力学上的应用及研究。1696年，法国的洛比达发明求不定式极限的“洛比达法则”。1697年，瑞士的约·贝努利解决了一些变分问题，发现最速下降线和测地线。 1704年，英国的牛顿发表《三次曲线枚举》《利用无穷级数求曲线的面积和长度》《流数法》。1711年，英国的牛顿发表《使用级数、流数等等的分析》。1713年，瑞士的雅·贝努利出版了概率论的第一本著作《猜度术》。1715年，英国的布·泰勒发表《增量方法及其他》。1731年，法国的克雷洛出版《关于双重曲率的曲线的研究》，这是研究空间解析几何和微分几何的最初尝试。1733年，英国的德·勒哈佛尔发现正态概率曲线。1734年，英国的贝克莱发表《分析学者》，副标题是《致不信神的数学家》，攻击牛顿的《流数法》，引起所谓第二次数学危机。1736年，英国的牛顿发表《流数法和无穷级数》。1736年，瑞士的欧拉出版《力学、或解析地叙述运动的理论》，这是用分析方法发展牛顿的质点动力学的第一本著作。1742年，英国的麦克劳林引进了函数的幂级数展开法。1744年，瑞士的欧拉导出了变分法的欧拉方程，发现某些极小曲面。1747年，法国的达朗贝尔等由弦振动的研究而开创偏微分方程论。1748年，瑞士的欧拉出版了系统研究分析数学的《无穷分析概要》，这是欧拉的主要著作之一。1755～1774年，瑞士的欧拉出版了《微分学》和《积分学》三卷。书中包括微分方程论和一些特殊的函数。1760～1761年，法国的拉格朗日系统地研究了变分法及其在力学上的应用。1767年，法国的拉格朗日发现分离代数方程实根的方法和求其近似值的方法。1770～1771年，法国的拉格朗日把置换群用于代数方程式求解，这是群论的开始。1772年，法国的拉格朗日给出三体问题最初的特解。1788年，法国的拉格朗日出版了《解析力学》，把新发展的解析法应用于质点、刚体力学。1794年，法国的勒让德出版流传很广的初等几何学课本《几何学概要》。1794年，德国的高斯从研究测量误差，提出最小二乘法，于1809年发表。1797年，法国的拉格朗日发表《解析函数论》，不用极限的概念而用代数方法建立微分学。1799年，法国的蒙日创立画法几何学，在工程技术中应用颇多。1799年，德国的高斯证明了代数学的一个基本定理：实系数代数方程必有根。

a和b模p同余是指(a-b)是p的倍数

正整数集S,x,y∈S,定义关系R： ＜x,y＞∈R 当且仅当 x≡y （mod）n （x≡y （mod）n 表示x,y除以n的余数相同） 称此关系为模n的同余关系. 可以验证此关系是一个等价关系

就是除以三的余数相同比如5和2除以3都余2300和3除以三都余0这些都叫同余

不难证明推广的结果：同余关系是等价关系。证：a==b mod m<=>a-b |: m 这里用以等价地表示 m | a-b从而b-a |: m<=> b==a mod m这就证明了互反性。同时易证a==a mod m， 即自反性。另外再证： a==b , b==c mod m 可以推出 a==c mod m前提即存在 r,s使得 a=b+sm, b=c+rm, 于是a=c+rm+sm=c+(r+s)m, 于是a==c mod m于是传递性成立。于是，同余关系是等价关系。

表示同余关系的数学表达式，与等式相似。将等式中的等号“=”换成同余符号“≡”，必要时在式尾缀以(mod m) 注明模m（即除数），就是同余式。含有未知数的同余式叫做同余方程，通常要求整数解。同余式的定义如果两个正整数 a和 b之差能被 n整除，那么我们就说 a和 b对模n同余，记作：a ≡b (mod n)同余式的运算同余式运算类似于等式的运算，在等号两边可进行加减乘除的算术运算。如 a≡b (mod n) ，则有：a + c ≡b + c (mod n)a - c ≡b - c (mod n)a ·c ≡b ·c (mod n)但在应用除法运算时应特别注意，仅在除数与模互质时，才能去除同余式的两边，如：a /c ≡b / c (mod n) ，必须c 与 n要互质，就c 与 n须没有公因数。

一个关系满足自反、对称、传递叫做等价关系.模M同余关系作为关系的一种,也满足以上三条,当然是同余关系了.比如10与10模3同余,这是自反；10与4模3同余,则4与10模3同余,即模3同余有等价性.10与4模3同余,4与7模3同余,则10与7模3同余,这是传递性.

就是除以三的余数相同 比如5和2除以3都余2 300和3除以三都余0 这些都叫同余

模7同余的例子有哪些性质（）。 A.如果a和b有模7同余关系，那么b和a有模7同余关系。B.a和b是模7同余关系，那么a=b。C.如果a和b有模7同余关系，b和c有模7同余关系，那么a和c有模7同余关系。D.a和a是模7同余关系。正确答案：ACD

搜一下：1.非空集合上的同余关系一定是等价关系吗?反之如何?(举例加以说明)

{2,4} {1,3,5}

25≡13(mod 6)就是说25和13除以6的余数相同

mod n?总得有模呀

搜一下：离散数学高手请入，关于子群，陪集和同余关系