Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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\}$


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?

share|cite|improve this question

m=28 using the chinese remainder theorem

share|cite|improve this answer
Why does CRT lead to 28? – Jonah Sinick Nov 1 '12 at 20:07
@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
Can you explain that further in terms of my latest edit? – CodeKingPlusPlus Nov 2 '12 at 2:33

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.