Reference no: EM131557742

1. Find all the solutions to the quadratic equation x^2 = 13mod(493) (493 = 17 · 29), by following these steps:

a. First, use the Legendre symbol (and Quadratic Reciprocity, if necessary) to explain why each of the congruence x^2 = 13mod(17) and x^2 = 13mod(29) has a solution

b. Then, by examination, find the two solutions to each congruence

c. Finally, use the Chinese Remainder Theorem to find all four solutions (remember, you have to give your solutions modulo 493)

2. Use the smallest primitive root mod(13), to find the (three) solutions to the polynomial congruence x^3 = 5mod(13) (you must show the method you use - don't just give the answers)

3. Evaluate the following Legendre symbols - give each step (you can assume all the results about the symbols (±2/p) and (±3/p)
! (if you need them), but no others.

a.(17/101)

b.(-46/17)c.(23/43)

4. Suppose p is an odd prime having a primitive root r

a. Prove r^((p-1)/2)= -1 mod(p)

b. Prove, using a., that if p = 3 mod(4), then ord p(-r) = (p-1)/2 !(and hence - r isn't a primitive root mod p)

c. Prove if p = 1 mod(4), then - r must also be a primitive root mod(p)

5. Consider the two quadratic equations in a and b

a. x^2 + 5x = 12 mod(31)

b. x^2 + 5x = -12 mod(31)

One of them has a solution and one doesn't. Explain why the one that doesn't have a solution, doesn't and the one that does have a solution does - then find the solutions.

6. Use the Quadratic Reciprocity Law to prove: if p is prime (5/p) = 1 if and only if p = 1,9,11, or 19 mod(20) that is, if p is congruent to one of those four numbers. (what are the possible remainders if p is divided by 20?