1
$\begingroup$

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,

2 Answers 2

1

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).

  • 0
    Many thanks, now I found it much easier ;)2011-04-18
2

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.

  • 0
    @user6312: Thanks$a$lot.2011-04-16