Jacobi and Legendre Symbol

Question

I'm trying to calculate the value of $k=(\frac{5}{645784635653487634537})$, that is either: $1,-1$ or $0$. (Jacobi/Legendre symbol)

Since $\gcd(5,645784635653487634537)=1$, we know that $k$ is either $1$ or $-1$.

Now, how can I calculate the value of $k$ with such big denominator? Congruences are impossible to do with such values.

Answer 1

Using the $6$th property of Jacobi symbol here : WIKI PAGE. You don't need to prove that $645784635653487634537$ is prime. You just need to notice that $645784635653487634537$ and $5$ are coprime and odd. Since $5$ is prime you only need to prove that $5$ does not divide $645784635653487634537$ which is obvious because this big number does not end with $5$.

We can conclude the same way than the other answer.

Answer 2

645784635653487634537 is prime, so we can apply the Quadratic reciprocity law:

$k\cdot(\frac{645784635653487634537}{5}) = -1^{\frac{5 - 1}{2} \cdot \frac{645784635653487634537 - 1}{2}}=1$.

Now $(\frac{645784635653487634537}{5}) = (\frac{2}{5}) = -1$, so $k=-1$.