Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x3 ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if p and q are primary numbers in the ring of Eisenstein integers, both coprime to 3, the congruence x3 ≡ p (mod q) is solvable if and only if x3 ≡ q (mod p) is solvable.
History Sometime before 1748 Euler made the first conjectures about the cubic residuacity of small integers, but they were not published until 1849, 62 years after his death. Gauss's published works mention cubic residues and reciprocity three times: there is one result pertaining to cubic residues in the Disquisitiones Arithmeticae (1801). In the introduction to the fifth and sixth proofs of quadratic reciprocity (1818) he said that he was publishing these proofs because their techniques (Gauss's lemma and Gaussian sums, respectively) can be applied to cubic and biquadratic reciprocity. Finally, a footnote in the second (of two) monographs on biquadratic reciprocity (1832) states that cubic reciprocity is most easily described in the ring of Eisenstein integers. From his diary and other unpublished sources, it appears that Gauss knew the rules for the cubic and quartic residuacity of integers by 1805, and discovered the full-blown theorems and proofs of cubic and biquadratic reciprocity around 1814. Proofs of these were found in his posthumous papers, but it is not clear if they are his or Eisenstein's. Jacobi published several theorems about cubic residuacity in 1827, but no proofs. In his Königsberg lectures of 1836–37 Jacobi presented proofs. The first published proofs were by Eisenstein (1844).
Integers A cubic residue (mod p) is any number congruent to the third power of an integer (mod p). If x3 ≡ a (mod p) does not have an integer solution, a is a cubic nonresidue (mod p). Cubic residues are usually only defined in modulus n such that λ ( n ) {\displaystyle \lambda (n)} (the Carmichael lambda function of n) is divisible by 3, since for other integer n, all residues are cubic residues. As is often the case in number theory, it is easier to work modulo prime numbers, so in this section all moduli p, q, etc., are assumed to be positive odd primes. We first note that if q ≡ 2 (mod 3) is a prime then every number is a cubic residue modulo q. Let q = 3n + 2; since 0 = 03 is obviously a cubic residue, assume x is not divisible by q. Then by Fermat's little theorem,
x q ≡ x ( mod q ) , x q − 1 ≡ 1 ( mod q ) {\displaystyle x^{q}\equiv x{\pmod {q}},\qquad x^{q-1}\equiv 1{\pmod {q}}}
Multiplying the two congruences we have
x 2 q − 1 ≡ x ( mod q ) {\displaystyle x^{2q-1}\equiv x{\pmod {q}}}
Now substituting 3n + 2 for q we have:
x 2 q − 1 = x 6 n + 3 = ( x 2 n + 1 ) 3 . {\displaystyle x^{2q-1}=x^{6n+3}=\left(x^{2n+1}\right)^{3}.}
Therefore, the only interesting case is when the modulus p ≡ 1 (mod 3). In this case the non-zero residue classes (mod p) can be divided into three sets, each containing (p−1)/3 numbers. Let e be a cubic non-residue. The first set is the cubic residues; the second one is e times the numbers in the first set, and the third is e2 times the numbers in the first set. Another way to describe this division is to let e be a primitive root (mod p); then the first (resp. second, third) set is the numbers whose indices with respect to this root are congruent to 0 (resp. 1, 2) (mod 3). In the vocabulary of group theory, the cubic residues form a subgroup of index 3 of the multiplicative group ( Z / p Z ) × {\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }} and the three sets are its cosets.
Primes ≡ 1 (mod 3) A theorem of Fermat states that every prime p ≡ 1 (mod 3) can be written as p = a2 + 3b2 and (except for the signs of a and b) this representation is unique. Letting m = a + b and n = a − b, we see that this is equivalent to p = m2 − mn + n2 (which equals (n − m)2 − (n − m)n + n2 = m2 + m(n − m) + (n − m)2, so m and n are not determined uniquely). Thus,
4 p = ( 2 m − n ) 2 + 3 n 2 = ( 2 n − m ) 2 + 3 m 2 = ( m + n ) 2 + 3 ( m − n ) 2 {\displaystyle {\begin{aligned}4p&=(2m-n)^{2}+3n^{2}\\&=(2n-m)^{2}+3m^{2}\\&=(m+n)^{2}+3(m-n)^{2}\end{aligned}}}
and it is a straightforward exercise to show that exactly one of m, n, or m − n is a multiple of 3, so
p = 1 4 ( L 2 + 27 M 2 ) , {\displaystyle p={\frac {1}{4}}(L^{2}+27M^{2}),}
and this representation is unique up to the signs of L and M. For relatively prime integers m and n define the rational cubic residue symbol as
[ m n ] 3 = { 1 m is a cubic residue ( mod n ) − 1 m is a cubic non-residue ( mod n ) {\displaystyle \left[{\frac {m}{n}}\right]_{3}={\begin{cases}1&m{\text{ is a cubic residue }}{\pmod {n}}\\-1&m{\text{ is a cubic non-residue }}{\pmod {n}}\end{cases}}}
This symbol does not have the multiplicative properties of the Legendre symbol; for this, we need the true cubic character with values in the cubic roots of 1 defined below.
Euler's conjectures (now proved). Let p = a2 + 3b2 be a prime. Then the following hold:
[ 2 p ] 3 = 1 ⟺ 3 ∣ b [ 3 p ] 3 = 1 ⟺ 9 ∣ b or 9 ∣ ( a ± b ) [ 5 p ] 3 = 1 ⟺ 15 ∣ b or 3 ∣ b and 5 ∣ a or 15 ∣ ( a ± b ) or 15 ∣ ( 2 a ± b ) [ 6 p ] 3 = 1 ⟺ 9 ∣ b or 9 ∣ ( a ± 2 b ) [ 7 p ] 3 = 1 ⟹ ( 3 ∣ b and 7 ∣ a ) or 21 ∣ ( b ± a ) or 7 ∣ ( 4 b ± a ) or 21 ∣ b or 7 ∣ ( b ± 2 a ) {\displaystyle {\begin{aligned}\left[{\tfrac {2}{p}}\right]_{3}=1\quad &\Longleftrightarrow \quad 3\mid b\\\left[{\tfrac {3}{p}}\right]_{3}=1\quad &\Longleftrightarrow \quad 9\mid b{\text{ or }}9\mid (a\pm b)\\\left[{\tfrac {5}{p}}\right]_{3}=1\quad &\Longleftrightarrow \quad 15\mid b{\text{ or }}3\mid b{\text{ and }}5\mid a{\text{ or }}15\mid (a\pm b){\text{ or }}15\mid (2a\pm b)\\\left[{\tfrac {6}{p}}\right]_{3}=1\quad &\Longleftrightarrow \quad 9\mid b{\text{ or }}9\mid (a\pm 2b)\\\left[{\tfrac {7}{p}}\right]_{3}=1\quad &\Longrightarrow \quad (3\mid b{\text{ and }}7\mid a){\text{ or }}21\mid (b\pm a){\text{ or }}7\mid (4b\pm a){\text{ or }}21\mid b{\text{ or }}7\mid (b\pm 2a)\end{aligned}}}
The first two can be restated as follows. Let p be a prime that is congruent to 1 modulo 3. Then:
2 is a cubic residue of p if and only if p = a2 + 27b2. 3 is a cubic residue of p if and only if 4p = a2 + 243b2. Gauss's theorem. Let p be a positive prime such that
p = 3 n + 1 = 1 4 ( L 2 + 27 M 2 ) . {\displaystyle p=3n+1={\tfrac {1}{4}}\left(L^{2}+27M^{2}\right).}
Then L ( n ! ) 3 ≡ 1 ( mod p ) . {\displaystyle L(n!)^{3}\equiv 1{\pmod {p}}.}
One can easily see that Gauss's Theorem implies:
[ L p ] 3 = [ M p ] 3 = 1. {\displaystyle \left[{\tfrac {L}{p}}\right]_{3}=\left[{\tfrac {M}{p}}\right]_{3}=1.}
Jacobi's theorem (stated without proof). Let q ≡ p ≡ 1 (mod 6) be positive primes. Obviously both p and q are also congruent to 1 modulo 3, therefore assume:
p = 1 4 ( L 2 + 27 M 2 ) , q = 1 4 ( L ′ 2 + 27 M ′ 2 ) . {\displaystyle p={\tfrac {1}{4}}\left(L^{2}+27M^{2}\right),\qquad q={\tfrac {1}{4}}\left(L'^{2}+27M'^{2}\right).}
Let x be a solution of x2 ≡ −3 (mod q). Then
x ≡ ± L ′ 3 M ′ ( mod q ) , {\displaystyle x\equiv \pm {\frac {L'}{3M'}}{\pmod {q}},}
and we have:
[ q p ] 3 = 1 ⟺ [ L + 3 M x 2 p q ] 3 = 1 ⟺ [ L + 3 M x L − 3 M x q ] 3 = 1 [ q p ] 3 = 1 ⟹ [ L M ′ + L ′ M L M ′ − L ′ M q ] 3 = 1 {\displaystyle {\begin{aligned}\left[{\frac {q}{p}}\right]_{3}=1\quad &\Longleftrightarrow \quad \left[{\frac {{\frac {L+3Mx}{2}}p}{q}}\right]_{3}=1\quad \Longleftrightarrow \quad \left[{\frac {\frac {L+3Mx}{L-3Mx}}{q}}\right]_{3}=1\\\left[{\frac {q}{p}}\right]_{3}=1\quad &\Longrightarrow \quad \left[{\frac {\frac {LM'+L'M}{LM'-L'M}}{q}}\right]_{3}=1\end{aligned}}}
Lehmer's Theorem. Let q and p be primes, with p = 1 4 ( L 2 + 27 M 2 ) . {\displaystyle p={\tfrac {1}{4}}\left(L^{2}+27M^{2}\right).} Then:
[ q p ] 3 = 1 ⟺ q ∣ L M or L ≡ ± 9 r 2 u + 1 M ( mod q ) , {\displaystyle \left[{\frac {q}{p}}\right]_{3}=1\quad \Longleftrightarrow \quad q\mid LM{\text{ or }}L\equiv \pm {\frac {9r}{2u+1}}M{\pmod {q}},}
where
u ≢ 0 , 1 , − 1 2 , − 1 3 ( mod q ) and 3 u + 1 ≡ r 2 ( 3 u − 3 ) ( mod q ) . {\displaystyle u\not \equiv 0,1,-{\tfrac {1}{2}},-{\tfrac {1}{3}}{\pmod {q}}\quad {\text{and}}\quad 3u+1\equiv r^{2}(3u-3){\pmod {q}}.}
Note that the first condition implies that any number that divides L or M is a cubic residue (mod p). The first few examples of this are equivalent to Euler's conjectures:
[ 2 p ] 3 = 1 ⟺ L ≡ M ≡ 0 ( mod 2 ) [ 3 p ] 3 = 1 ⟺ M ≡ 0 ( mod 3 ) [ 5 p ] 3 = 1 ⟺ L M ≡ 0 ( mod 5 ) [ 7 p ] 3 = 1 ⟺ L M ≡ 0 ( mod 7 ) {\displaystyle {\begin{aligned}\left[{\frac {2}{p}}\right]_{3}=1\quad &\Longleftrightarrow \quad L\equiv M\equiv 0{\pmod {2}}\\\left[{\frac {3}{p}}\right]_{3}=1\quad &\Longleftrightarrow \quad M\equiv 0{\pmod {3}}\\\left[{\frac {5}{p}}\right]_{3}=1\quad &\Longleftrightarrow \quad LM\equiv 0{\pmod {5}}\\\left[{\frac {7}{p}}\right]_{3}=1\quad &\Longleftrightarrow \quad LM\equiv 0{\pmod {7}}\end{aligned}}}
Since obviously L ≡ M (mod 2), the criterion for q = 2 can be simplified as:
[ 2 p ] 3 = 1 ⟺ M ≡ 0 ( mod 2 ) . {\displaystyle \left[{\frac {2}{p}}\right]_{3}=1\quad \Longleftrightarrow \quad M\equiv 0{\pmod {2}}.}
Martinet's theorem. Let p ≡ q ≡ 1 (mod 3) be primes, p q = 1 4 ( L 2 + 27 M 2 ) . {\displaystyle pq={\tfrac {1}{4}}(L^{2}+27M^{2}).} Then
[ L p ] 3 [ L q ] 3 = 1 ⟺ [ q p ] 3 [ p q ] 3 = 1. {\displaystyle \left[{\frac {L}{p}}\right]_{3}\left[{\frac {L}{q}}\right]_{3}=1\quad \Longleftrightarrow \quad \left[{\frac {q}{p}}\right]_{3}\left[{\frac {p}{q}}\right]_{3}=1.}
Sharifi's theorem. Let p = 1 + 3x + 9x2 be a prime. Then any divisor of x is a cubic residue (mod p).
Eisenstein integers
Background In his second monograph on biquadratic reciprocity, Gauss says:
The theorems on biquadratic residues gleam with the greatest simplicity and genuine beauty only when the field of arithmetic is extended to imaginary numbers, so that without restriction, the numbers of the form a + bi constitute the object of study ... we call such numbers integral complex numbers. [bold in the original] These numbers are now called the ring of Gaussian integers, denoted by Z[i]. Note that i is a fourth root of 1. In a footnote he adds
The theory of cubic residues must be based in a similar way on a consideration of numbers of the form a + bh where h is an imaginary root of the equation h3 = 1 ... and similarly the theory of residues of higher powers leads to the introduction of other imaginary quantities. In his first monograph on cubic reciprocity Eisenstein developed the theory of the numbers built up from a cube root of unity; they are now called the ring of Eisenstein integers. Eisenstein said that to investigate the properties of this ring one need only consult Gauss's work on Z[i] and modify the proofs. This is not surprising since both rings are unique factorization domains. The "other imaginary quantities" needed for the "theory of residues of higher powers" are the rings of integers of the cyclotomic number fields; the Gaussian and Eisenstein integers are the simplest examples of these.
Facts and terminology Let
ω = − 1 + i 3 2 = e 2 π i 3 , ω 3 = 1. {\displaystyle \omega ={\frac {-1+i{\sqrt {3}}}{2}}=e^{\frac {2\pi i}{3}},\qquad \omega ^{3}=1.}
And consider the ring of Eisenstein integers:
Z [ ω ] = { a + b ω : a , b ∈ Z } . {\displaystyle \mathbb {Z} [\omega ]=\left\{a+b\omega \ :\ a,b\in \mathbb {Z} \right\}.}
This is a Euclidean domain with the norm function given by:
N ( a + b ω ) = a 2 − a b + b 2 . {\displaystyle N(a+b\omega )=a^{2}-ab+b^{2}.}
Note that the norm is always congruent to 0 or 1 (mod 3). The group of units in Z [ ω ] {\displaystyle \mathbb {Z} [\omega ]} (the elements with a multiplicative inverse or equivalently those with unit norm) is a cyclic group of the sixth roots of unity,
{ ± 1 , ± ω , ± ω 2 } . {\displaystyle \left\{\pm 1,\pm \omega ,\pm \omega ^{2}\right\}.}
Z [ ω ] {\displaystyle \mathbb {Z} [\omega ]} is a unique factorization domain. The primes fall into three classes:
3 is a special case:
3 = − ω 2 ( 1 − ω ) 2 . {\displaystyle 3=-\omega ^{2}(1-\omega )^{2}.}
It is the only prime in Z {\displaystyle \mathbb {Z} } divisible by the square of a prime in Z [ ω ] {\displaystyle \mathbb {Z} [\omega ]} . The prime 3 is said to ramify in Z [ ω ] {\displaystyle \mathbb {Z} [\omega ]} . Positive primes in Z {\displaystyle \mathbb {Z} } congruent to 2 (mod 3) are also primes in Z [ ω ] {\displaystyle \mathbb {Z} [\omega ]} . These primes are said to remain inert in Z [ ω ] {\displaystyle \mathbb {Z} [\omega ]} . Note that if q {\displaystyle q} is any inert prime then:
N ( q ) = q 2 ≡ 1 ( mod 3 ) . {\displaystyle N(q)=q^{2}\equiv 1{\pmod {3}}.}
Positive primes in Z {\displaystyle \mathbb {Z} } congruent to 1 (mod 3) are the product of two conjugate primes in Z [ ω ] {\displaystyle \mathbb {Z} [\omega ]} . These primes are said to split in Z [ ω ] {\displaystyle \mathbb {Z} [\omega ]} . Their factorization is given by:
p = N ( π ) = N ( π ¯ ) = π π ¯ . {\displaystyle p=N(\pi )=N({\overline {\pi }})=\pi {\overline {\pi }}.}
for example
7 = ( 3 + ω ) ( 2 − ω ) . {\displaystyle 7=(3+\omega )(2-\omega ).}
A number is primary if it is coprime to 3 and congruent to an ordinary integer modulo ( 1 − ω ) 2 , {\displaystyle (1-\omega )^{2},} which is the same as saying it is congruent to ± 2 {\displaystyle \pm 2} modulo 3. If gcd ( N ( λ ) , 3 ) = 1 {\displaystyle \gcd(N(\lambda ),3)=1} one of λ , ω λ , {\displaystyle \lambda ,\omega \lambda ,} or ω 2 λ {\displaystyle \omega ^{2}\lambda } is primary. Moreover, the product of two primary numbers is primary and the conjugate of a primary number is also primary. The unique factorization theorem for Z [ ω ] {\displaystyle \mathbb {Z} [\omega ]} is: if λ ≠ 0 , {\displaystyle \lambda \neq 0,} then
λ = ± ω μ ( 1 − ω ) ν π 1 α 1 π 2 α 2 π 3 α 3 ⋯ , μ ∈ { 0 , 1 , 2 } , ν , α 1 , α 2 , … ⩾ 0 {\displaystyle \lambda =\pm \omega ^{\mu }(1-\omega )^{\nu }\pi _{1}^{\a