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.

To determine a quadratic congruence equation has any solution, we have to evaluate $$\bigg( \dfrac{a}{p} \bigg)$$, So can we apply the algorithm of Jacobi symbol to evaluate this? If yes, what's the easiest way to evaluate this symbol? Let's not take efficiency into account because I don't have a computer in my exam, so I just want to learn the simplest way which I will be able recall it easily during the exam. For example, evaluate $$\bigg( \dfrac{2819}{4177} \bigg)$$

$$(\dfrac{2819}{4177}) = (\dfrac{4177}{2819}) \text{ because } \frac{(2819-1)(4177-1)}{4} = \text{ even } $$ $$= (\dfrac{1358}{2819}) = (\dfrac{2}{2819}) \cdot (\dfrac{679}{2819})$$ $$= (-1) \cdot (\dfrac{679}{2819}) \text{ because } \frac{2819^2 - 1}{8} = \text{ odd }$$ $$= (-1) \cdot (-1) \cdot (\dfrac{2819}{679}) = (\dfrac{2819}{679}) \text{ because } \frac{(m-1)(n-1)}{4} = \text{ odd }$$ $$= (\dfrac{2819}{679}) = (\dfrac{103}{679}) = (-1) \cdot (\dfrac{679}{103}) \text{ because } \frac{(103-1)(679-1)}{4} = \text{ odd }$$ $$= -(\dfrac{61}{103}) = -(\dfrac{103}{61}) \text{ because } \frac{(61-1)(103-1)}{4} = \text{ even }$$ $$= -(\dfrac{42}{61}) = -(\dfrac{2}{61}) \cdot (\dfrac{21}{61}) = -(\dfrac{21}{61}) \text{ because } \frac{61^2 - 1}{8} = \text{ even }$$ $$= -(\dfrac{61}{21}) \text{ because } \frac{(21-1)(61-1)}{4} = \text{ even }$$ $$= -(\dfrac{19}{21}) = -(\dfrac{21}{19}) \text{ because } \frac{(19-1)(21-1)}{4} = \text{ even }$$ $$= -(\dfrac{2}{19}) = (-1) \cdot (-1) = 1 \text{ because } \frac{19^2-1}{8} = \text{ odd }$$.

Since in the book example, the author often skipped many steps, so I just want to make sure that I understand it correctly. Any suggestion and idea would be greatly appreciated.

Thank you,

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

There are two problems. First, you have an error above: $\:(2|61) = -1\:,\:$ not $1$. Second, as I mentioned before when discussing the generalized Euler Criterion:

BEWARE $\ $ The criterion cannot be expressed equivalently as a simple Jacobi symbol calculation. For example we have $\rm(8|15) = 1\ $ but $8$ is not a square (mod $15$).

However, in your example all is well since, after correcting the sign error, the Jacobi symbol evaluates to $-1$ so it correctly identifies nonsquares. But when it evaluates to $1$ (as you had above) it needn't correctly identify squares (except when the denominator is prime, i.e. when it reduces to a Legendre symbol).

share|improve this answer
    
Thank you Bill, so what is the main difference between Jacobi and Legendre? I'm a bit confused now :(. –  Chan Apr 16 '11 at 17:56
1  
@Chan, for $(p|q)$ to be a Legendre symbol, $q$ must be prime. A Legendre symbol is 1 if $p$ is a square mod $q$, $-1$ if it isn't. For $(p|q)$ to be a Jacobi symbol, there is no such restriction on $q$. If the symbol is $-1$, $p$ isn't a square, but if it's 1, you can't say whether $p$ is a square. –  Gerry Myerson Apr 16 '11 at 23:58
    
@Gerry Myerson: Many thanks. So if I want to see if is there a solution for quadratic congruence, then I should stick with Legendre symbol? –  Chan Apr 17 '11 at 4:48
1  
@Chan: You can use the generalized Euler criterion - see the link above (originally the link pointed to the wrong place - I just fixed it). –  Bill Dubuque Apr 17 '11 at 7:04
    
Many thanks, now I found it much easier ;) –  Chan Apr 18 '11 at 4:56
add comment

It looks to me like what you have done is fine. Did you check to see whether 4177 is prime? If it isn't, then Jacobi symbol 1 doesn't guarantee quadratic congruence solvable, e.g., $x^2\equiv2\pmod{15}$ has no solution even though the symbol is 1.

share|improve this answer
    
Thanks. 4177 is actually prime. So like you said, before attempting to evaluate Jacobi symbol, I have to check if $p$ is prime? –  Chan Apr 16 '11 at 6:52
1  
@Chan: You can evaluate Jacobi symbols $\left(\frac{a}{m}\right)$ without caring about whether $m$ is prime. But then, as pointed out in the comment above, if the result is $1$ you cannot conclude that $a$ is a quadratic residue of $m$. (If $m$ is prime, of course you can.) If the Jacobi symbol evaluates to $-1$, however, you can conclude that $a$ is not a quadratic residue of $m$, whether or not $m$ is prime. –  André Nicolas Apr 16 '11 at 12:49
    
@user6312: Thanks a lot. –  Chan Apr 16 '11 at 17:56
add comment

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.