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,