Thread: Legendre Symbol

Evaluate the Legendre symbol below:

(461/773)

Show all work/theorems used to compute it.

Originally Posted by math19091

Evaluate the Legendre symbol below:

(461/773)

Show all work/theorems used to compute it.

Note 461 = 1 (mod 4).

Quadradic Reciprocity:
(773/461)

= (312/461) = (8/461)*(3/461)*(13/461)
=(2/461)*(3/461)*(13/461)

Theorem 2 (2/p)=1 iff p=1,7(mod 8) for odd primes p.

Use theorem,
(-1)*(3/461)*(13/461)

Theorem 1 (3/p)=1 iff p=1,11(mod 12) for odd primes p.

Use theorem,
(-1)(-1)(13/461)=(13/461)

Note that p=1(mod 4).
Quadradic Reciprocity:
(461/13) = (6/13) = (2/13)*(3/13)

Use Theorem 1 and Theorem 2:
(-1)(+1)=-1.

Thus the Legendre Symbol is equal to -1.

Originally Posted by ThePerfectHacker

Note 461 = 1 (mod 4).

Quadradic Reciprocity:
(773/461)

= (312/461) = (8/461)*(3/461)*(13/461)
=(2/461)*(3/461)*(13/461)

Theorem 2 (2/p)=1 iff p=1,7(mod 8) for odd primes p.

Use theorem,
(-1)*(3/461)*(13/461)

Theorem 1 (3/p)=1 iff p=1,11(mod 12) for odd primes p.

Use theorem,
(-1)(-1)(13/461)=(13/461)

Note that p=1(mod 4).
Quadradic Reciprocity:
(461/13) = (6/13) = (2/13)*(3/13)

Use Theorem 1 and Theorem 2:
(-1)(+1)=-1.

Thus the Legendre Symbol is equal to -1.

Thanks TPH. Question: how did you do this part

(773/461)

= (312/461) = (8/461)*(3/461)*(13/461)

I don't see how you go from (773/461) to (312/461)

Originally Posted by math19091

Thanks TPH. Question: how did you do this part

(773/461)

= (312/461) = (8/461)*(3/461)*(13/461)

I don't see how you go from (773/461) to (312/461)

i believe he made the observation that 773 is congruent to 312 mod 461, so he can use either one to find the symbol, working with smaller numbers is always better

i think one of his theorems said he could do such a manuevor

Originally Posted by math19091

Thanks TPH. Question: how did you do this part

(773/461)

= (312/461) = (8/461)*(3/461)*(13/461)

I don't see how you go from (773/461) to (312/461)

I was assuming you know the fundamental properties of the Legendre symbol.

Theorem: Let p be an odd prime and a and b be two integers such that gcd(a,p)=gcd(b,p)=1. If a = b (mod p) then (a/p)=(b/p).

Thus, I just reduced the Legendre symbol by modular arithmetic.