题目
怎么证明费马小定理?
证明:假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1(mod p)
证明:假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1(mod p)
提问时间:2021-03-23
答案
一、准备知识:
引理1.剩余系定理2
若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(modm)时,有a≡b(modm)
证明:ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因为(m,c)=1即m,c互质,c可以约去,a–b≡0(mod m)可得a≡b(mod m)
引理2.剩余系定理5
若m为整数且m>1,a[1],a[2],a[3],a[4],…a[m]为m个整数,若在这m个数中任取2个整数对m不同余,则这m个整数对m构成完全剩余系.
证明:构造m的完全剩余系(0,1,2,…m-1),所有的整数必然这些整数中的1个对模m同余.取r[1]=0,r[2]=1,r[3]=2,r[4]=3,…r=i-1,1 引理3.剩余系定理7
设m是一个整数,且m>1,b是一个整数且(m,b)=1.如果a1,a2,a3,a4,…am是模m的一个完全剩余系,则ba[1],ba[2],ba[3],ba[4],…ba[m]也构成模m的一个完全剩余系.
证明:若存在2个整数ba和ba[j]同余即ba≡ba[j](mod m),根据引理2则有a≡a[j](mod m).根据完全剩余系的定义和引理4(完全剩余系中任意2个数之间不同余,易证明)可知这是不可能的,因此不存在2个整数ba和ba[j]同余.由引理5可知ba[1],ba[2],ba[3],ba[4],…ba[m]构成模m的一个完全剩余系.
引理4.同余定理6
如果a,b,c,d是四个整数,且a≡b(mod m),c≡d(mod m),则有ac≡bd(mod m)
证明:由题设得ac≡bc(mod m),bc≡bd(mod m),由模运算的传递性可得ac≡bc(mod m)
二、证明过程:
构造素数p的完全剩余系P={1,2,3,4…(p-1)},因为(a,p)=1,由引理3可得A={a,2a,3a,4a,…(p-1)a}也是p的一个完全剩余系.令W=1*2*3*4…*(p-1),显然W≡W(mod p).令Y=a*2a*3a*4a*…(p-1)a,因为{a,2a,3a,4a,…(p-1)a}是p的完全剩余系,由引理2以及引理4可得a*2a*3a*…(p-1)a≡1*2*3*…(p-1)(mod p)即W*a^(p-1)≡W(modp).易知(W,p)=1,由引理1可知a^(p-1)≡1(modp)
引理1.剩余系定理2
若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(modm)时,有a≡b(modm)
证明:ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因为(m,c)=1即m,c互质,c可以约去,a–b≡0(mod m)可得a≡b(mod m)
引理2.剩余系定理5
若m为整数且m>1,a[1],a[2],a[3],a[4],…a[m]为m个整数,若在这m个数中任取2个整数对m不同余,则这m个整数对m构成完全剩余系.
证明:构造m的完全剩余系(0,1,2,…m-1),所有的整数必然这些整数中的1个对模m同余.取r[1]=0,r[2]=1,r[3]=2,r[4]=3,…r=i-1,1 引理3.剩余系定理7
设m是一个整数,且m>1,b是一个整数且(m,b)=1.如果a1,a2,a3,a4,…am是模m的一个完全剩余系,则ba[1],ba[2],ba[3],ba[4],…ba[m]也构成模m的一个完全剩余系.
证明:若存在2个整数ba和ba[j]同余即ba≡ba[j](mod m),根据引理2则有a≡a[j](mod m).根据完全剩余系的定义和引理4(完全剩余系中任意2个数之间不同余,易证明)可知这是不可能的,因此不存在2个整数ba和ba[j]同余.由引理5可知ba[1],ba[2],ba[3],ba[4],…ba[m]构成模m的一个完全剩余系.
引理4.同余定理6
如果a,b,c,d是四个整数,且a≡b(mod m),c≡d(mod m),则有ac≡bd(mod m)
证明:由题设得ac≡bc(mod m),bc≡bd(mod m),由模运算的传递性可得ac≡bc(mod m)
二、证明过程:
构造素数p的完全剩余系P={1,2,3,4…(p-1)},因为(a,p)=1,由引理3可得A={a,2a,3a,4a,…(p-1)a}也是p的一个完全剩余系.令W=1*2*3*4…*(p-1),显然W≡W(mod p).令Y=a*2a*3a*4a*…(p-1)a,因为{a,2a,3a,4a,…(p-1)a}是p的完全剩余系,由引理2以及引理4可得a*2a*3a*…(p-1)a≡1*2*3*…(p-1)(mod p)即W*a^(p-1)≡W(modp).易知(W,p)=1,由引理1可知a^(p-1)≡1(modp)
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
1,人们染上烟瘾,最终因吸烟使自己丧命.
最新试题
热门考点
- 1平民寻白羽
- 2有关enjoy的用法
- 3a,b满足a(a十|)一(a的平方十2b)=I,求a的平方一4ab十4b的平方一2a十4b的值
- 4六一班有学生50人, 会游泳的占全班人数的72%,女生25人中有40%不会游泳,男生有百分之几不会游泳?
- 5《慈母情深》阅读理解题 对于“我”买书,母亲的态度是(),由此可以看出母亲().
- 6大度容人的容的意思
- 7定语从句where is the shop?you bought the clothes in the shop.
- 8扩展是什么意思
- 9我国的国歌及词和曲作者分别是谁
- 10如图,抛物线y1=-x2+2向右平移1个单位得到抛物线y2,则图中阴影部分的面积是( ) A.2 B.3 C.4 D.无法计算