Residuo Cuadratico

Sean n un numero primo impar y a un numero entero relativamente primo con n,entonces a es un residuo cuadratico de n, sı el mcd(a, n) = 1 y la congruencia tiene solucion.
Podemos deducir que si la congruencia no tiene solucion,entonces se dice que a no es residuo cuadratico de n.

EJEMPLO

Sea n = 11. Entonces para determinar que enteros son residuos cuadraticos de 11, debemos computar los cuadrados de los n´umeros enteros 1, 2, . . . , 10, es decir


Por lo tanto, los residuos cuadraticos son: 1, 3, 4, 5, 9 y los residuos no cuadraticos
son: 2, 6, 7, 8, 10.


CODIGO EN C++

Necesitaremos las siguientes funciones :

alg_euc() (Algoritmo de Euclides, puedes ver el código aqui )

a) Retornar todos los residuos cuadraticos de n

/* funcion que verifica si un elemento esta en el vector*/
bool esta_en(int elemento,vector<int> v)
{
  for(int i=0;i<v.size();i++)
   if(elemento==v.at(i))
     return true;
     
  return false;   
}

/*funcion que retorna todos los residuos cuadraticos de n*/
vector<int> ResiduosCuadraticos(int n)
{
 vector<int> v_rc;
 int mcd,x,a;
 for(int x=1;x<n;x++)
 {
     a=x*x%n;
     if(alg_euc(a,n)==1)
     {
        if(v_rc.size()==0 || !esta_en(a,v_rc))
          v_rc.push_back(a);
     }
 }
 return v_rc;
}

int main(int argc, char *argv[])
{
  vector<int> v=ResiduosCuadraticos(11);
  for(int i=0;i<v.size();i++)
  cout<<v.at(i)<<" ";
  cout<<endl;
    
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

b) Verificar si un numero 'a' es residuo cuadratico de n

bool esResiduoCuadratico(int a,int n)
{
  vector<int> v_rc=ResiduosCuadraticos(n);
  if(esta_en(a,v_rc))
     return true;
  return false; 
}

int main(int argc, char *argv[])
{
    if(esResiduoCuadratico(5,11))
      cout<<"\n SI es Residuo Cuadratico"<<endl;
    
    system("PAUSE");
    return EXIT_SUCCESS;
}