初等数论§3同余

初等数论同余方程组初等数论是数学中的一个分支，主要研究自然数的性质和整数的性质。

同余方程组是初等数论中的一个重要概念，它涉及到数与数之间的整除关系。

本文将介绍同余方程组的定义、性质以及解法，并通过例题来加深理解。

一、同余方程组的定义同余方程组是由若干个同余方程组成的一组方程。

同余方程的定义如下：对于整数a、b和正整数m，如果m能整除(a-b)，即(a-b)能被m整除，则称a与b对于模m同余，记为a≡b(mod m)。

这里的≡表示同余关系。

二、同余方程组的性质1. 同余关系具有自反性、对称性和传递性。

即对于任意的整数a、b和正整数m，有a≡a(mod m)，a≡b(mod m)等价于b≡a(mod m)，若a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)。

2. 同余关系具有加法和乘法的性质。

即对于任意的整数a、b和正整数m，若a≡b(mod m)，则a+c≡b+c(mod m)，ac≡bc(mod m)。

三、同余方程组的解法1. 线性同余方程组的解法：线性同余方程组是形如ax≡b(mod m)的方程组，其中a、b为整数，m为正整数。

若a与m互质，则存在唯一的解x0，且x≡x0(mod m)。

若a与m不互质，且b可被a整除，则方程组有无穷多个解，否则无解。

2. 中国剩余定理：中国剩余定理适用于一组两两互质的模数的同余方程组。

设m1、m2、...、mn为两两互质的正整数，a1、a2、...、an为整数，则同余方程组：x≡a1(mod m1)x≡a2(mod m2)...x≡an(mod mn)有唯一的解x，且0≤x<m1m2...mn。

四、例题解析1. 解线性同余方程组：求解方程组2x≡3(mod 5)和3x≡4(mod 7)。

首先，对于第一个方程，由于2与5互质，所以存在唯一解x0。

根据扩展欧几里得算法，我们可以求出x0=4。

然后，将x0代入第二个方程，得到3*4≡4(mod 7)，即12≡4(mod 7)。

数论算法讲义3章（同余方程）第 3 章同余方程（一）内容：● 同余方程概念● 解同余方程● 解同余方程组（二）重点● 解同余方程（三）应用● 密码学，公钥密码学3.1 基本概念及一次同余方程(一) 同余方程（1）同余方程【定义3.1.1】（定义1）设m 是一个正整数，f(x)为n 次多项式()0111a x a x a x a x f n n n n ++++=--Λ其中i a 是正整数（n a ≠0（mod m ）），则f (x)≡0（mod m ）（1）叫做模m 的（n 次）同余式（或模m 的（n 次）同余方程），n 叫做f(x)的次数，记为deg f 。

（2）同余方程的解若整数a 使得f (a)≡0（mod m ）成立，则a 叫做该同余方程的解。

（3）同余方程的解数若a 是同余方程（1）的解，则满足x ≡a （mod m ）的所有整数都是方程（1）的解。

即剩余类a C ＝{x ｜x ∈Z ，x ≡a （mod m ）}中的每个剩余都是解。

故把这些解都看做是相同的，并说剩余类a C 是同余方程(1)的一个解，这个解通常记为x ≡a （mod m ）当21,c c 均为同余方程(1)的解，且对模m 不同余时，就称它们是同余方程(2)的不同的解，所有对模m 的两两不同余的解的个数，称为是同余方程（1）的解数，记作()m f T ;。

显然()m f T ;≤m（4）同余方程的解法一：穷举法任意选定模m 的一组完全剩余系，并以其中的每个剩余代入方程（1），在这完全剩余系中解的个数就是解数()m f T ;。

【例1】（例1）可以验证，x ≡2，4（mod 7）是同余方程15++x x ≡0（mod 7）的不同的解，故该方程的解数为2。

50＋0＋1＝1≡3 mod 751＋1＋1＝3≡3 mod 752＋2＋1＝35≡0 mod 753＋3＋1＝247≡2 mod 754＋4＋1＝1029≡0 mod 755＋5＋1＝3131≡2 mod 756＋6＋1＝7783≡6 mod 7【例2】求同余方程122742-+x x ≡0（mod 15）的解。

第三讲：初等数论3——同余的性质和应用三、巩固练习1. 今天是星期三，到第1000天是星期几？解：从今天到第1000天相隔999天，1000-1≡5(mod 7)，3+5-7=1，是星期一.2. 若1059，1417，2313分别被自然数x除时，所得余数都是y，则x-y= ．解：∵1059≡y(mod x) ，1417≡y(mod x) ， 2313≡y(mod x)，∴1417-1059=358≡0(mod x)，2313-1417=896≡0(mod x)， 2313-1059=1254≡0(mod x)又（358，896，1254）的最大公约数为2，则x=2， y=1，x-y=1．3. 若正整数a和1995对于模6同余，则a的值可以是（）A. 25B. 26C. 27D. 28解：1995除以6的余数是3，a≡1995 (mod 6)，a除以6的余数也是3，只有a=27，选C.4. 一个两位数被7除余1，它的反序数被7除也余1，那么这样的两位数共有（）A. 2个B. 3个C. 4个D. 5个解：列出满足条件的所有两位数：15，22，29，36，43，50，57，64，71，78，85，92，99 两位数据反序数也满足条件的有：22，29，92，99，选C.5. 设n为自然数，则32n+8被8除的余数是_________.解：由32n+8=9n+8，知32n+8≡1n+0(mod 8)≡1(mod 8) ，故32n+8被8除余1.6. 黑板上写着13个数：1908，1918，1928，1938，1948，1958，1968，1978，1988，1998，2008，2018，2028．小明第一次擦掉其中的一个数，第二次擦掉剩下数中的两个数，第三次擦掉剩下数中的三个数，第四次擦掉剩下数中的四个数，他想使得每次擦掉数后剩下的所有数之和为13的倍数，小明的意图能否达到？如果可以，给出一种可行的方法，不能请说明理由．答案：可以：依次擦掉（2028）；（1958，1968）；（1908，1938，1978）；（1918，1928，1998，2008）。

初等数论（三）--同余基本性质：（1） 反身性：(mod )a a m ≡（2） 对称性：若(mod ),a b m ≡则(mod ),b a m ≡（3） 传递性：如果(mod ),a b m ≡(mod ),b c m ≡那么(mod ),a c m ≡以上三个性质说明∙“同余是一个等价关系，Z 中元素可以按照模m 分成m 个类，粗略地讲，用一类中的元素可以认为是相同的”（4） 如果(mod ),a b m ≡(mod ),c d m ≡那么(mod ),(mod ),a c b d m ac bd m ±≡±≡（5） 如果(mod ),a b m ≡那么(mod ),n n a b m ≡（6） 如果(mod )ac ab m ≡，不一定有(mod )c b m ≡（整数之间的乘法消去律不一定成立），（7） 若(mod ),ac bc m ≡则mod (,)m a b c m ⎛⎫≡ ⎪⎝⎭。

因此，(,)1c m =时，才会有(mod )a b m ≡。

例1.若质数5,p ≥并且21p +也是质数，证明：41p +是合数。

例2.对于任何n 个整数的集合，存在一个子集，该子集的元素之和被n 整除。

例3.证明表达式23,95x y x y ++按照相同的,x y 被17整除。

例4.设3p ≥为奇质数且111...21a p b +++=-， 证明：p a 。

作业：证明：3131421x x ++++被7整除。

例5.30对夫妻围着圆桌而坐。

证明：至少有两名妻子到各自丈夫的距离相等。

例6.设(,)1a m =，证明方程(mod )ax b m ≡在{0,1,2,3,...,1}m -中有唯一解。

例7.设01,,,,1,2,3,...n n a b x N x ax b n -∈=+=。

证明：数列12,,....,,...n x x x 不可能都是质数。

例8.证明方程2222x y z xyz ++=只有一个整数解0x y z ===。

同余关系的概念与定理同余关系是离散数学中一个重要的概念，它在数论、代数和密码学等领域有着广泛的应用。

本文将介绍同余关系的概念和相关定理。

一、同余关系的概念同余关系是数论中的一个基本概念，它描述了两个数之间的整除关系。

具体来说，给定两个整数a和b，如果它们除以一个正整数m所得的余数相同，即a和b对m同余，记作a≡b(mod m)，则称a和b关于模m同余。

二、同余关系的性质同余关系具有以下三个性质：1.自反性：对于任意整数a，a≡a(mod m)恒成立。

即任意整数与自身关于模m同余。

2.对称性：对于任意整数a和b，若a≡b(mod m)，则b≡a(mod m)。

即若a与b关于模m同余，则b与a关于模m同余。

3.传递性：对于任意整数a、b和c，若a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)。

即若a与b关于模m同余，且b与c关于模m同余，则a与c关于模m同余。

三、同余关系的定理1. 除法定理：对于任意整数a和正整数m，存在唯一的整数q和r，使得a=qm+r，其中0≤r<m。

即任意整数a可以表示为以m为模的除法形式。

2. 模运算性质：- 同余类的性质：对于任意整数a和正整数m，a关于模m的同余类可以表示为[a]m={b∈Z | b≡a(mod m)}，其中Z表示整数集合。

同余类[a]m是所有与a关于模m同余的整数构成的集合。

- 同余的运算性质：对于任意整数a、b和正整数m，若a≡a' (mod m)且b≡b' (mod m)，则有a+b≡a'+b' (mod m)，a-b≡a'-b' (mod m)，ab≡a'b' (mod m)。

3. 唯一性定理：对于给定的整数a、b和正整数m，存在整数x，使得a≡b (mod m)的充分必要条件是a和b对m的余数相同。

即a和b关于模m同余的充分必要条件是它们对m的余数相同。

4. 同余定理：对于任意整数a、b和正整数m，若a≡b (mod m)，则a^n≡b^n (mod m)，其中n是正整数。

同余的运算法则全文共四篇示例，供读者参考第一篇示例：同余的概念最早出现在数论领域，是一种描述整数间的模运算关系的数学概念。

同余的运算法则涉及到模运算的一系列性质和规律，对于解决一些数论问题和密码学中的加密算法起着至关重要的作用。

本文将介绍同余的概念及其运算法则，并讨论其在数学和应用方面的重要性。

1. 同余的定义在数论中，我们通常使用符号“≡”表示同余关系。

如果两个整数a和b除以一个正整数m的余数相等，即a除以m和b除以m的余数相等，我们就说a与b关于模m同余，记为a≡b(mod m)。

简单来说，同余就是指两个数除以同一个数的余数相等。

12和22关于模5同余，因为12除以5的余数为2，22除以5的余数也为2，即12≡22(mod 5)。

2. 同余的运算法则在模运算中，同余有着一系列的运算法则。

我们可以根据这些法则来简化模运算的计算，并处理一些复杂的数论问题。

（1）同余的传递性如果a≡b(mod m)且b≡c(mod m)，那么可以推出a≡c(mod m)。

这就是同余关系的传递性，即如果两个数与同一个模同余，那么它们之间也是同余的。

举例来说，如果5≡15(mod 10)且15≡25(mod 10)，那么可以推出5≡25(mod 10)。

（2）同余的对称性和反对称性（3）同余的加法和乘法性质对于同余关系来说，加法和乘法都具有良好的性质。

（4）同余的幂运算性质如果a≡b(mod m)，那么对于任意正整数n，有a^n≡b^n(mod m)。

即同余数的幂运算后依然同余。

（5）同余的逆元如果a在模m下存在逆元，即存在整数b使得ab≡1(mod m)，那么我们称b是a的逆元。

对于素数模m来说，任意整数a在模m下都有逆元。

同余的概念在数论和密码学领域有着广泛的应用。

（1）同余在数论中的应用在数论中，同余可以用来证明一些整数性质和解决一些数论问题。

在证明费马小定理和欧拉定理等定理时就会用到同余的性质。

在密码学中，同余的概念有着重要的应用。