同余的基本概念和性质课件

1、3.1同余的概念和性质，1。学会交流PPT，第三章是同余，这是数论中的一个基本概念。本章不仅介绍了同余的基本知识，还介绍了同余的一些应用。2，学会交流PPT，同余的基本性质第一节，定义1。给定一个正整数M，如果整数A和B之间的差可以被M整除，那么A和B被认为与模M一致，或者A和B被记录为B(模M)。这时，B也被认为与模M全等。如果整数A和B之间的差不能被M整除，那么A和B被认为与模M全等。学习交流PPT，同余的基本性质在第一节中，定理1的以下三个陈述是等价的：(A)B(mod M)；()有一个整数q，所以a=bqm()有整数q1和q2，所以a=q1mrb=q2mr0 r m。这个证明留待练习。

2、4，学会交流PPT，第一节是同余的基本性质，定理2同余具有以下性质： (自反性)a a(mod m)；()(对称)a b(模m) b a(模m)；()(及物性)a b，b c (mod m) a c (mod m)。证据是为练习而保留的。5，学习同余的基本性质，定理3让A，B，C和D是整数，a b (mod m)，c d (mod m)，(1)然后(A C B D(mod M)；()AC BD(mod m)20 .证明()从公式(1)和定义(1)中，我们可以知道ma b、mc d、6的第1节中同余的基本性质，学会交流PPT，所以m(a c) (b d)是结论()；根据公式(1)和定理1，存在整

3、数q1和q2，使得a=b q1m，c=d q2m，所以AC=BD(q2m q1d q2b)m，然后利用定理1，推导出结论()。证书已完成。7，学习交流PPT，第一部分是同余的基本性质，定理4假设ai，bi(0 i n)，X，Y是整数，而x y (mod m)，艾比(mod m)，0 i n，那么(2)，并且这个证明是留给练习的。8，学会交流PPT，第一节是同余的基本性质，定理5的下列结论成立：(a)b(mod m)，d m，d0 a b(mod d)；(a)b(mod m)，k 0，kN AK bk(mod MK)；(a)b(mod mi)，1 i k a b (mod m1，m2，MK)；(

4、a)b(mod m)(a，m)=(b，m)；()不列颠哥伦比亚省(MODM)，(中部，中部)=1甲乙(MODM)。9。学会交流第一节同余的基本性质PPT，证明结论() ()，并把它作为一个练习。()从ac bc (mod m)得到mc(a b)，然后从(c，m)=1和第一章第三节的定理4得到ma b，即a b (mod m)。证书已完成。10，在PPT的第一部分学习同余的基本性质。例1设N=是整数N的十进制表示，即N=an10n an 110n 1 a110 a0，然后()3 | n () 9 | n () 11 | n () 13 | n、110结论()，()用同样的方法证明。12，学会交流

5、PPT，同余的基本性质在第一节，要证明结论()，只需用公式(2)和100 1，101 3，102 4，103 1，(mod 1 3)和，13，学会交流PPT，同余的基本性质在第一节，注33，14，学会交流PPT，第一节是同余的基本性质，例2，找到被7整除的条件，并说明是否1123333，解是100 1，101 3，102 2，103 1 (mod 7)，所以，也就是15，学习第一节同余的基本性质、因为789 456 123 1=455 7455，所以71123456789。16，学习交流PPT，同余的基本性质第一节，依次计算同余公式22 4，24 16，28 256，216 154，232 1

6、 (mod 641)。示例3显示了它是否可以被641整除。所以0 (mod 641)，即641。17，学会交流PPT，第一节是同余的基本性质、注：一般来说，计算ab (mod m)往往是一项复杂的工作。然而，如果使用欧拉定理或费马定理(见第4节)，它可以适当简化。18，学会交流PPT，第一节是同余的基本性质，解(2573346)26(7334)26=7(72)16 426 7(1)16 426=(7 4)26 326=3(35)5 3例4求(2573346) 26的余数除以50。，19，学会交流PPT，第一节是同余的基本性质，我们有71 3，72 1，74 1 (mod 10)。因此，如果77

7、 r (mod 4)，那么、在例5中计算的单个数字。现在77 (1)7 1 3 (mod 4)，20，学习交流PPT，同余的基本性质在第一节、所以它是由公式(3)得到的，也就是说，n的一位数是3。注：一般来说，如果得到模m的同余，可分为以下几个步骤：(1)求整数k使AK 1(模m)；()求正整数r，r k，使BC r(mod k)；(a)r(mod m ).21，学会交流PPT，第一节，同余的基本性质，由42N 13 N2=442N 93n=416N 93n 43n 93n=133n 0(mod 13)证明，例6，如果n是正整数，那么1342n 1 3 n 2。22，学会交流PPT，第一节，同

8、余的基本性质、证明了如果a=2k 1，当n=1时，有a2=(2k 1)2=4k(k 1) 1 1 (mod 23)，即公式(4)成立。例7证明如果2 a和n是正整数，那么1 (mod 2n 2)。(4)，23，学习交流PPT，同余的基本性质在第一节，让方程(4)适用于n=k，然后有1 (mod 2k 2)=1 q2k 2，其中qZ，所以，=(1 q2k 2)2=1 q 2k 31(mod 2k 3)这表明方程(4)适用于n=k 1。通过归纳，公式(4)适用于所有正整数n。24，学会交流PPT，第一节是同余的基本性质，这证明了a2 1 (mod p) pa2 1=(a 1)(a 1)，所以它必须

9、是pa 1或pa 1，例8如果P是素数，A是整数，a 1或a 1可以从a2 1 (mod p)推出，即a 1 (mod p)或a 1 (mod p)。25，学会交流PPT，第一节是同余、的基本性质，解是792n 8n、9n和11n因为792=8911。我们有8n 8 z=6、和9n 91 3 x y 4 5 z=19 x y 9x y 1，(5)，例9，让n的十进制表示为，如果792n，找到x，y，z，26，学会交流PPT，第一节是同余的基本性质、11n11z54y x 3 1=3y x 113y x. (6)，因为0 x，y 9，x y 1=9或18，3 y x=0或，27，学习第一节同余的基本性质，从而得到四个方程，其中A取9或18，B取0或11。在x=0，y=9的条件下，求解四个方程，得到x=8，y=0，z=6。