勒让德符号

Legendre 符号

函数 Legendre(a,p)

返回 $\bigl(\frac{a}{p}\bigr)$,

定义:  $p$ 是一奇素数, $a$ 不能被 $p$ 除尽. 当 $a$ 是数 $p$ 的平方剩余时, 符号 $\bigl(\frac{a}{p}\bigr)$ 表示 $+1$; 当 $a$ 是数 $p$ 的平方非剩余时, 符号 $\bigl(\frac{a}{p}\bigr)$ 表示 $-1$. 

这个符号是勒让德引入的.

勒让德符号的性质

Claim 1.  若 $a\equiv b\pmod p$, 则 $\bigl(\frac{a}{p}\bigr)=\bigl(\frac{b}{p}\bigr)$.

算法:

1.  若 $a > p$, 则计算 $b=a \mod p$.  利用 Claim 1.

关于 Legendre 符号的性质, 见问题2855, 1802, 1751

>> :mode=polyn
Switch into polynomial mode.

>> (x+1)*(x^2-x+1)
in> (x+1)*(x^2-x+1)

out> 1x^3+0x^2+0x^1+1x^0

------------------------

改进:

1.  编写简化程序, 将系数为 0 的项删除.

2.  当系数为 1 且 x 的指数不为 0 时, 比如 1x^3 简写为 x^3; 而当指数为 0 时, 简写为 1;

3.  变元可以自己指定, 目前只支持 x.

4.  系数可以是符号, 比如 (ax+1)*(bx+c)

5.  将目前的 polyn 模式更名为 polynZ, 表示整系数一元多项式模式.  polyn 代表一般的模式.

已经完成 1 和 2.  见 show_poly() 和 show_poly_DES() 函数. 事实上, 这两个函数应该合并在一起.

>> (x+1)*(x^2-x+1)
in> (x+1)*(x^2-x+1)

out> x^3+1

添加 sort() 函数,  函数可以是如下形式

sort(N1,N2,...,Nm)

sort(N1,N2,...,Nm;/)   递增排序, 最后一个参数可以是 / 或 ASC

sort(N1,N2,...,Nm;\)    递减排序, 最后一个参数可以是 \ 或 DEC

sort("filename.txt")    //对filename.txt 中的数据进行排序, 默认输出为 filename_sorted.txt

Erdös-Strass 猜想参见问题1864.

函数:

Erdos_Strass_conj(n)

返回满足

\[
\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}
\]

的正整数解 $x,y,z$.