HDU3508的结论证明Author:[BUPT]TsuraraDate:2010/08/06记：GCD(m,n)=(m,n)，LCM(m,n)=[m,n]，m整除n=m|n。原题：Youaregivenapositiveintegerm.Calculatetheproductofallpositiveintegerslessthenorequaltomandcoprimewithm,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(modm)，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)=1a^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