In practice, there are two cases of Legendre symbols which can be computed easily, but are not covered by the previous section. In both cases, they involve LS(a, p) with a fixed, and the prime p varying. Let's look back at an earlier example of Legendre symbols of this type.
The value of LS(5, p) depends only on the congruence class of p modulo a specific integer. This is somewhat surprising! In fact, it may not be clear yet that this is the case. Let's compute some Legendre symbols to check it out.
The applet below will display a table, with each line providing the remainder of a modulo n together with the value of LS(a, pi), where pi is the ith prime. The value of i runs from 2 (thus we start with p2 = 3) and ends at B + 1. In the example below, we set a = 5 and n = 3.
Examining the output, we don't see any obvious patterns. Let's try setting n = 5:
This time a pattern does emerge. Upon close inspection, we see that LS(5, p) = 1 when p is congruent to 1 or 4 modulo 5, and LS(5, p) = 1 when p is congruent to 2 or 3 modulo 5.
In the next two subsections, we examine two cases similar to the above illustration. For each, your task is to find a pattern similar to the one we spotted for a = 5.
11.6.1 Computing LS(1, p)
Let p be an odd prime. We want to know when 1 is congruent to a square mod p. As above, use the applet with different values of n to look for patterns. Here's what we get if n = 2.
That may have not been too helpful! Try other values of n until you find a pattern.
Research Question 5
For which odd primes p is LS(1, p) = 1?
Hint: Once you have a good conjecture, consider Euler's Criterion when searching for a proof.
11.6.2 Computing LS(2, p)
Same song, second verse. Use the same approach as above to tackle Research Question 6. By now you should be an expert at using the applet, so we leave all of the entries for you to fill in.
Research Question 6
For which odd primes p is LS(2, p) = 1?
Note: We are primarily looking for a good conjecture for this problem. A proof is fairly difficult.
Section 11.1 | Section 11.2 | Section 11.3 | Section 11.4 | Section 11.5 | Section 11.6
Chapter 11 | DNT Table of Contents
Copyright © 2001 by W. H. Freeman and Company