Math 560
Spring, 2006
hw10

Assume in what follows that p and q are odd primes. I will ask you to look for some patterns. There are patterns there to be found - several of them are quite deep. So concentrate on seeing what they are and stating them carefully. When you think you've found one, make a prediction based on it for some relatively large values of p (and q, if necessary) and then check the prediction. John Bussey has kindly provided a web utility that will save you tedious computation. (Maybe he will post the source code there so you can see how his program works.)

  1. "When does D have a square root in Zp?" For each fixed D there is a pattern to be found, so that you can easily figure out whether D has a square root mod p. The answer should be of the form "yes, when p is congruent to x or y or ... modulo M, no when it's congruent to u or v or ... modulo M."

    But note that this pattern does not tell you how to find the square roots (although John's program will).

    1. When does -1 have a square root in Zp? (You should find the answer to this one in your class notes, since Praveen guessed it in class a few weeks ago. Verify it.)

    2. When does 2 have a square root in Zp?

    3. When does 3 have a square root in Zp?

  2. Look for a pattern of patterns. Try to answer the previous problem for more values of D, to see if you can guess the value of M. (You won't find a pattern for the values of x, y, u, v, ... .)

  3. Look for a relationship between answers to the questions

    Does p have a square root in Zq? (yes or no)
    Does q have a square root in Zp? (yes or no)

    Your answer should be of the form "Both questions have the same answer when ...; the questions have opposite answers when ..."

    If you can answer this hard question you are in good company - no one could until Euler did in 1783. And he couldn't prove that the pattern he guessed was right. That needed to wait for Gauss, in 1796.

    Here's a hint: mod 4 is important.