hdu3508的结论证明

《hdu3508的结论证明》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、HDU3508的结论证明Author:[BUPT]TsuraraDate:2010/08/06记：GCD(m,n)=(m,n)，LCM(m,n)=[m,n]，m整除n=m

2、n。原题：Youaregivenapositiveintegerm.Calculatetheproductofallpositiveintegerslessthenorequaltomandcoprimewithm,andgivetheanswermodulom.对于正整数m，求所有所有小于m且与m互质的正整数的乘积，结果模m。求证：对于正整数m，令S为所有

3、小于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。该定理证明不在此

4、赘述。引理2：正整数a模m的乘法逆元存在（且唯一）当且仅当a与m互质。即ax≡1(modm)有（满足0

5、一的。注意到该定理事实上保证a与逆元x都与m互质。引理3：定义：设m>=1，(a,m)=1。则使得式da≡1(modm)成立的最小的正整数d称为a对模m的指数（也称为阶或周期），记作ordm(a)。由欧拉定理d（数论）知使得a≡1(modm)的d一定存在（比如φ(m)），则ordm(a)=d<=φ(m)。当ordm(a)=φ(m)时，称a是模m的原根。nn模m有原根的充分必要条件是m=1,2,4,p,2p,p为素数，n>=1。引理3.0：若a≡b(modm),(a,m)=1，则ordm(a)=ordm(b)。该引理证明很简单，

6、不赘述。d引理3.1：设m>=1，(a,m)=1。对任意整数d，若a≡1(modm)，则ordm(a)

7、d。证明：设d'=ordm(a)，则d=qd'+r,0<=r

8、φ(m)。引理3.2：a,若n

9、m，则ordn(a)

10、ordm(a)；b,若(n,m)=1，则ordnm(a)=[ordn(a),ordm(a)]。证明：a:由a^(ordm(a))≡1(modm)易知a

11、^(ordm(a))≡1(modn)，由引理3.1有ordn(a)

12、ordm(a)。b:记ord=[ordn(a),ordm(a)]，由a有ordm(a)

13、ordmn(a)，ordn(a)

14、ordmn(a)。因此ord

15、ordmn(a)。又a^ord≡1(modm)且a^ord≡1(modn)，而(m,n)=1，则有a^ord≡1(modmn)，则ordmn(a)

16、ord。因此ord=[ordn(a),ordm(a)]=ordnm(a)。α0α1α2αk引理3.3：设m的质因数分解为m=2p1p2...pk，则ordm(a)

17、

18、λ(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.2b知ordm(a)=[ord2^α0(a),ordp1^α1(a),ordp2^α2(a),...,ordpk^αk(a)]，而由引理1我们有α0cα1αkord2^α0(a)

19、φ(2)(=2)，ordp1^α1(a)

20、φ(p1)，...，ordpk^αk(a)

21、φ(pk)。因此ordm(a)

22、λ(m)。k引理3.4：设k

23、为非负整数，则ordm(a)=ordm(a)/(ordm(a),k)。证明：k记ord=ordm(a),ord'=ord/(ord,k),ord''=ordm(a)，即要求证ord''=ord'。ordkord''先证明ord'

24、ord''。由条件知a≡1(modm),(a)