2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

m=28 using the chinese remainder theorem

$\endgroup$
  • 1
    $\begingroup$ Why does CRT lead to 28? $\endgroup$ – Jonah Sinick Nov 1 '12 at 20:07
  • $\begingroup$ @JonahSinick Because you have to check what $n$ is modulo 4 and modulo 7. CRT tell you that that is a question modulo 28. $\endgroup$ – N. S. Nov 2 '12 at 1:13
  • $\begingroup$ Can you explain that further in terms of my latest edit? $\endgroup$ – CodeKingPlusPlus Nov 2 '12 at 2:33
2
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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