如何在Excel中计算整数a与素数p的Legendre符号

Legendre符号$\left(\frac{a}{p}\right)$的规则是：

• 若整数$a$能被素数$p$整除，结果为0；
• 若$a$是模$p$的二次剩余且不被$p$整除，结果为1；
• 若$a$是模$p$的非二次剩余，结果为-1。

可用的Excel公式 #

假设整数$a$存于单元格A1，素数$p$存于单元格B1，直接使用以下嵌套公式即可：

=IF(MOD(A1,B1)=0,0,IF(MOD(MOD(A1,B1)^((B1-1)/2),B1)=1,1,-1))

公式拆解 #

1. 第一步判断整除性：MOD(A1,B1)=0时直接返回0，对应符号定义的第一种情况；
2. 应用欧拉判别法：先取a mod p避免大数运算，再计算其(p-1)/2次方后对p取模；
3. 判定剩余类型：模p结果为1则返回1（二次剩余），否则返回-1（此时结果必为p-1，等价于-1模p）。

注意事项 #

• 务必保证B1中的值是素数，否则结果不符合Legendre符号的定义；
• 若a为负数，Excel的MOD函数会返回非负余数，不影响最终计算；
• 对$p=2$的情况同样适用：a为偶数时返回0，奇数时返回1，完全符合符号定义。

内容的提问来源于stack exchange，提问作者Robin