03-20-2015, 08:15 AM
Edit: Updated definition of (0,-1) to be 1 rather than 0.
The Kronecker symbol is a generalization of the Jacobi symbol, itself a generalization of the Legendre symbol.
The Legendre symbol (a/b) returns 1 if a is a quadratic residue of b, -1 if not & 0 if the GCD(a,b)>1, b an odd prime.
The Jacobi symbol allows b to be the product of odd primes & then returns results as for the product of the individual Legendre symbols of the factors of b.
The Kronecker symbol allows b to be any integer.
Input to the programme:
{ a , b }
returns
1, -1 or 0.
Remember: the Kronecker symbol does NOT indicate a quadratic residue if it returns 1. The individual prime factors may have Legendre symbols of -1 & -1, ie their product is 1, which the Kronecker symbol returns.
The Kronecker symbol is a generalization of the Jacobi symbol, itself a generalization of the Legendre symbol.
The Legendre symbol (a/b) returns 1 if a is a quadratic residue of b, -1 if not & 0 if the GCD(a,b)>1, b an odd prime.
The Jacobi symbol allows b to be the product of odd primes & then returns results as for the product of the individual Legendre symbols of the factors of b.
The Kronecker symbol allows b to be any integer.
Input to the programme:
{ a , b }
returns
1, -1 or 0.
Remember: the Kronecker symbol does NOT indicate a quadratic residue if it returns 1. The individual prime factors may have Legendre symbols of -1 & -1, ie their product is 1, which the Kronecker symbol returns.
Code:
Ans►L1:
Ans(1)►A:
L1(2)►B:
IF B==-1
THEN
1:
IF A<0
THEN
-1:
END:
ELSE
IF B
THEN
IF (A MOD 2)+(B MOD 2)
THEN
0►V:
WHILE NOT(B MOD 2)
REPEAT
B/2►B:
V+1►V:
END:
1:
IF V MOD 2
THEN
IF ABS((A MOD 8)-4)==1
THEN
-1:
END:
END:
Ans►K:
IF B<0
THEN
-B►B:
IF A<0
THEN
-K►K:
END:
END:
WHILE A
REPEAT
0►V:
WHILE NOT(A MOD 2)
REPEAT
V+1►V:
A/2►A:
END:
IF V MOD 2
THEN
IF ABS((B MOD 8)-4)==1
THEN
-K►K:
END:
END:
IF (A MOD 4)*(B MOD 4)==9
THEN
-K►K:
END:
ABS(A)►R:
B MOD R►A:
R►B:
END:
(B==1)K:
ELSE
0:
END:
ELSE
ABS(A)==1:
END:
END: