Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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|improve this answer

m=28 using the chinese remainder theorem

share|improve this answer
1  
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 Answer

 
discard

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.