Euler's Criterion using BigIntegers given RSA n=p*q

Question

I'm trying to find if (a/p) is a quadratic residue using Euler's criterion

I'm aware that using this method only 3 answers should exist: 1, 0, or -1

However, when I implemented this in Java using BigIntegers I'm getting a different result. When I run the code below, my legendreSymbol equals 104192021379649097919980 which cannot be right. I've looked at many tutorials and all of the express Euler's criterion as a^((n-1)/2) mod n which is exactly how I'm calculating it in my code.

I tried to look for any similar implementations online but I can't find any at all.

I tired to factorize n into p and q and tried using Euler's criterion on those values but some of those results are still not either 0, 1 or -1

public static void main(String args[]) {
        BigInteger p = new BigInteger("329398839493");
        BigInteger q = new BigInteger("500356734809");
        BigInteger n = p.multiply(q);

        
        BigInteger vote = new BigInteger("131187442706502465465362");

        
        if(isQuadraticResidue(vote, n)) System.out.println("Vote 1 = QR");
        else System.out.println("Vote 1 = QNR");
    }
    
    //Quadratic Reciprocity Eulers Criterion
    public static boolean isQuadraticResidue(BigInteger num, BigInteger n) {
        //https://en.wikipedia.org/wiki/Legendre_symbol
        //if the legendreSymbol = 1 then the number is a quadratic residue
        
        BigInteger exponent = n.subtract(BigInteger.ONE).divide(BigInteger.TWO);
        BigInteger legendreSymbol = num.modPow(exponent, n);
        System.out.println(legendreSymbol);

        return legendreSymbol.equals(BigInteger.ONE);
    }

Answer 1

For Euler's Criterion as you stated a^((n-1)/2) mod n, n must be an odd prime and a coprime to n. In your code, you passed in p*q for n which is obviously not an odd prime