# Modular arithmetic, congruence classes and the jacobi symbol

Find a modulus $m$ and a finite list of congruence classes $a_1, ..., a_r \mod m$ such that $(\frac{7}{n}) = 1 \iff n \equiv a_i \mod m$ for some $i = 1$ to $r$.

Let me know if I am on the right track or give me some hints please.

Here is what I have so far: $\rightarrow$

Case 1: $n \equiv 1 \mod 4 \implies (\frac{7}{n}) = (\frac{n}{7}) = 1$

Thus the values for $n$ which $n$ is a quadratic residue $\mod 7$ are: $\{1, 2, 4\}$

Case 2: $n \equiv 3 \mod 4 \implies (\frac{7}{n}) = -(\frac{n}{7}) = 1$

Hence the values for which $n$ is a non-quadratic residue $\mod 7$ are: $\{3, 5, 6\}$

EDIT

case 1: $n \equiv 1 \mod 4$ and $n \equiv 4 \mod 7$ Now by the CRT we should be able able to find $n$.

Do: $n = 7 \cdot -1 \cdot 1 + 4\cdot 4 \cdot 2 = 25$. Checking we see $25 \equiv 1 \mod 4$ and $25 \equiv 4 \mod 7$ but I want $n \equiv$ either $1 \mod 28$ or $4 \mod 28$

So, what went wrong?

-

@JonahSinick Because you have to check what $n$ is modulo 4 and modulo 7. CRT tell you that that is a question modulo 28. –  N. S. Nov 2 '12 at 1:13
Your task is not to find $n$ and $m$, but rather just $m$ such that knowing $n\bmod m$ is enough to deduce the value of $(\frac7n)$. You've already shown that knowing $n\bmod 4$ and $n\bmod 7$ is enoouhg. Can you show that knowing $n\bmod 28$ is sufficient as well?