Legendre

Returns the Legendre symbol. Let pLaTeXp be an odd prime. An integer aLaTeXa is a quadratic residue modulo pLaTeXp if it is congruent to a perfect square modulo pLaTeXp, and is a quadratic nonresidue modulo pLaTeXp otherwise. The Legendre symbol is a function of aLaTeXa and pLaTeXp defined as

ap={leftleft-1  if  a0 (mod p) and there is no integer x: ax2italic (mod p),  0   if  a0 (mod p),  1   if  a0 (mod p) and for some integer x: ax2 (mod p).

Syntax

legendre(Integer, Integer)

Description

Given an integer aLaTeXa and an odd prime pLaTeXp, computes the Legendre symbol ap.

arithmetic.legendre.calc.png