定理(威尔逊定理) p为素数if(p-1)!=-1(modp) 证明 必要性:设p为一素数,当p=2,3时,结论显然成立 现设p>3是一奇素数,S={2,3,…,p-2},a∈S.因为 (a,p)=1,存在整数m和n,使am+pn=1,于是 am=l(mod p). 设b=m-pq,即b是p除m的余数,易知b≠1,b却-1, 故b∈S,且ab=1(modp).可以证明a≠b
定理 (威尔逊定理) p为素数 iff (p-l)!-1(mod p). 证明 必要性: 设p为一素数, 当p=2,3时, 结论显然成立. 现设p>3是一奇素数, S={2, 3, …, p-2}，aS. 因为 (a,p)=1, 存在整数m和n, 使am+pn=1, 于是 am1(mod p). 设b=m-pq, 即b是p除m的余数, 易知 b≠1, b≠p-1, 故 bS, 且 ab1(mod p). 可以证明 a≠b
定理(威尔逊定理) p为素数if(p-)=-1(modp) 假设a=b,则有(b-1)(b+1)=0(modp),而b+l,b p-1,故(b-1)(b+1)=0(modp)不成立 可见S中的数可分成(p-3)2对,每一对数a和b,满 足ab=l(modp),故得23.!p-2)≡(modp),即可得 (p-1)!≡-1(modp)
定理 (威尔逊定理) p为素数 iff (p-l)!-1(mod p). 假设 a=b, 则有(b-1)(b+1)0(mod p), 而 b≠l, b ≠p-1, 故(b-1)(b+1)0(mod p)不成立. 可见S中的数可分成(p-3)/2对, 每一对数a和b, 满 足 abl(mod p), 故得2·3…(p-2) (mod p), 即可得 (p-1)! -1 (mod p)
定理(威尔逊定理) p为素数if(p-1)=-1(modp) 充分性:若(p-1)!=l(modp),则p为素数 假设p是合数,令p=ab,a中p 由题设条件知,p|(p-1)!+1) 又因a|p,则有a|(p-1)+1) 但由于ap-1可得a|(p-1)!, 从而a|(p-1)!+1)-(p-1)!),即a|l, 因而p只有因子1和p,即p为素数
定理 (威尔逊定理) p为素数 iff (p-l)!-1(mod p). 充分性: 若(p-1)! = -l (mod p), 则 p为素数. 假设p是合数, 令 p＝ab, a≠p. 由题设条件知, p|((p-1)!+l). 又因 a|p, 则有 a|((p-1)!+1). 但由于 a≤p-1可得 a|(p-1)!, 从而 a|(((p-1)!+1)-(p-1)!), 即a|l, 因而p只有因子1和p, 即p为素数
同余关系及其在计算机领域的应用 同余的应用1:国际图书标准(SBN编码 sBN是 international standard of book number的缩写,即国 际标准图书编号。lsBN是国际通用的图书或独立的出版物(除定期出版 的期刊)代码。出版社可以通过sBN清晰地辨认所有非期刊书籍。一个 1sBN只有一个或一份相应的出版物与之对应。新版本如果在原来旧版 的基础上没有内容上太大的变动,在出版时也不会得到新的SBN号码。 当平装本改为精装本出版时,原来相应的sBN号码也应当收回。 国际标准图书编号问世后,很快得到推广,主要是因为它对出版 商、书商的工作有很大的益处,体现在:国际标准书号是机读的编码 从图书的生产到发行、销售始终如一,对图书的发行系统起了很大的 作用;它的引入使图书的定购、库存控制、账目和输出过程等任何图书 业的分支程序都简化了;国际标准书号也对图书馆和文献中心的订购、 采选、编目和流通程序都有促进作用;sBN系统的引入也服务于书目信 息的流动和使用,而且为一个国家的图书生产提供经济的书目控 制;SBN对图书市场更有效率,它能确定国际上出版的任何图书及其 版社。在书业中习惯称lsBN为库藏码( Stock Number),就是因为 普遍应用于书库管理
同余关系及其在计算机领域的应用 同余的应用1：国际图书标准(ISBN编码) ISBN是international standard of book number 的缩写，即国 际标准图书编号。ISBN是国际通用的图书或独立的出版物(除定期出版 的期刊)代码。出版社可以通过ISBN清晰地辨认所有非期刊书籍。一个 ISBN只有一个或一份相应的出版物与之对应。新版本如果在原来旧版 的基础上没有内容上太大的变动，在出版时也不会得到新的ISBN号码。 当平装本改为精装本出版时，原来相应的ISBN号码也应当收回。 国际标准图书编号问世后，很快得到推广，主要是因为它对出版 商、书商的工作有很大的益处，体现在:国际标准书号是机读的编码， 从图书的生产到发行、销售始终如一，对图书的发行系统起了很大的 作用;它的引入使图书的定购、库存控制、账目和输出过程等任何图书 业的分支程序都简化了;国际标准书号也对图书馆和文献中心的订购、 采选、编目和流通程序都有促进作用;ISBN系统的引入也服务于书目信 息的流动和使用，而且为一个国家的图书生产提供经济的书目控 制;ISBN对图书市场更有效率，它能确定国际上出版的任何图书及其出 版社。在书业中习惯称ISBN为库藏码(Stock Number)，就是因为其被 普遍应用于书库管理
同余关系及其在计算机领域的应用 10位数sBN的结构 现行的sBN由10位数字组成,这10位数字由4组数字组成,中间用 相连,每组数字都有不同的含义 第一组号码是地区号,又叫组号,最短的只有一位数字,最长的达五位数 字,大体上兼顾文种、国别和地区。0、1代表英语,使用这两个代码的 国家有:澳大利亚、加拿大、爱尔兰、新西兰、波多黎各、南非、英国、 美国、津巴布韦等;2代表法语,法国、卢森堡以及比利时、加拿大和瑞士 的法语区使用该代码;3代表德语,德国、奥地利和瑞士德语区使用该代 码;4是日本出版物的代码;5是俄罗斯出版物的代码;7是中国出版物使用的 代码。 第二组:出版社代码。由国家或地区的sBN中心设置并分给各个出版社。 第三组:书序码。该出版物代码,是出版者分配给每一个出版物的编号。 第四组:计算机校验码。校验码是SBN号的最后一位数值,它能够校验出 sBN号是否正确。校验码只能是1位数,当为10时,记为罗马数字X
同余关系及其在计算机领域的应用 10位数ISBN的结构 现行的ISBN由10位数字组成，这10位数字由4组数字组成，中间用 “-”相连，每组数字都有不同的含义。 第一组号码是地区号，又叫组号，最短的只有一位数字，最长的达五位数 字，大体上兼顾文种、国别和地区。0、1代表英语，使用这两个代码的 国家有:澳大利亚、加拿大、爱尔兰、新西兰、波多黎各、南非、英国、 美国、津巴布韦等;2代表法语，法国、卢森堡以及比利时、加拿大和瑞士 的法语区使用该代码;3代表德语，德国、奥地利和瑞士德语区使用该代 码;4是日本出版物的代码;5是俄罗斯出版物的代码;7是中国出版物使用的 代码。 第二组: 出版社代码。由国家或地区的ISBN中心设置并分给各个出版社。 第三组:书序码。该出版物代码，是出版者分配给每一个出版物的编号。 第四组:计算机校验码。校验码是ISBN号的最后一位数值，它能够校验出 ISBN号是否正确。校验码只能是1位数，当为10时，记为罗马数字X