This is the only chapter in my book that presents results without proof. The theorems are simply too beautiful to omit, even if the proofs are beyond my ken.
Quadratic reciprocity states that, for odd primes p and q, p is a square mod q iff q is a square mod p, unless p and q are 3 mod 4, in which case p is a square mod q iff q is not a square mod p. The legendre symbol [p\q] is concise notation for "p is a square mod q", whence reciprocity can be written: [p\q] = [q\p] unless p and q are 3 mod 4, whence [p\q] ≠ [q\p]. Separate rules deal with [2\q] and [-1\q]. All this is familiar territory, but we want to extend this concept in two different ways.
Let R be a pid containing the integers. R contains prime elements, and like the integers, R mod a prime element is a finite field. The size of this finite field is determined by the residue degree of q. As with any finite field of odd characteristic, Half the entries are squares and half are nonsquares. If p and q are prime elements of R, [p\q] is true if p is a square mod q, and false if p is not a square mod q. Does R have reciprocity rules similar to the integers? Often it does, though the relationship is more complicated.
Why stop at squares? Is p a cube or a fourth power etc mod q? We don't want a yes or know answer here, we want to take the discrete log of p in the finite field R/q, and, in the case of cubic reciprocity, extract its remainder mod 3. If b is a primitive element in the finite field, then p is either a cube, or b times a cube, or b2 times a cube. There are three possible values for [p\q]. 0 1 and 2 is one convention, representing a cube, b times a cube, or b2 times a cube. There are 4 possible values for quartic reciprocity as per 1, b, b2, and b3 times a fourth power, and so on. Yet this is problematic over the integers, because there is no preferred primitive element b. As you switch from [p\q] to [q\p], you have to select a primitive element in each case. It might not be possible to select the same primitive element. Do we just select one at random? That would surely destroy any reciprocity that might exist. To fix this conundrum, cubic reciprocity is only defined on rings that contain the cube roots of 1. Let y be the first cube root of 1 traveling counterclockwise around the unit circle, and map this canonically to an element in the finite field R/q. If the order of this field is l, then p raised to the (l-1)/3 will be 1 whenever p is a cube in this field. If p is not a cube, then p raised to the (l-1)/3 is a nontrivial cube root of 1 that coincides with the image of y, or of y2. The fixed element y in R anchors the function [p\q] for any prime q in R. This is the hook we can hang our hat on. If some form of reciprocity exists it will reveal itself, because each legendre symbol is based on the fixed element y. Quadratic reciprocity in the integers did this implicitly by fixing the element -1. This is all we need for squares versus nonsquares. A square raised to the (l-1)/2 is 1, while a nonsquare raised to the (l-1)/2 is -1. Everything is based on -1, the square root of 1. In the same way, cubic reciprocity requires the cube roots of 1, quartic reciprocity requires the fourth roots of 1, and so on. That is why this chapter follows the chapter on cyclotomic number fields.
Let R be the ring of gaussian integers, i.e. the integers with i adjoined. We know how primes split in this ring. An integer prime p is totally ramified if p = 2, inert if p = 3 mod 4, and splits into two distinct primes if p = 1 mod 4. R is a pid, so prime elements and prime ideals correspond.
Mod out by a gaussian prime v that lies over the integer p. The size of the resulting finite field is p2 if p is inert, or p if p splits. This is the norm of v, or the norm of the ideal generated by v, and it is denoted |v|.
Within any finite field of odd characteristic, half the nonzero entries are squares and half are nonsquares. Thus the legendre symbol [a\p] is well defined for any complex prime p lying over an odd prime in the integers, And it is equivalent to a raised to the (|p|-1)/2. The result is 1 if a is a square mod p, and -1 if a is a nonsquare mod p.
Using the square nonsquare criteria, i.e. the parity of the discrete log expressed as 1 or -1, [ab\p] = [a\p] × [b\p]. At the same time, ab to the (|p|-1)/2 = a to the (|p|-1)/2 times b to the (|p|-1)/2, so we are consistent.
Whether based on an inert prime or a splitting prime, the order of the residue field is always 1 mod 4, hence -1 is always a square. It's the square of i of course. All good, but when is i a square? i is a square iff the order of the field is 1 mod 8. This is the case when q is real, 3 mod 4, giving a field of size 1 mod 8. So let p = a+bi. Since a2+b2 = 1 mod 4, exactly one of a or b is even. Say it is b. a2 becomes 1 mod 8, and i becomes a square iff b is 0 mod 4. The same rule covers the real prime q, since the imaginary component is 0.
Write 2 = (1+i)2*i3. Thus [2\p] = [i\p]. We know when i is a square, as per the previous paragraph. That takes care of -1 and 2, leaving the odd primes.
The residue field is R mod the principal ideal generated by p. Thus p could be replaced with any of its associates. Evaluate 12 mod 7 and you get the same thing as 12 mod -7. In the gaussian world, multiply p by i, and the residue field is the same, and each legendre symbol comes out the same. So use whichever associate you like downstairs. In particular, adjust a complex denominator so that the imaginary component is even. (In the case of a real inert prime, the imaginary component is 0, which is even.)
Let l = a+bi, and let m = c+di, where b and d are even. Assume l and m are primes. Quadratic reciprocity asserts [l\m] = [m\l]. As mentioned above, you can multiply the bottom by i to make d even. You can do the same to the top, but if you do, you must adjust the result according to [i\m].
As above, let l = a+bi, and let q be a real prime that is 3 mod 4. Once again [l\q] = [q\l]. This is a special case of the above, since the imaginary component of q is already even.
Finally, [1+i\m] = [2\c+d], where the right hand side is treated as a jacobi symbol over the integers. Since c+d is odd there is no trouble here. I'm not going to prove this in general, but consider a real prime, whence c is 3 mod 4 and d is 0. The jacobi symbol [2\q] over the integers is 1 if q = 7 mod 8, or -1 if q = 3 mod 8. Square q to get a field whose order is q2. Since 2 is an integer, its discrete log is divisible by q+1. Thus 2 is a fourth power. Since q2 = 1 mod 8, i is a square, but look mod 16 and i is a fourth power only if q = 7 mod 8. Thus 2i is always a square, but it is a fourth power iff q = 7 mod 8. Take the square root and 1+i is a square iff q = 7 mod 8, which is what we want.
Like the integers, the gaussian legendre symbol generalizes to a jacobi symbol having the same reciprocity rules. Define the jacobi symbol first, then prove the reciprocity rules, without having to factor top and bottom.
The jacobi symbol [a\n] is, by definition, the product of [a\q] over all primes q dividing n, including multiplicities. Since n factors uniquely, this is well defined.
Verify that [ab\n] = [a\n][b\n]. Then use this to show [a\n] is the product of [p\q] over all primes p in a and all primes q in n, including multiplicities. But there's a catch - the associates of the primes of a matter. Actually they mattered before, in the integers, we just didn't worry too much about it. If the top is 15, and you factor it into -3 times -5, instead of 3 times 5, then you have to evaluate the jacobi symbols with negative numbers on top. Pull -1 out of each negative factor and you have an even or odd number of -1's, determined by the sign of a. This evaluates to 1 or [-1\n] respectively, and is strictly a function of a, regardless of how you choose to factor it. In the same way, the factors of a can have various powers of i attached to them, but the number of factors of i mod 4 depends on the quadrant that contains a. Write a as the product of primes in standard form, with the imaginary components even, and you might have to adjust the result by [i\n]. Once again this depends on a and not the factorization.
Are the reciprocity rules still valid? Consider [i\n]. The real primes of n don't change anything, so pull them out. We now have a product of complex primes where the second component of each is even. Expand (a+bi) * (c+di), where b or d is 0 or 2 mod 4. The product has an even imaginary term that is 0 mod 4 iff b and d agree mod 4. Thus we can simply look at the product and get the right answer. Do this for the product of all the primes in n. Thus [i\n] is determined by the value of the second component of n mod 4, just as it was when n was prime. There is no need to factor n.
Perform the same analysis for [1+i\n]. Let a b c and d take on all their values mod 8. That will determine the residue class of 2, and the jacobi symbol with 2 on top. There are 256 possibilities, and miraculously, it all works out. Thus we can evaluate [1+i\n] without factoring n.
Now we're ready to flip. Each symbol [p\q] retains its value when flipped, and [a\n] = [n\a]. That completes the proof.
Use a gcd style algorithm, like we did with the integers, to evaluate the jacobi symbol [a\n] without having to factor a or n. Since R is a euclidean domain, there is no trouble here.
Since the gaussian integers contain the fourth roots of 1, we can consider quartic reciprocity, originally called biquadratic reciprocity. The order of the residue field of any odd prime is 1 mod 4, hence the nonzero elements of this field can be fourth powers, squares, or nonsquares. Raise such an element to the (|p|-1)/4 and get a fourth root of 1. This is canonically equal to the image of 1, i, -1, or -i. This is the result of the legendre symbol [a\p], or if you prefer, 0 1 2 or 3 for 1, i, -1, and -i. Sometimes the multiplicative notation is convenient, and sometimes the additive notation is convenient.
If you have implemented quartic reciprocity, then you have quadratic reciprocity for free. Evaluate [a\p], and if the result is 1 or -1 then a is a square mod p. If the result is i or -i then a is not a square mod p.
Start with [i\p], which depends on |p| mod 16. We know |p|-1 is divisible by 4. If |p|-1 is not divisible by 8, i.e. |p| is 5 or 13 mod 16, then 1 has no eighth root, and i is not a square. If |p| = 9 mod 8 then i is a square, and if p = 1 mod 16 then i is a fourth power. Turning to the implementation / definition of [i\p], raise i to the (|p|-1)/4. Thus (|p|-1)/4, mod 4, equals [i\p] in additive notation.
Anticipating the jacobi symbol, we would like [i\n] to follow the same mod 16 rule. Multiply 1 5 9 or 13 mod 16 by 1 5 9 or 13 mod 16, (16 combinations), then subtract 1, divide by 4, and look at the result mod 4. You will find the sum of the characters of the two factors. Do this for all the factors of n, and [i\n] can be computed using the mod 16 rule without factoring n.
A gaussian number is even if its norm is even, and odd if its norm is odd. The only even prime is 1+i, and a number is even iff it is divisible by 1+i. As a grid in the complex plane, an even number is surrounded by four odd numbers, and an odd number is surrounded by 4 even numbers, somewhat like a checkerboard.
Let an odd number be primary if it is 1 mod 2+2i. Build a base cell above the x axis, anchored at the origin. This is a square tilted 45 degrees, inside a larger square of size 4. The odd numbers inside are i, 3i, 1+2i, and -1+2i. These correspond to the 4 units around the origin. Thus every odd number has exactly one associate that is primary. A real prime q, for instance, is never primary, since it is 3 mod 4, but -q does the trick, and the result is 1 mod 4.
With quadratic reciprocity we wanted the imaginary component to be even. That was the primary associate, though we didn't call it that. Quartic takes one more step: b is even and a = b+1 mod 4.
The product of primary numbers is primary, thanks to modular mathematics, and the conjugate of a primary number is primary. A composite primary number can be uniquely factored into primary primes, since the product of those primes is primary.
Look within the larger 4 by 4 square, from -2 to 2 and from 0 to 4i. There are two instances of a primary number, 1 and -1+2i. Only the first is 1 mod 4. This will play a role in reciprocity, as we'll see below.
Reduce a number mod 4, i.e. reduce each component mod 4. a+bi is primary if a = 1 and b = 0 mod 4, or a = 3 and b = 2 mod 4. Again, the former is 1 mod 4.
If p and q are primary primes, and either is 1 mod 4, then [p\q] = [q\p]. If both are 3+2i mod 4, then [p\q] = -1 times [q\p]. This will remind you of integer quadratic reciprocity.
Let's illustrate with the primes -1+2i and 3+2i, lying over 5 and 13 respectively. These are primary but not 1 mod 4. Pull 3+2i back to -1 in the base cell spanned by -1+2i. Raise this to the (5-1)/4 and get -1. Thus [3+2i\-1+2i] = -1. On the other hand, -1+2i is the same as -4 mod 3+2i. Raise this to the (13-1)/4 and get -64, or 1 mod 13. -1 times -1 = 1, so we're good.
Look at the jacobi symbol with a composite number n below. If the top is not 1 mod 4, and we intend to flip, then each prime below that is not 1 mod 4 multiplies the result by -1. The net effect is -1 iff there are an odd number of primes that are not 1 mod 4, iff n is not 1 mod 4. Once again we can use the reciprocity rules without factoring n.
If i is upstairs, and a primary number a+bi is downstairs, then we are interested in a2+b2 mod 16, as discussed earlier. If b is 0 mod 4 then b2 drops out. Consider a = 1 or 5 mod 8. These lead to 1 or 9 mod 16. Thus a character of 1 or -1. When b = 2 mod 4, b2 becomes 4 mod 16. This time a is 3 or 7 mod 8, and a2 is 9 or 1 mod 16. The formula that works is i to the -(a-1)/2.
Finally, [1+i\p] = i to the (a-b-1-b2)/4.
Let R be the eisenstein integers Z[w], where w is the cube root of 1. The sixth root of 1 comes rolling in as w+1. R is a ufd, so there is no trouble.
Remember that 3 is ramified, primes that are 2 mod 3 are inert, and primes that are 1 mod 3 split. In particular, 2 is inert, and all primes other than 2 have odd norm and are considered odd. 1-w generates the prime lying over 3, and (1-w)2 = -3w, which is an associate of 3.
To evaluate [2\p], place the integer 2 in a finite field of order |p|. The answer is [2\|p|], using integer and finite field residues.
Recall that an odd gaussian number was primary, for purposes of quadratic reciprocity, if it was 1 mod 2, and primary for quartic if it was 1 mod 2+2i. An eisenstein number coprime to 2 and 3 is primary if it is 1 mod 2-2w. By the chinese remainder theorem, this is 1 mod 2 and 1 mod 1-w. Look at the rhombus spanned by 2 and 2w, i.e. the residue field mod 2. It contains 0 and the first three units around the circle. Looking mod 1-w, the result is 0 or ±1. The first three units around are left alone, or negated, as need be, to become 1 mod 1-w. Therefore exactly one associate of any number beyond 3 is primary. Here are the first few conjugate prime pairs in primary form.
7 -3-2w
7 -1+2w
13 3+4w
13 -1-4w
19 3-2w
19 5+2w
31 -5-6w
31 1+6w
37 -3+4w
37 -7-4w
43 7+6w
43 1-6w
The product of primary numbers is primary, thanks to modular mathematics, and the conjugate of a primary number is primary. A composite primary number can be uniquely factored into primary primes, since the product of those primes is primary.
Let p be a real prime that is 2 mod 3, thus inert. What is [1-w\p]? Assume p = 1 mod 4. By reciprocity, 3 is not a square mod p. However, in the field of order p2 every integer has a discrete log divisible by p+1. In particular, a primitive element b mod p has discrete log p+1. b to an odd power is 3. Thus the discrete log of 3 is 2 mod 4. 3 is a square in the residue field but not a fourth power. Since the field has order 1 mod 8, -1 is a fourth power. The field has order 1 mod 12, hence it contains a twelfth root of 1, and w is a fourth power. -3w is a square but not a fourth power. (1-w)2 = -3w, hence 1-w cannot be a square. On the other hand, let p = 3 mod 4 and 3 is a fourth power in the field of order p2 (as is every other integer), and w is a fourth power, and -1 is a fourth power, hence 1-w is a square. In summary, 1-w is a square mod p iff p = 3 mod 4.
To make p primary, negate it, so that it is a negative number. Now [1-w\p] is 1 for 1 mod 4 and -1 for 3 mod 4.
Let p = a+bw be an eisenstein prime in primary form. Write 1-w + kp = n, carrying 1-w to an equivalent integer n. 1-w is a square iff n is a square mod |p|. Conjugate, and 1-w2 + kp = n. The conjugate of 1-w over the conjugate prime has the same residue. Yet 1-w times the unit 1+w is the conjugate 1-w2. If the sixth root of 1 is itself a square, i.e. if there is a twelfth root of 1, then the two residues agree. In other words, [1-w\p] = [1-w\p] iff |p| = 1 mod 4.
The formula for [1-w\p] cannot be a function of norm, or the real component of p, as this does not change with conjugation. Since b is even, a cannot be even, else p is divisible by 2. 1-w is a square mod p iff a+b is 1 mod 4. This also works if p is a real prime (b = 0), as shown above.
The sixth root of 1 is a square iff there is a twelfth root of 1, iff |p| = 1 mod 4.
If p and q are primary primes beyond 3, then [p\q] = [q\p], unless |p| and |q| are both 3 mod 4, whence [p\q] ≠ [q\p]. This will remind you of integer quadratic reciprocity.
Consider -1+2w lying over 7, and 3-2w lying over 19. These are both primary, with norms that are 3 mod 4. Add the first to the second, giving 2, which is a square mod 7. Add the second to the first, giving 2, which is not a square mod 19.
There is no trouble extending these 1 mod 4 rules to composite numbers for the jacobi symbol.
Cubic reciprocity requires the cube roots of 1, thus R is at least the eisenstein integers. Assume R is Z[w], as described in the previous section.
A number not divisible by 1-w is primary if it is 1 mod 3. Look at the parallelogram spanned by 3 and 3w. Of the 9 points inside, 3 are divisible by 1-w. These are 0, 1+2w, and 2+w. The remaining 6 correspond to the 6 units. 1, w, and 1+w represent themselves, 2 and 2w represent -1 and -w, and 2+2w represents -1-w, which is the same as w2. Thus every number coprime to 3 has exactly one associate that is primary.
The product of primary numbers is primary, and the conjugate of a primary number is primary. A composite primary number can be uniquely factored into primary primes, since the product of those primes is primary.
The key result is that [p\q] = [q\p] when p and q are primary primes apart from 3. Remember that the legendre symbol generates a cube root of 1, rather than +1 or -1.
w is a cube iff there is a ninth root of 1, iff the norm of p is 1 mod 9. You can see this by raising w to the (|p|-1)/3. The result is (|p|-1)/3, mod 3.
Raise 1+w, the sixth root of 1, to the (|p|-1)/3 for its cubic character. Assuming p is not 2, the norm is oddd, and the exponent is even. Instead raise w to half the exponent. The result is (|p|-1)/6, mod 3.
As a special case, look at [w\2]. The residue field has order 4, thus any element is raised to the 3/3, which is 1. 1 and w are their own characters, and 1+w is the same as w2 in this field.
Finally we have the prime lying over 3. Let p be a primary prime of the form a+bw, hence a is 1 mod 3. [1-w\p] = w to the (a-1)/3.
Generalize this to the jacobi symbol, and cubic reciprocity is complete.
Combine this with quadratic reciprocity to build legendre and jacobi symbols that crank out sixth roots of 1. Using additive notation, [x\p]6 = 2×[x\p]3 + 3×[x\p]2. In general, reciprocity can be handled prime power by prime power. If you solve cubic and quartic reciprocity for cyclo 12, then these characters can be combined to give reciprocity of order 12.
If R contains the fifth roots of 1, the quintic legendre symbol [x\p] returns one of the fifth roots of 1, or a number from 0 to 4 in additive notation. This can be combined with quadratic reciprocity to produce tenth roots of 1.
There is a new wrinkle here, not seen before. There are units beyond the roots of 1. In particular, you must describe [f\p], where f is the fundamental unit, as well as [w\p], [1-w\p], and reciprocity for [p\q] and [q\p]. I don't have formulas for any of these, but I did develop some software with table driven formulas that seems to work. One set of routines uses the gcd algorithm and the reciprocity rules to compute the jacobi symbol, while another set of routines finds the primes over p and computes the residues directly via exponentiation. Then the results can be compared. You can view the program if you dare, but it is not commented, nor is it terribly well designed. It was just a spare time project circa 2012. Other programs look at quartic reciprocity over cyclo 4 and cyclo 8. These rings are all ufds, so there is no trouble describing a jacobi symbol as a product of legendre symbols over primes.
Let S be a ring extension of R, and let R have the l roots of 1, so that the l order jacobi symbol makes sense in R or in S. Let w be the first nontrivial root of 1, so that wl = 1. Let P be a prime ideal in R. For any x in S, [x\P] with respect to S = [|x|\P] with respect to R. Here |x| is the norm of x in the ring extension S/R. If S/R is not galois then the norm is the product of the images of x in the complex plane, i.e. what x would do in the normal closure of S. Thus |x| winds up in R, and the second jacobi symbol makes sense.
As a warm up, let S/R be a quadratic extension, adjoining q the square root of something in R. The galois group has order 2, mapping q to -q. Let P be prime in R, with residue field having size o. Either P splits into P0*P1 or P is inert. Consider the case of P = P0*P1. S/P0 is a field of size o. The character is x to the (o-1)/l. This is evaluated mod P0, and then mod P1, and the results are multiplied together. Let e = (o-1)/l. Write xe = p0 + wa, where a is [x\P0]. Then write xe = p1 + wb, where b is [x\P1]. (p0 is a member of P0 and p1 is a member of P1.) [x\P] is now a+b. Conjugate the second equation and the conjugate of x, raised to the e, is p0 + wb. (Note that w is part of R, and is fixed by conjugation.) Multiply the two equations and |x|e = p0 + wa+b. Since |x| and w both lie in R, we can restrict P0 to R, giving P. Raising |x| to the e, and reducing mod P, gives the right answer.
[2+i\101], as a quadratic jacobi symbol over the gaussian integers, equals [5\101] as a legendre symbol over the integers.
Next let P be inert, giving a field of order o2. [x\P] is now x to the (o2-1)/l. Remember that l divides o-1. Let z generate the larger field as a primitive element, and let conjugation map z to zo. This is the only nontrivial conjugation in a finite field extension of dimension 2. Group z and zo together. That gives zo+1. This is |z|, and it is raised to the (o2-1)/l over (o+1), which is (o-1)/l. This reproduces the jacobi symbol downstairs. We have equality, whether P splits or not.
[2+i\103], as a jacobi symbol over the gaussian integers, equals [5\103] as a legendre symbol over the integers.
Assuming S/R is galois, the generalization to a flat split is clear. Let S/R have dimension d, and let P split into d primes. This leads to an equation like xe = p3 + w to the b3. Let c3 be the conjugation that maps P3 back to P0, and let x3 be c3(x). We then have x3e = p0 + w to the b3. Do this across the board and multiply, giving |x|e = p0 + w to the b0+b1+b2… Again, the element p0 that makes this true lies in R, and in P, so we have built [|x|\P] in R, and this is the same as [x\P] in S.
If P is inert, the relationship also holds. Let the smaller residue field have order o as above, and let the larger field have order od. In other words, the dimension of S/R is d. The galois group is cyclic, generated by z goes to zo. Gather the conjugates of z together, giving z to the 1+o+o2+…od-1. Divide this into z to the (od-1)/l and get |z|(o-1)/l. This is the jacobi formula downstairs.
Bravely move on to any galois extension S/R and any unramified prime. P splits into P0*P1*P2… Let G be the galois group, and let H be the subgroup that fixes P0. Remember that G acts transitively on the primes lying over P. For illustration let H have size 3, consisting of conjugations c0 c1 and c2. (c0 is trivial.) Let c6 move P2 onto P0. Clearly c6c1 and c6c2 will do just as well; call these c7 and c8 respectively. Apply c6 to xe + p2 = w to the b2 and get x6e + p0 = w to the b2. Multiply all these together and get (x0x3x6x9…)e + p0 = w to the b0+b1+b2+b3… The expression at the right is [x\P] in S. In other words, [x\P] = [x0x3x6…\P0].
Let T be the intermediate subring fixed by H. Thus S/T is galois, with galois group H. Let Q0 = P0 intersect T. Thus P0 lies over Q0. If another prime lies over Q0 then H moves P0 onto this other prime. But H fixes P0, hence Q0 is inert up through P0. We dealt with this case above. [x6\P0] in S = [x6x7x8\Q0] in T. Transform x0, x3, x6, x9, etc in this way and get all the conjugates of x, or |x|. Therefore, [x\P] in S = [|x|\Q0] in T. To clarify, the norm of x is taken relative to S/R, then this value in R is part of the legendre symbol over Q0 within the ring T.
To find [|x|\Q0] in T, |x| is raised to an exponent f, which is the size of the residue field T/Q0, minus 1, divided by l. As you step up from T to S, the residue degree of Q0 is multiplied by 3 to get the residue degree of P0 over P. At the same time, the residue degree of P0 over P is 3. Therefore T/Q0 is the same as R/P. The exponent f that implements the character is the same in R/P as it is in T/Q0. Thus the expression is the same as [|x|\P] in R. That completes the connection from [x\P] in S to [|x|\P] in R. The relationship holds for any galois extension.
Let T/R be a separable extension that is not galois, and let S be the normal closure of T. Thus S/R and S/T are galois. Let y be an element of T, and let x in S have norm Y relative to S/T. [x\P]S = [|x|\P]R. Since the norm of the norm is the norm, the second expression is [|y|\P]R. That's one of the two expressions we want. Change the left side to [|x|\P]T, or [y\P]T, and we're done.
There is one catch; is there an x in S for every y in T? It's enough to find an x whose norm is y plus anything in P. That doesn't change any of the jacobi symbols. Push P up to some Q in S and mod out by that. Norm now maps a larger residue field into a smaller. It actually maps the larger field onto the smaller. Let the fields have sizes o and od, whence norm = z to the (od-1) / (o-1). z is a primitive element, although norm does the same thing to any power of z. Norm takes primitive z upstairs to primitive v downstairs, z2 to v2, z3 to v3, and so on, wrapping the larger field around the smaller like a covering space. If P is inert, so that P and Q coincide, then every y is covered and we're done. This is not usually the case.
Let P split into P0, P1, and P2 in T. By the chinese remainder theorem, T/P becomes T/P0 * T/P1 * T/P2. We need an x in S whose norm projects to any triple y0 y1 y2 in these three quotient rings. S/P is also isomorphic to S/P0 * S/P1 * S/P2. And S/P0 is a ring extension of T/P0 etc. Find x0 x1 x2 whose norms map to y0 y1 y2. This triple uniquely determines x.
So R doesn't matter any more. We have S/T a galois extension. Let P = P0; then we can do the same for P1 and P2. Let y be an element in T/P. We need an x in S/P whose norm maps to y. We have already evaluated the case of P inert in S, so let P split into Q0 * Q1 in S. Let x0 map to y through S/Q0, and let x1 map to y through S/Q1. Combine these to build x mapping to y, and that completes the proof.
Adjoin the cube root of 2 to the integers, giving an extension R that is a ufd, but is not galois. The primes over 5 are uneven, having residue degrees of 5 and 25. We don't know anything about quadratic reciprocity in R, but we do know that [x\5]R = [|x|\5]Z.
An odd integer n is prime iff for every x coprime to n, x(n-1)/2 mod n = [x\n], where [x\n] is the jacobi symbol of x over n.
If n is prime the jacobi symbol is the legendre symbol, which is 1 if x is a square mod n, and -1 otherwise. Raise a square to the (n-1)/2 and you are raising something else to the n-1, which becomes 1, just like the legendre symbol. Raise a nonsquare to the (n-1)/2 and get -1; so it all works out.
Conversely, suppose the equation holds more than half the time, yet n is not prime. Let n have a factor of pk, for k > 1. The group of units includes a cycle of order pk-1, comprising the multiples of p in pk, which I will call the p cycle. This runs in parallel with a cycle of order p-1, and perhaps other cycles if there are other prime factors of n. The integer 1 mod n projects to 0 in the p cycle, and 1 in the cycle of order p-1. Similarly, -1 projects to 0 in the p cycle, and -1 in the cycle of order p-1. If x is coprime to n then it is a valid nonzero unit in the cycle of order p-1, else it would be a multiple of p. With this established, x could land anywhere in the p cycle. An x chosen at random will be nonzero in the p cycle most of the time. Even if pk is as small as 32, x is nonzero in this cycle 2/3 of the time. Raising to the (n-1)/2 multiplies this value by -1/2, which permutes all the values in the cycle. The result isn't going to be 0, which would be necessary for x(n-1)/2 = ±1 mod n. The test fails at least 2/3 of the time. Thus n is squarefree.
Again, the jacobi symbol and the exponential agree more than half the time. When they agree, the value is ±1. Square this, and xn-1 is 1 more than half the time. The chinese remainder theorem tells us a uniform distribution mod n implies, and comes from, a uniform distribution mod p for each prime factor p in n. If half the nonzero values of x lead to 1 mod p, then at most half of these values of x lead to 1 mod n. So more than half the values mod p, raised to the n-1, yield 1.
Suppose p-1 does not divide n-1. Raise x, mod p, to the n-1, thus multiplying its discrete log by n-1. The nonzero values land on various roots of 1, evenly distributed. The roots of 1 could be 1 and -1, thus at most half the nonzero values land on 1. This is not enough, hence each p-1 divides n-1. This implies n is one of those pesky carmichael numbers.
Suppose (n-1)/(p-1) is even. After n-1 is cut in half, it is still sufficient to drive each x up to a value of 1 mod p. This can only equal 1 mod n (rather than -1). Each time the jacobi test succeeds, it succeeds with 1. However, have the jacobi symbols come out -1. This causes the test to fail at least half the time. Therefore (n-1)/(p-1) is odd for each prime p dividing n.
Let p and q be two primes dividing n. Raising x to the (n-1)/2 and looking mod p or q has the effect of telling us whether x is a square mod p or mod q. All combinations appear in a uniform distribution. Half the time x will be a square under one prime and a nonsquare under the other. The result is a value that is 1 mod one prime and -1 mod the other. This cannot equal ±1 mod n. The test fails at least half the time. Two prime factors are not possible.
In summary, a composite number fails the jacobi test at least half the time. This gives a probabilistic algorithm with specific error constraints. If the jacobi test succeeds on 20 randomly selected values of x, then n is composite with probability below 1 in a million. If you want more certainty, run the test another 20 times, and n is composite with probability below 1 in a trillion. It doesn't take long to attain near certainty.
The test suggests we make sure x and n are coprime at the outset, but this is not necessary, for the jacobi test, based on the gcd algorithm, will reveal any common factors. This is unlikely in any case, since n usually consists of large primes, and you're not going to stumble onto one of these by accident.
The test is efficient for large values of n. Modular exponentiation is tractable, and the jacobi symbol [x\n] is computed using the gcd algorithm, which also runs in log(n) time. In fact, gcd runs a bit faster than you might think.
Here is a question inspired by the previous section. Let n be a positive odd integer greater than 1. If x(n-1)/2 is ±1, when is it equal to the jacobi symbol [x\n]? The value obtained by exponentiation looks reasonable, but is it right? First note that x and n are coprime, else we would not obtain a value of ±1. As it turns out, the two values agree if there is an exponent m and a value c such that xm = ±1 and cm = -1.
Assume c and m exist. Let m = u×2k, where u is odd. For notational convenience let e (the even part) = 2k. Let y = xu and b = cu, giving ye = ±1 and be = -1.
If r (a prime number) divides n, be = -1 mod r, and b2e = 1 mod r. Therefore r-1 is divisible by 2e. All divisors of n are 1 mod 2e.
Assume d1 and d2 are divisors of n, and [y\d1] and [y\d2] agree with the corresponding exponential expressions y to the (d1-1)/2 and y to the (d2-1)/2, mod n. Consider d3 = d1×d2. Jacobi symbols are multiplied, so [y\d3] = [y\d1] × [y\d2]. Write d1 = 2ev1+1 and d2 = 2ev2+1. The new exponent becomes (d1d2-1)/2, or 2e2v1v2 + ev1 + ev2. The first term in the exponent looks like d1-1 times ev2. Raise y to this power and get 1, which doesn't change a thing. The last two terms are (d1-1)/2 and (d2-1)/2. This produces the product of the original exponential expressions. If d1 and d2 match, then so does d3.
For each prime r, [y\r] = y(r-1)/2 mod r. Remember that y was set to xu. Thus y to the (r-1)/2 becomes a power of ye, and becomes ±1 mod n. 1 mod n corresponds to 1 mod r, and -1 mod n corresponds to -1 mod r, hence [y\r] = y(r-1)/2 mod n. This holds for all primes r dividing n. Use the previous result to combine divisors, until [y\n] = y(n-1)/2 mod n.
Great, but we're really interested in x. Replace y with xu and get this.
[xu\n] = xu×(n-1)/2 mod n
The left side is [x\n]u, and since u is odd, this is the same as [x\n]. The right side is also an expression that equals ±1 raised to the u, so that doesn't change anything either. At the end of the day, [x\n] = x(n-1)/2. The jacobi symbol agrees with the exponential. All we need is c and m as described above.
Assume x(n-1)/2 comes out ±1. How can we use the above to guarantee a match with [x\n]?
If n = 3 mod 4, let c = -1 and let m = (n-1)/2.
If the exponential comes out -1 it must be right. Let c = x and let m = (n-1)/2.
If a lower exponential xk = -1, for k dividing n, let c = x and let m = k.
If xu = 1 (u odd), let c = -x and let m = u.
The strong pseudoprime test, attributed to Miller and Rabin, is a computational improvement on the jacobi test. It never computes a jacobi symbol; instead it determines whether the exponential is accurate using conditions 3 and 4 above. If either condition holds the exponential agrees with [x\n], and more important, if both fail n is composite. Let's see why this is so.
If x(n-1)/2 ≠ ±1, the pseudoprime test fails and n is composite.
Let u be the odd portion of n-1. If xu ≠ 1, and its successive squares eventually produce 1, without passing through -1, 1 has a square root different from ±1, and n is composite.
Raise x to the u. If this is 1 it will remain 1 all the way up to xn-1. The exponential matches the jacobi symbol by condition 4. If xu is -1, invoke condition 3. If xu is anything else, keep squaring until you reach -1. When you find it, invoke condition 3. If you don't find it, n is composite.
/* Strong Pseudoprime Test */
/* Run this 20 times with random values of x, and if each returns true, */
/* n is composite with probability 1 in a trillion. */
bool StrongPrimeTest(x, n)
{
/* remove powers of 2 from n-1 */
for(k=0, u=n-1; even(u); u/=2)
++k;
x = (x^u) % n; /* x to the u mod n */
if(x == 1 || x == -1) return true; /* could be prime */
--k; /* don't need to go all the way up to n-1 */
while(k > 0) { /* at most log2(n) iterations */
x = (x^2) % n;
if(x == 1) return false; /* composite */
if(x == -1) return true;
--k;
}
/* We didn't even get ±1 for x^((n-1)/2). */
return false;
}
|
If n is composite and x is chosen at random, the strong pseudoprime test indicates composite with probability 3/4. This is an improvement over the jacobi prime test, which establishes composite with probability 1/2. Trying 20 values actually gives confidence of 1 in a trillion, rather than 1 in a million.
Let u be the largest odd divisor of n-1. Let k be the maximum integer for which there is some x, such that x raised to the 2k = -1. Note that k is at least 0, since -1 to the first power is indeed -1.
Let m = u×2k. If n is prime, the cyclic multiplicative group mod n is divisible by u, and by 2k+1, thus divisible by 2m. Every x is an mth root of 1 or an mth root of -1, but we're assuming n is composite, so assume x is not an mth root of ±1. Raise x to the u and we don't get ±1, so we keep going. Square, and square, and square, and we never get ±1, else x would be an mth root of ±1. The test proves n is composite. How often do we miss the mth roots of ±1?
The aforementioned mth roots of ±1 form a group which I will call G. Find x so that x to the 2k = -1. Then raise this to the u and get -1. Thus xm = -1. There is at least one x that when raised to the m yields -1. This belongs to G.
Let H be all the (2m)th roots of 1. G is a subgroup of H. The homomorphism xm takes H into the square roots of 1, and it takes G onto ±1. Since n is composite, there will be other square roots of 1 beyond ±1.
Split n into a product of s prime powers pi to the bi. Everything in G becomes an mth root of ±1 mod pi to the bi. A typical cycle of units, of order pb-1×(p-1), has an mth root of -1 inherited from G. This implies a root of order 2×2k. Since p is odd, 2×2k divides p-1. In other words, p = 1 mod 2×2k. Multiply primes together and n = 1 mod 2×2k. This places an upper bound on k. It follows that 2m is at most n-1.
For each prime power, independently select an mth root of -1, or 1. When raised to the m power, we have all combinations of 1 and -1. This gives 2s square roots of 1. In other words, xm maps H onto the square roots of 1. Only two of these come out ±1 mod n, and this is the image of G. Running the homomorphism in reverse, the index of G in H is 2s-1. When outside of G, the pseudoprime test fails, so if s > 2, the test fails 3/4 of the time, and we're done.
Assume s = 2, two prime powers in n. In the worst case, 2m = n-1, that's as big as H can be, and the (n-1)th roots of 1 form a subgroup inside all the units mod n. Call this group W, and let V be the group of all units mod n. The efficiency of the algorithm is multiplied by the index of W in V. n is a carmichael number iff every x coprime to n satisfies xn-1 = 1 mod n, iff every x is an n-1 root of 1, iff V = W. Since a carmichael number requires three primes, n is not a carmichael number. There is some x in V that is not in W. The index of W in V is at least 2, and when combined with the index of G in H, we get 4, and we're done.
Finally, let s = 1, so that n = pb, and V is cyclic of order pb-1×(p-1). Since p and n-1 are coprime, W is contained in the latter cycle. At worst, the entire cycle is W, whence the index of W in V is pb-1. This is less than 4 only when n = 32. (Not that anybody's going to work hard to see if 9 is prime.) Even in this case we can still save the day. Bring in the elements that are not units, namely 3 and 6, and 6 elements out of 8 fail the pseudoprime test.
For any composite n, at least 3/4 of the values of x between 1 and n-1 prove that n is composite. For most values of n, the ratio is much better. However, when n is a carmichael number based on 3 primes, G has index 4 in H, and W has index 1 in V, giving a combined index of 4. It is conjectured that there are infinitely many such numbers, and if true, the test cannot be more than 3/4 accurate, so it looks like we're done.
When the pseudoprime test proves n is composite, n is often handed off to a factoring algorithm, and some algorithms have trouble with prime powers. A simple check insures n is not a prime power.
Suppose n = pk, and choose x at random, and raise x to the n-1. If the result is 0 then x contains a lesser power of p, and gcd(x,n) provides a factor of n. Otherwise x is raised to the p-1 first, then to the (n-1)/(p-1). The result is 1 mod p. Subtract 1 and take the gcd with n to extract a lesser power of p. However if x = 1 mod n, raise x to the (n-1)/2, (n-1)/4, etc, until you have a square root of 1. (The strong pseudoprime test naturally performs these calculations.) Half the time the square root of 1 will be nontrivial, i.e. not -1. Yet it is 1 or -1 in the cycle of order p-1. Add or subtract 1 to find something divisible by p. Once again the gcd algorithm finds a factor of n.