HDU3508的结论证明.pdfVIP

HDU3508 的结论证明 Author:[BUPT]Tsurara Date: 2010/08/06 记：GCD(m,n)=(m,n)，LCM(m,n)=[m,n]，m 整除 n=m|n。 原题： You are given a positive integer m. Calculate the product of all positive integers less then or equal to m and coprime with m, and give the answer modulo m 对于正整数 m ，求所有所有小于m 且与m 互质的正整数的乘积，结果模m 。 求证： 对于正整数 m ，令S 为所有小于m 且与m 互质的正整数的集合，P 为 S 中所有元素的乘积。 则P ≡ ±1 (mod m) ，且P ≡ -1 (mod m) 当且仅当m 有原根。 引理0 ：(Euler 函数) 定义对正整数m ，φ(m)为小于等于m 的正整数中与m 互质的数的个数，成为 Euler 函数。 Euler 函数的性质作为引理0 。 Euler 函数的性质见： /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 (mod m)有 （满足0xm 的唯一）解当且仅当(a,m)=1 。 证明： 必要：若 ax ≡ 1 (mod m)，则ax=1+km，ax-km=1，k 为整数。由引理 1 知，a 与m 互质。 充分：若 a 与m 互质，则由引理 1 知，存在整数x,y 使得 ax+my=1 ，ax=1-my，即ax ≡ 1 (mod m) 。 特别地， 满足 0xm 的解唯一。若x也是该方程一个解，则 ax ≡ ax ≡ 1 (mod m) ，x(ax) ≡ (xa)x (mod m) ，即x ≡ x (mod m) ，注意到0xm，则x 是唯一的。 注意到该定理事实上保证 a 与逆元x 都与m 互质。 引理3 ： 定义：设m=1 ，(a,m)=1 。则使得式 d a ≡ 1 (mod m) 成立的最小的正整数 d 称为 a 对模 m 的指数 （也称为阶或周期），记作ord (a) 。由欧拉定理 m d （数论）知使得a ≡ 1 (mod m) 的d 一定存在（比如 φ(m) ），则ord (a)=d=φ(m) 。当 m ord (a)=φ(m)时，称a 是模 m 的原根。 m n n 模 m 有原根的充分必要条件是m=1, 2, 4, p , 2p , p 为素数，n=1 。 引理3.0 ：若a ≡ b (mod m),(a,m)=1 ，则ord (a)=ord (b) 。该引理证明很简单，不赘述。 m m d 引理3.1 ：设m=1 ，(a,m)=1 。对任意整数d，若a ≡ 1 (mod m) ，则ord (a)|d 。 m 证明： 设 d=ord (a)，则d=qd+r,0=rd m d qd+r d q r r 则 a -1=a -1=(a ) a -1 ≡ a -1 (