(38G) Kronecker (Quadratic Character) Symbol

[Gerald H]

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.

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: