11.8 Legendre

Legendre( n, m )

Legendre returns the value of the Legendre symbol of the integer n modulo the positive integer m.

The value of the Legendre symbol L(n/m) is 1 if n is a quadratic residue modulo m, i.e., if there exists an integer r such that r^2 = n mod m and -1 otherwise.

If a root of n exists it can be found by RootMod (see RootMod).

While the value of the Legendre symbol usually is only defined for m a prime, we have extended the definition to include composite moduli too. The Jacobi symbol (see Jacobi) is another generalization of the Legendre symbol for composite moduli that is much cheaper to compute, because it does not need the factorization of m (see FactorsInt).

    gap> Legendre( 5, 11 );
    1         # $4^2 = 5$ mod $11$
    gap> Legendre( 6, 11 );
    -1        # thus there is no $r$ such that $r^2 = 6$ mod $11$
    gap> Legendre( 3, 35 );
    -1        # thus there is no $r$ such that $r^2 = 3$ mod $35$ 

Previous Up Top Next
Index