HDU3508的结论证明.pdf

HDU3508的结论证明
Author:[BUPT]TsuraraDate:2010/08/06

记：GCD(m,n)=(m,n)，LCM(m,n)=[m,n]，m整除n=m|n。

原题：
Youaregivenapositiveintegerm.Calculatetheproductofallpositiveintegerslessthenorequal
tomandcoprimewithm,andgivetheanswermodulom.
对于正整数m，求所有所有小于m且与m互质的正整数的乘积，结果模m。

求证：
对于正整数m，令S为所有小于m且与m互质的正整数的集合，P为S中所有元素的乘积。
则P≡±1(modm)，且P≡-1(modm)当且仅当m有原根。

引理0：(Euler函数)
定义对正整数m，φ(m)为小于等于m的正整数中与m互质的数的个数，成为Euler函数。
Euler函数的性质作为引理0。
Euler函数的性质见：
http://zh.wikipedia.org/zh-cn/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0
引理1：(Bezout定理推论)
方程ax+by=1有整数解当且仅当a与b互质，即(a,b)=1。
该定理证明不在此赘述。
引理2：
正整数a模m的乘法逆元存在（且唯一）当且仅当a与m互质。即ax≡1(modm)有
（满足0<x<m的唯一）解当且仅当(a,m)=1。
证明：
必要：若ax≡1(modm)，则ax=1+km，ax-km=1，k为整数。由引理1知，a与m互质。
充分：若a与m互质，则由引理1知，存在整数x,y使得ax+my=1，ax=1-my，即ax≡1
(modm)。
特别地，满足0<x<m的解唯一。若x'也是该方程一个解，则ax≡ax'≡1(mod
m)，x(ax)≡(xa)x'(modm)，即x≡x'(modm)，注意到0<x<m，则x是唯一的。
注意到该定理事实上保证a与逆元x都与m互质。
引理3：
定义：设m>=1，(a,m)=1。则使得式
ad≡1(modm)
成立的最小的正整数称为对模的指数（也称为阶或周期），记作。由欧拉定理
damordm(a)
（数论）知使得d的一定存在（比如），则。当
a≡1(modm)dφ(m)ordm(a)=d<=φ(m)
时，称是模的原根。
ordm(a)=φ(m)am
模m有原根的充分必要条件是m=1,2,4,pn,2pn,p为素数，n>=1。

引理：若，则。该引理证明很简单，不赘述。
3.0a≡b(modm),(a,m)=1ordm(a)=ordm(b)
引理：设，。对任意整数，若d，则。
3.1m>=1(a,m)=1da≡1(modm)ordm(a)|d
证明：
设，则
d'=ordm(a)d=qd'+r,0<=r<d'
则ad-1=aqd'+r-1=(ad')qar-1≡ar-1(modm)
因为0<=r<d'，由d的定义知r=0，证毕。
推论：由欧拉定理，。
3.1ordm(a)|φ(m)
引理：若，则；若，则。
3.2a,n|mordn(a)|ordm(a)b,(n,m)=1ordnm(a)=[ordn(a),ordm(a)]
证明：
由易知，由引理有
a:a^(ordm(a))≡1(modm)a^(ordm(a))≡1(modn)3.1ordn(a)|
。
ordm(a)
记，由有，。因此
b:ord=[ordn(a),ordm(a)]aordm(a)|ordmn(a)ordn(a)|ordmn(a)
。又且，而，则有
ord|ordmn(a)a^ord≡1(modm)a^ord≡1(modn)(m,n)=1
a^ord≡1(modmn)，则
。因此。
ordmn(a)|ordord=[ordn(a),ordm(a)]=ordnm(a)
引理：设的质因数分解为α0α1α2αk，则，
3.3mm=2p1p2...pkordm(a)|λ(m)
其中
cα1α2αk
λ(m)=[2,φ(p1),φ(p2),...,φ(pk)],c=0(α0=0,1);1(α0=2);α0-2(α0>=3)
λ(m)称为Carmichael函数。
证明：
由引理知，而由引理我们有
3.2bordm(a)=[ord2^α0(a),ordp1^α1(a),ordp2^α2(a),...,ordpk^αk(a)]1
α0c，α1，，αk。因此。
ord2^α0(a)|φ(2)(=2)ordp1^α1(a)|φ(p1)...ordpk^αk(a)|φ(pk)ordm(a)|λ(m)
引理：设为非负整数，则k。
3.4kordm(a)=ordm(a)/(ordm(a),k)
证明：
记k，即要求证。
ord=ordm