Determine the quadratic character of $293 \bmod 379$.

Question

Determine the quadratic character of 293 mod 379.

Did several other problems like this with 3, 5, 60, -1 and 307 all mod 379 but still having a tough time with this problem. I can post up work from these examples if helpful. Any help is appreciated.

So far I have...

(293/379)=(379/293)=(86/293)...

I'm not really sure how to finish this out, any help is appreciated.

Answer 1

$\newcommand{kron}[2]{\left( \frac{#1}{#2} \right)}$

You are trying to determine the Legendre symbol $\kron{293}{379}$. There is a pretty general recipe when trying to compute Legendre symbol $\kron{a}{p}$ when $p$ doesn't divide $a$ and $p$ is an odd prime. The tools available are

1. Explicitly find all the squares mod $p$, or represent $a$ as a square. (This is only worthwhile for small $p$)
2. Use Euler's Criterion to compute $a^{\frac{p-1}{2}} \bmod p$. This is $1$ is $a$ is a square mod $p$ and $-1$ if $a$ is not a square mod $p$.
3. Alter $a$ by adding a multiple of $p$.
4. Factor $a$ into a product of primes $p_i^{k_i}$. Then $\displaystyle \kron{a}{p} = \prod_i \kron{p_i}{p}^{k_i}$, and one can consider each Legendre symbol separately.
5. Use quadratic reciprocity and its supplemental laws. This means that:
   1. When $a$ is an odd prime $q$, you can use $\displaystyle \kron{q}{p} = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\kron{p}{q},$
   2. $\kron{2}{p} = 1$ if $p \equiv \pm 1 \pmod 8$ and $-1$ otherwise,
   3. and $\kron{-1}{p} = 1$ if $p \equiv 1 \pmod 4$ and $-1$ otherwise.

One can always proceed algorithmically by factoring the numerator, using quadratic reciprocity to flip each Legendre symbol, reducing the new numerators mod the denominators, and repeating until the numbers are small enough to analyze by inspection.

Here, $293$ and $379$ are prime. By quadratic reciprocity, $$ \kron{293}{379} = \kron{379}{293}.$$ Reducing mod $293$, this becomes $$ \kron{379}{293} = \kron{86}{293} = \kron{2}{293} \kron{43}{293}.$$ As $293 \equiv 5 \pmod 8$, this becomes $$\kron{2}{293} \kron{43}{293} = - \kron{43}{293}.$$ Applying quadratic reciprocity and reducing mod $43$, this becomes $$- \kron{43}{293} = - \kron{293}{43} = -\kron{35}{43}.$$ One could factor and repeat. But one might also write this as $$-\kron{35}{43} = - \kron{-8}{43} = -\kron{-1}{43} \kron{2}{43}^3.$$ As $43$ is $3 \bmod 4$, we know $\kron{-1}{43} = -1$. And as $43$ is $3 \bmod 8$, we know that $\kron{2}{43} = -1$. So this becomes $$-\kron{-1}{43} \kron{2}{43}^3 = -(-1)(-1)^3 = -1.$$

And so we conclude that $293$ is not a square mod $379$. $\diamondsuit$