作业帮如何证明费马小定理
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/08 02:09:14
如何证明费马小定理
如何证明费马小定理
如何证明费马小定理
引理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
楼上都是用的是欧拉的证明，但是我认为这个证明太长了并且需要有一定的初等数论基础，下面我用归纳法证明。
反向归纳法：设P(n)是含正整数n的命题，如果1.有无穷多的正整数n使得P（n）成立，2.在假定P（k+1)成立的前提下，P（k)成立，那么P（n）对于所有的正整数n均成立。
证明：
令m=lp，则费吗小定理可以变成：（lp)^p-(...
全部展开
楼上都是用的是欧拉的证明，但是我认为这个证明太长了并且需要有一定的初等数论基础，下面我用归纳法证明。
反向归纳法：设P(n)是含正整数n的命题，如果1.有无穷多的正整数n使得P（n）成立，2.在假定P（k+1)成立的前提下，P（k)成立，那么P（n）对于所有的正整数n均成立。
证明：
令m=lp，则费吗小定理可以变成：（lp)^p-(lp)^p,由于l可以取任意的正整数，所以有无穷多的正整数使得该命题成立。
假定P（k+1)成立，利用二项式定理展开(k+1)^p-(k+1)=(k^p-k)+C(1,p)K^(p-1)+C（2，p）k^(p-1)+........................C(p-1,p)K (C(m,n)表示组合数，不会打请谅解！）
由于p整除于C（m,p)，在题设的假定下，p整除于(k+1)^p-(k+1），所以P整除于（K^p-k）即P（k)成立，由反向归纳法可知对于任意的正整数费马小定理均成立。
证毕
相较于楼上的证明这个证明要简洁的多并且要简单得多，回避了欧拉的证明中欧拉定理和简化剩余系的铺垫。
收起
对与p互质的整数a，考虑a,2a,3a...(p-1)a，由p是质数，任何两个的差不被p整除，所以任何两个数模p不同余，即a,2a,3a...(p-1)a是1,2,3..p-1的一个排列。将两组数全相乘，得到a*2a*3a*...*(p-1)a=1*2*3..*(p-1)，整理成(p-1)!*a^(p-1)同余(p-1)!(mod p)。由于(p-1)!和p互质，两遍可以约掉，就有a^(p-1)同...
全部展开
对与p互质的整数a，考虑a,2a,3a...(p-1)a，由p是质数，任何两个的差不被p整除，所以任何两个数模p不同余，即a,2a,3a...(p-1)a是1,2,3..p-1的一个排列。将两组数全相乘，得到a*2a*3a*...*(p-1)a=1*2*3..*(p-1)，整理成(p-1)!*a^(p-1)同余(p-1)!(mod p)。由于(p-1)!和p互质，两遍可以约掉，就有a^(p-1)同余1模p
收起