compute each of the following Legendre symbols: a) (60/71) and b) (127/443)?

Answer 1

Well, let' s do (60/71) first.
60 = 15*4 and 4 is a square,
so (60/71) = (15/71) = (3/71)(5/71).
This follows from the multiplicative property of
the Legendre symbol
Now use the reciprocity law:
Since 3 and 71 are both congruent to 3 mod 4
(3/71) = -(71/3) = -(2/3) = -(-1) = 1.
Also 5 = 1(mod 4),
so (71/5) = (5/71) = (1/71) = 1.
So (60/71) = 1 and
x² = 60(mod 71) is solvable.

b). (127/443) = -(443/127) because
127 and 443 are congruent to 3(mod 4).
Next, (443/127) = (62/127)
since 443 = 62(mod 127).
Also (62/127) = (2/127)(31/127)
and (2/127) = 1 because 127 = 7(mod 8).
So it boils down to evaluating
(31/127) = -(127/31) (same reasons as above)
= -(3/31) = (31/3) = 1.
So (127/443) = -1
and x² = 127(mod 443)
is not solvable.
Incidentally, I checked both these results by
Euler's criterion:
a^(p-1)/2 = 1(mod p) if a is a quadratic
residue mod p and -1 otherwise and
both checked out fine. I used PARI to
do this.
Finally, we can find the solutions to x² = 60(mod 71)
quite easily, since 71 = 3(mod 4).
Let's solve x² = 15(mod 71) and double the
result mod 71.
Theorem: If p = 3(mod 4) and x² = a(mod p) (*)
is solvable then x = ±a^(p+1)/4 solves (*).
Proof: If we square ±a^(p+1)/4 we get
x² = a^(p+1)/2 = a^(p-1)/2 *a^2 /2= a(mod p).
So x² = 15(mod 71) has the solution
±15^18 = ±50(mod 71)
and thus the solution of
x² = 60(mod 71) is x = ±100 = ±29(mod 71).
Hope my explanations are OK for you!

Answer 2

NERD!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!