Chinaunix首页 | 论坛 | 认证专区 | 博客 登录 | 注册

技术之美

暂无签名

  • 博客访问: 1092424
  • 博文数量: 135
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 4864
  • 用 户 组: 普通用户
  • 注册时间: 2013-01-23 18:56
个人简介

将晦涩难懂的技术讲的通俗易懂

文章分类

全部博文(135)

文章存档

2017年(9)

2016年(26)

2015年(18)

2014年(60)

2013年(22)

微信关注

IT168企业级官微



微信号:IT168qiye



系统架构师大会



微信号:SACC2013

订阅
热词专题
同余定理 2014-04-15 23:53:13

分类: IT职场

一、 同余

      对于整数除以某个正整数的问题,如果只关心余数的情况,就产生同余的概念。

定义1 用给定的正整数m分别除整数ab,如果所得的余数相等,则称ab对模m同余,记作ab(mod m),如 56mod 8)。

定理1  整数a,b对模m同余的充要条件是 a-b能被m整除(即m|a-b)。

证  设a=mq1+r1, 0<=r1

   b=mq2+r2, 0<=r2

ab(mod m),按定义1r1=r2,于是a-b=m(q1+q2),即有m|a-b.

反之,若m|a-b,m|m(q1-a2)+r1-r2,则m|r1-r2,但|r1-r2|,故r1=r2,ab(mod m)

推论1   ab(mod m)的充要条件是a=mt+bt为整数)。abm同余,则ab相差整数个m

定理2  同余关系具有反身性、对称性与传递性,即

1aa (mod m);

2)若ab (mod m), ba (mod m);

3)若ab (mod m), bc (mod m),则ac (mod m).

定理3 若ab(mod m), cd (mod m),

1a+cb+d (mod m);

2a-cb-d (mod m);

3acbd (mod m).

多于两个的同模同余式也能够进行加减乘运算。对于乘法还有下面的推论:

推论2  若ab(mod m),n为自然数,则anbn (mod m)

定理4 若cacb(mod m), (c,m)=d, a,b为整数,则ab(mod m/d).

推论ca=cb(mod m), (c,m)=1,a,b为整数,则ab(mod m).

定理5 若ab (mod m),ab (mod n),ab(mod [m,n]). (注:[m,n]表示m,n的最小公倍数)

推论ab(mod mi), i=1,2,,n,则ab (mod [m1,m2,..,mn]).

 

1 证明:正整数a9的倍数必须且只须a的各位数码之和是9的倍数。

证  设a=an.10n+an-1.10n-1++a0

101 (mod 9)10k1(mod 9),k=0,1,2,,n          (同余的传递性,推论21=10(mod9),10=100(mod9)---

所以 ak.10kak (mod 9), k=0,1,2,,n

所以aa0+a1+...+an (mod 9)

因此 9|a的充要条件是 9| a0+a1+...+an  。

2 设a=anan-1a1a0,11|a的充要条件。

解由10-1 (mod 11),10k(-1)k (mod 11), k=0,1,2,,n

   而 aa0-a1+a2-+(-1)nan (mod 11)

  因此 11|a的充要条件是11| a0-a1+a2-+(-1)nan.

求正整数a能被7整除的条件。

解  由于 1000-1 (mod 7),从而1000k(-1)k (mod 7), k=0,1,2,,n,

 于是设a= anan-1a1a0 (1000)  这就有aa0-a1+a2-+(-1)nan (mod 7)

 因此 7|a的充要条件是a0-a1+a2-+(-1)na0 (mod 7) 这里的ai为三位数(一千进制).

 如当a=89101234579时,由于579-234+101-89=3570 (mod 7),所以7|a

定义2 如果m为自然数,集合Kr={x|x=mt+r,t是任意整数}r=0,1,,m

则称K0,K1,,Km-1m的剩余类

例如,模2的剩余类是偶数类与奇数类;模3的剩余类是:K0={,-6,-3,0,3,6,}K1={,-5,-2,1,4,7,}K2={,-4,-1,2,5,8}

剩余类具有如下列比较明显的性质:

1)模m的剩余类K0K1,……,Km-1都是整数的非空子集;

2)每个整数必属于且只属于一个剩余类;

3)两个整数属于同一个剩余类的充要条件是它们对模m同余。

定义3 从模m的每个剩余类中任取一个数,所得到的m个数叫做m的完全剩余系

对模m来说,它的完全剩余系是很多的,经常采用的是:

0,1,2,,m-1;

1,2,3,,m;

-(m-1)/2,,-1,0,1,,m/2   (m为奇数)

-m/2+1,,-1,0,1,,m/2     (m为偶数)

-m/2,,-1,0,1,,m/2-1     (m为偶数).

 

定理6  k个整数a1,a2,,ak构成模m的完全剩余系的充要条件是k=m,且这m个数对模m两两不同余。

定理7   若x1,x2,,xm 是模m的完全剩余系,(a,m=1,b为整数,则ax1+bax2+b,…,axm+b也是模m的完全剩余系。(注:(m,n)表示m,n的最大公约数

二 欧拉函数

定义在模m的完全剩余系中,所有与m互素的数叫做m的简化剩余系。例如1379是模10的一个简化剩余系。

定义若对任意的自然数m,用记号ф(m)表示0,1,2,,m-1中与m互素的数的个数,则称ф(m)欧拉函数

例如ф(10)=4,ф(7)=6,ф(1)=1

定理k个整数a1,a2,,ak构成模m简化剩余系的充要条件是k=ф(m)(ai,m)=1,i=1,2,ф(m),且这ф(m)个数对模m两两不同余。

定理(a,m)=1x1,x2,,xф(m)是模m的简化剩余系,则ax1,ax2,,axф(m)也是模m的简化剩余系。

定理3(欧拉定理) 若(a,m)=1,则aф(m) ≡1 (mod m)

证 设x1,x2,,xф(m)是模m的简化剩余系,根据定理2ax1,ax2,,axф(m)也是模m的简化剩余系。

由此可知x1,x2,,xф(m)中任一个数必与ax1,ax2,,axф(m)中某一个数对模m同余;反之ax1,ax2,,axф(m)中任一个数必与x1,x2,,xф(m)中某一个数对模m同余,这就有:

ax1ax2axф(m)x1x2xф(m) (mod m),(x1x2xф(m),m)=1,所以aф(m) ≡1 (mod m)

1 已知x=h是使ax1 (mod m)中成立的最小正整数,求证h|ф(m)

证 由ah-1=mt(t为整数)可知(a,m)=1,于是

aф(m) ≡1 (mod m)

令ф(m)=hq+r,0<=r为自然数

代入上面的同余式,可得 ar ≡1 (mod m),所以r=0,故h|ф(m)

推论(费马小定理) 若p是素数,则

1) 当(a,p)=1时,ap-1 ≡1 (mod p)

2) ap ≡a (mod p)

证 先证1)。由p是素数,知0,1,2,,p-1中有p-1个数与p互素,于是ф(p)=p-1。又因为(a,p)=1,所以根据定理3得证1)。

再证2)。当(a,p)=1时,由1)知2)成立;当(a,p)不等于1时,p|a,余数同为0,2)也成立。

欧拉在1760年证明了定理3,故称为欧拉定理。费马在1640年提出了上面的推论,它的证明是欧拉在1736年完成的,这个推论通常叫做费马小定理。

2 设a为整数,求证a5a(mod 30).

证 由于30=2.3.5,而依据费马小定理,有

a5a(mod 5) (1)

a3a(mod 3) (2)

a2a(mod 2) (3)

(2)得 a5a3a(mod 3) 4

(3)a5a4a2a(mod 2) (5)

于是由(1).(4),(5),并且2,3,5两两互素,所以 a5a(mod 30).

定理4 若p是素数,则ф(pa)=pa-pa-1。 (ф(pa)的计算公式)

证 考虑模pa的完全剩余系0,1,2,,p,,2p,,pa-1 (1)

(1)式中与pa不互素的数只有p的倍数0,p,2p,,(pa-11)p,这共有p a-1个,于是(1)中与pa互素的数有pa-p a-1个,所以ф(pa)=pa-pa-1

定理5 若(m,n)=1,则ф(mn)=ф(m)ф(n)

推论 若正整数m1,m2,mk两两互素,则ф(m1m2mk)=ф(m1)ф(m2)…ф(mk).

定理6 若m的标准分解式为m=p1a1p2a2pkak,

则ф(m)=p1a1-1p2a2-1pkak-1(p1-1)(p2-1)(pk-1).

3 设(n,10)=1,求证n101n的末三位数相同。

证:为了证明n101-n0只要证明n1001(mod 1000).

事实上由(n,125)=1,φ(125)= φ(5^3)=5^3-5^2=100,有n1001(mod 125);

再由n是奇数知8|n^2-1,进而n^1001(mod 8),(125,8)=1,得证。

阅读(1281) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册