MA357, Spring 2008
Comments on Problem Set 7

1. For part (a), suppose that p ≡ 3 (mod 4) and that p|(a2+b2). Then a2 ≡ –b2 (mod p). If p doesn't divide b, there exists a number c such that bc ≡ 1 (mod p), and hence (ac)2 ≡ –1 (mod p). Thus, we conclude that –1 is a square (mod p). On the other hand, since p ≡ 3 (mod 4), we know that –1 is not a square (mod p). This is a contradiction, and it came from assuming that p didn't divide b. So b must be a multiple of b, and since a2 ≡ –b2 (mod p), so must a. So we've shown that p|a and p|b.

Part (b) is actually easier. Since p ≡ 1 (mod 4), we know –1 is a square (mod p), so there exists a number x such that x2 ≡ –1 (mod p). Clearly x can't be divisible by p. But the congruence translates to p|(x2+1), and so a=x, b=1 gives the two integers we want.

2. These should all have been easy. GP says:

? kronecker(85,101)
%1 = 1
? kronecker(29,541)
%2 = -1
? kronecker(101,1987)
%3 = 1
? kronecker(31706,43789)
%4 = -1

3. The point is that the quadratic formula works fine (mod p), as long as p is not 2 and we interpret everything in a (mod p) sense, i.e., the square root is taken in the (mod p) world and dividing by 2a is multiplying by its inverse (mod p).

To decide whether a quadratic has solutions, then, we look at its discriminant, which in this case is (–3)2+4=13. This is certainly not zero (mod 31957), so the quadratic will have two solutions if 13 is a square (mod 31957) and no solutions if not. GP says

? kronecker(13,31957)
%5 = 1

Hence 13 is a square and the equation has two roots.

Are you curious about what the roots are? The solutions to x2 ≡ 13 (mod 31957) are x ≡ 14243 and x ≡ 17714. The inverse of 2 is 15978. So the solutions are

x1 ≡ (3 + 14243)*15978 ≡ 7123 (mod 31957)
and
x2 ≡ (3 + 17714)*15978 ≡ 24837 (mod 31957)

I'll let you check that those do work!

4. To say p divides A2 – 5 amounts to saying A2 ≡ 5 (mod p). Hence 5 is a square (mod p), so the Legendre symbol (5/p) is equal to 1. But (since p is not 2 or 5) by quadratic reciprocity (5/p) = (p/5), so we want to know whether p is a square mod 5. Climbing mountains, we see that the only squares mod 5 are 1 and 4. So p must be congruent to either 1 or 4 (mod 5).

5. Just check cases. For example, if p = 8k + 3, then p2 = 64k2 + 48k + 9. So p2 – 1 = 8(8k2 + 6k + 1), and we see that (p2 – 1)/8 is odd, which gives the correct value of the Legendre symbol. The other cases are identical.

6. Should all be routine. Notice that:

The answers are: (a) no solutions, (b) eight solutions, (c) no solutions, (d) two solutions, (e) two solutions, (f) no solutions.

7. As noted in class, the correct statement is that any prime divisor of n2–n+1 is either equal to 3 or congruent to 1 modulo 6.

First of all, since n2–n is even, n2–n+1 can't be divisible by 2. It can be divisible by 3, if n=2 for example. (So it remains to look only at primes different from 2 or 3.

OK, now the idea is to complete the square and then use the same method as in problem 4. Since p can't be equal to 2, it makes no difference if we multiply everything by 4. That allows us to complete the square without introducing denominators:

4(n2 – n + 1) = 4n2 – 4n + 4 = (2n–1)2 + 3
So if p divides this, we'll have (2n – 1)2 ≡ –3 (mod p), that is, –3 will be a square (mod p). [This is where p=3 slips in: –3=0 (mod 3), which is certainly a square.] Since we're assuming p is not 3, we can use the standard quadratic reciprocity yoga:

(–3/p) = (–1/p)(3/p) = (–1)(p–1)/2(–1)(p–1)/2(p/3) = (p/3)

and (p/3)=1 if and only if p ≡ 1 (mod 3). Finally, since p is odd, if p=3k+1, then k must be even, so p=6n+1, so p ≡ 1 (mod 6).


Fernando Q. Gouvêa ---- fqgouvea@colby.edu
Last modified: Fri May 02 14:19:41 Eastern Daylight Time 2008