一、準(zhǔn)備知識(shí)：
引理1．剩余系定理2
若a,b,c為任意3個(gè)整數(shù),m為正整數(shù),且(m,c)=1,則當(dāng)ac≡bc(modm)時(shí),有a≡b(modm)
證明：ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因?yàn)?m,c)=1即m,c互質(zhì),c可以約去,a–b≡0(mod m)可得a≡b(mod m)
引理2．剩余系定理5
若m為整數(shù)且m>1,a[1],a[2],a[3],a[4],…a[m]為m個(gè)整數(shù),若在這m個(gè)數(shù)中任取2個(gè)整數(shù)對(duì)m不同余,則這m個(gè)整數(shù)對(duì)m構(gòu)成完全剩余系.
證明：構(gòu)造m的完全剩余系（0,1,2,…m-1）,所有的整數(shù)必然這些整數(shù)中的1個(gè)對(duì)模m同余.取r[1]=0,r[2]=1,r[3]=2,r[4]=3,…r=i-1,1引理3．剩余系定理7
設(shè)m是一個(gè)整數(shù),且m>1,b是一個(gè)整數(shù)且(m,b)=1.如果a1,a2,a3,a4,…am是模m的一個(gè)完全剩余系,則ba[1],ba[2],ba[3],ba[4],…ba[m]也構(gòu)成模m的一個(gè)完全剩余系.
證明：若存在2個(gè)整數(shù)ba和ba[j]同余即ba≡ba[j](mod m),根據(jù)引理2則有a≡a[j](mod m).根據(jù)完全剩余系的定義和引理4（完全剩余系中任意2個(gè)數(shù)之間不同余,易證明）可知這是不可能的,因此不存在2個(gè)整數(shù)ba和ba[j]同余.由引理5可知ba[1],ba[2],ba[3],ba[4],…ba[m]構(gòu)成模m的一個(gè)完全剩余系.
引理4．同余定理6
如果a,b,c,d是四個(gè)整數(shù),且a≡b(mod m),c≡d(mod m),則有ac≡bd(mod m)
證明：由題設(shè)得ac≡bc(mod m),bc≡bd(mod m),由模運(yùn)算的傳遞性可得ac≡bc(mod m)
二、證明過(guò)程：
構(gòu)造素?cái)?shù)p的完全剩余系P={1,2,3,4…(p-1)},因?yàn)?a,p)=1,由引理3可得A={a,2a,3a,4a,…(p-1)a}也是p的一個(gè)完全剩余系.令W=1*2*3*4…*(p-1),顯然W≡W(mod p).令Y=a*2a*3a*4a*…(p-1)a,因?yàn)閧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）