课程目录
本页目录
定义
设 m>1 是正奇数,m=p1p2⋯pr(其中 pi 是奇素数,可重复),gcd(n,m)=1,定义雅可比符号为:
(mn)=i=1∏r(pin)
其中 (pin) 是勒让德符号。当 m=1 时,约定 (1n)=1。
注意:雅可比符号 (mn)=1 不保证 n 是模 m 的二次剩余。只有当 m 为素数时,两者才等价。
性质
雅可比符号继承勒让德符号的大部分性质:
(a) 周期性
若 a≡b(modm),则 (ma)=(mb)。
(b) 完全积性
(mab)=(ma)(mb),(mna)=(ma)(na)
(c) 补充律
(m−1)=(−1)2m−1,(m2)=(−1)8m2−1
(d) 互反律
设 m,n 是大于 1 的互质正奇数,则
(nm)(mn)=(−1)2m−1⋅2n−1
计算优势
雅可比符号的最大意义在于:计算勒让德符号时无需对分子做质因数分解。只需利用互反律反复翻转约化,即可高效计算。
例:计算 (99071001)(9907 是素数)。
若用勒让德符号,需分解 1001=7×11×13;而用雅可比符号可直接做互反律:
(99071001)=(10019907)(∵ 1001≡1(mod4))=(10019907mod1001)=(1001898)=(10012)(1001449)=(1001449)=(4491001)=(449103)=(103449)=(10337)=(37103)=(3729)=(2937)=(298)=(292)3=−1