Simbolo de Legendre

Sean p un numero primo e impar y a un numero entero no divisible por p. Entonces el sımbolo de Legendre se define por :



CODIGO EN C++

Necesitaremos las siguientes funciones :

esResiduoCuadratico(int a,int n) (Algoritmo que verifica si un numero a es residuo cuadratico de n, puedes ver el código aqui )

int Legendre(int a , int p)
{
    if(esResiduoCuadratico(a,p))
      return 1;
    return -1;     
}