雅可比符号(Jacobi symbol)是勒让德符号的推广,由普鲁士数学家卡尔·雅可比于1837年引入。它在数论的多个分支中有应用,特别是在计算数论的素性检验、大数分解以及密码学中扮演着重要角色。

简介

雅可比符号(Jacobi symbol)是勒让德符号的推广,整数对整数 的雅可比符号表示为。设 是大于 1的奇数,且 的素因数分解式为 (式中因数可以相同),如果,则雅可比符号定义为:

其中,是 对 的勒让德符号。例如,取,则:

注:雅可比符号是勒让德符号的推广,但是根据雅可比符号的值不能判断同余式是否有解。

定义补充说明

(1)当 是奇素数时,雅可比符号就是勒让德符号。

(2)当 是奇素数且 时,方程 有解。当m不是奇素数时,这个结论不一定成立。

定理

定理1

(1)若,则

(2)

(3)对于任意的整数,有

(4)对于任意的整数,有

定理2

设 是奇数,其中 是素数,则下面的结论成立:

(1)

(2)

定理3

设m,n是大于1的奇整数,则

利用以上定理,可以容易计算Jacobi符号,特别是Legendre符号的数值。但是,必须注意,在判断方程 的可解性时,Legendre符号和Jacobi的作用是不一样的。

对于一般的正奇数m来说,即使条件 成立,也并不能保证 一定有解。

举例

例1

已知3371是素数,判断方程 是否有解。

解:利用Jacobi符号的性质,有

因此,方程无解。

例2

设a与b是正奇数,求 的关系。

解:

参考资料