数学难题:若a是非零自然数,n是质数且与a互质,则a^(n-1)-1定能被n整除...
发布网友
发布时间:2024-10-02 17:19
我来回答
共3个回答
热心网友
时间:2024-10-06 20:25
费马小定理是数论中的一个重要定理,其内容为: 假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1(mod p) 假如p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1
证明
一、准备知识: 引理1.剩余系定理2 若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(mod m)时,有a≡b(mod m) 证明: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<i<=m。令(1):a[1]≡r[1](mod m),a[2]≡r[2](mod m),a≡r(mod m)(顺序可以不同),因为只有在这种情况下才能保证集合{a1,a2,a3,a4,…am}中的任意2个数不同余,否则必然有2个数同余。由式(1)自然得到集合{a1,a2,a3,a4,…am}对m构成完全剩余系。 引理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),根据引理1则有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≡bd(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)
热心网友
时间:2024-10-06 20:23
这个是定理来着,找本书看一下欧拉定理证明过程(fermat-euler定理)。
为了习惯令p=n表示素数
A组取a 2a 3a ...........(p-1)a,它们两两不同余
B组取1 2 3 ..............(p-1),它们两两不同余,
所以A组 B组都是P的既约同余系
A组相乘得a^(p-1)*(p-1)!
B组相乘得 (p-1)!
二者对模P必同余,因此a^(p-1)同余1(否则设a^(p-1)同余1<r<p, 设(p-1)!同余0<s<p, 则rs同余s, rs-s=(r-1)s是p的倍数,而0<r-1、s<p,积不可能是p的倍数)
热心网友
时间:2024-10-06 20:28
二者对模P必同余,因此a^(p-1)同余1(否则设a^(p-1)同余1<r<p, 设(p-1)!同余0<s<p, 则rs同余s, rs-s=(r-1)s是p的倍数,而0<r-1、s<p,积不可能是p的倍数)