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.

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:

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.

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: