A Partitioning of the Natural Numbers 1, 2, 3, ..., Q-1 into N Sets where Q is a Prime, N Divides Q-1
Created | Updated Nov 26, 2008
Very little mathematical background is required to read this article; the background will be developed as needed. Topics as diverse as Fermat's "little" theorem, the cross-ratio function of geometry and complex analysis, primitive roots, Sophie Germain's theorem pertaining to Fermat's Last Theorem, the quadratic reciprocity law, higher order reciprocity laws, Gaussian sums, and Perron's theorem (sometimes used with Gaussian sums to prove the quadratic reciprocity law) will be discussed. As unlikely as it might seem, these topics have a common thread. Let n be a natural number and q be a prime such that q-1 is an integer multiple of n. (That infinitely many such primes exist follows from Dirichlet's theorem that there are infinitely many primes in the arithmetic progression in+j, i=1, 2, 3, ... where j is an integer relatively prime to n.) All of these topics are related to a partitioning of the natural numbers 1, 2, 3, ..., q-1 into n sets containing (q-1)/n elements each. The main topic of this article is the number of consecutive integers in each of these sets. Some topics only pertain to the partitioning of these natural numbers into sets and not to the number of consecutive integers in each set.
First, some mathematical preliminaries will be attended to; (1) a natural number is a positive integer, (2) a non-zero integer x is said to divide an integer y if y is an integer multiple of x, (3) integers x and y are said to be relatively prime if they have no common divisors other than 1 or -1, (4) an integer x is said to be congruent to an integer y modulo a non-zero integer z if z divides x-y (this is denoted by x≡y(mod z)), (5) x is called a least residue of y modulo z if x≡y(mod z) and 0≤x<z, (6) if q is a prime and x is an integer where q does not divide x, then xq-1≡1(mod q) (Fermat's "little" theorem), and (7) an integer g is called a primitive root of a prime q if q does not divide g and gd≠1(mod q) for any natural number d less than q-1 (there always exist primitive roots).
The Partitioning
Let g be a primitive root of q. The least residues modulo q of g1, g2, g3, ..., gq-1 are in some order 1, 2, 3, ..., (q-1). (If gi≡gj(mod q), 1≤i≤q-1, 1≤j≤q-1, j<i, then gi-j≡1(mod q), 1≤i-j<q-1, in contradiction to the definition of a primitive root. The least residues modulo q of g1, g2, g3, ..., gq-1 must then be a permutation of 1, 2, 3, ..., q-1.) Denote (q-1)/n by r. Let Ti, i=1, 2, 3, ..., n, denote the least residues modulo q of gi, gi+n, gi+2n, gi+3n, ..., gi+(r-1)n; this is the partitioning of the natural numbers 1, 2, 3, ..., (q-1) into n sets that will be discussed in this article. Let si denote the number of consecutive integers in Ti. For example, 2 is a primitive root of 13, so for q=13, n=3, and g=2, T1={2, 3, 11, 10}, T2={4, 6, 9, 7}, T3={8, 12, 5, 1}, s1=2, s2=1, and s3=0. (If, for example, x, x+1, and x+2 are elements of a set, then the number of consecutive integers in this sequence is considered to be 2. Similar counting of consecutive integers in a set applies for longer sequences.) A prime greater than 2 has more than one primitive root, but using a different primitive root makes no essential difference; the indices of the sets are just permuted. (If g1 is another primitive root of q, then g1≡gh(mod q) where h and q-1 are relatively prime. The least residues modulo q of gi, gi+n, gi+2n, gi+3n, ..., gi+(r-1)n are in some order the least residues modulo q of g1j, g1j+n, g1j+2n, g1j+3n, ..., g1j+(r-1)n where j≡ki(mod n) and k and n are relatively prime. For example, 6 is another primitive root of 13 and T1={6, 9, 7, 4}, T2={10, 2, 3, 11}, and T3={8,12, 5, 1} in this case. The T1 set for g=2 maps to the T2 set for g=6 and the T2 set for g=2 maps to the T1 set for g=6 [this corresponds to k=2]. The Tn set is always the same no matter which primitive root is used.)The least residues modulo q of gi, gi+n, gi+2n, gi+3n, ..., gi+(r-1)n are the roots of the congruence x(q-1)/n≡y(mod q), 0<x<q, yn≡1(mod q), 0<y<q. This is another way of interpreting the sets T1, T2, T3, ..., Tn. If n=2, the set T1 is said to consist of the quadratic non-residues of q, and the set T2 is said to consist of the quadratic residues of q. (If n>2, the set Tn could be said to consist of the residues and the other sets could be said to consist of the non-residues, but there is no advantage in lumping the non-residue sets together.) This is the background needed for stating the quadratic reciprocity law. More will be said on this later.
Elementary Properties of the Number of Consecutive Elements in a Set
Theorems concerning s1, s2, s3, ..., sn will now be stated. Proofs of the theorems are not difficult, but are fairly lengthy and will be omitted. This is no major loss since the theorems themselves are of moderate interest. Let a, b, and c be integers relatively prime in pairs.(1) an+bn≡cn(mod q), q≡1(mod n), q does not divide abc, has a solution if and only if sn≠0.
(2) s1+s2+s3+...+sn=r-1.
(3) If r is even, exactly one of si is odd.
(4) If r is odd and n is even, si=si+(n/2), i=1, 2, 3, ..., (n/2).
(5) If n=2 and r is even, s1=s2+1.
(6) If 6 does not divide r and 2r≠1(mod q), then 6 divides sn. If 6 divides r and 2r≠1(mod q), then sn≡2(mod 6). If 6 does not divide r and 2r≡1(mod q), then sn≡3(mod 6). If 6 divides r and 2r≡1(mod q), then sn≡5(mod 6).
The following is a brief explanation of Theorem (6). Let x-1 denote an integer such that xx-1≡1(mod q). Let C(x) denote the least residues modulo q of x, 1-x, (1-x)-1, -x(1-x)-1, -x-1(1-x), and x-1 (the formal values of the cross-ratio function). If one element of C(x) is a root of x(q-1)/n≡1(mod q) and is one larger than another root, then every element of C(x) is a root and is one larger than another root. The elements of C(x) are distinct unless 2 is an element of C(x) (in which case the distinct elements are 2, (q+1)/2, and q-1) or a root of x2-x+1≡0(mod q), 0<x<q, is an element of C(x) (in which case the distinct elements are the two roots of x2-x+1≡0(mod q), 0<x<q). x2-x+1≡0(mod q) has a root if and only if 6 divides q-1.
Relevance of the Number of Consecutive Elements in a Set to Sophie Germain's Theorem
The following is Legendre's version of Sophie Germain's theorem. Let p and q be distinct odd primes and assume that the following conditions are satisfied: (1) If ap+bp≡cp(mod q), then q divides abc. (2) p is not congruent to the pth power of an integer modulo q. Then there is no solution of ap+bp=cp, p does not divide abc (the so-called first case of Fermat's Last Theorem). A corollary of Sophie Germain's theorem is; if p is an odd prime and q=2p+1 is a prime, then there is no solution of ap+bp=cp, p does not divide abc. Theorem (1) can be used to demonstrate this. If n is an odd prime, and q=2n+1 is a prime, then Tn={1, q-1}. 1 and q-1 are not consecutive (so that the first condition is satisfied) and n is not equal to 1 or q-1 (so that the second condition is satisfied). Wendt's theorem (concerning a cyclic matrix) is commonly used to determine if the first condition of Sophie Germain's theorem is satisfied; it's easier to compute the elements of Tn and determine if there are any consecutive elements than it is to compute Wendt's determinant.Non-Elementary Properties of the Number of Consecutive Elements in a Set
There are an abundance of non-elementary properties of s1, s2, s3, ..., sn. Some empirical results (for n≤16) are;(1) If q<40000, n=3, r is a square, and 2r≠1(mod q), then s1-s2=s2-s3 (or s2-s1=s1-s3 for some other primitive root of q).
(2) If q<40000 and n=3, then s1-s2=s2-s3 (or s2-s1=s1-s3) only if r is a square.
(3) If q<40000, n=3, r is a square, and 2r≡1(mod q), then s3-s2+2=s1-s3.
(4) If q<40000 and n=3, then s3-s2+2=s1-s3 only if r is a square.
(5) if q<40000 and n=3, then s1=s3 (or s2=s3) only if r/2 is odd.
(6) If q<40000 and n=3, then s1≠s2.
(7) If q<40000, n=4, and r is an odd square, then s1=s2=s3=s4.
(8) If q<40000 and n=4, then s1=s2=s3=s4 only if r is an odd square.
(9) If q<40000, n=4, and r is even, then s1-s2=s2-s3.
(10) If q<40000, n=6, r is even, and 22r≠1(mod q), then s1=s3=s4 (or s2=s3=s5 for some other primitive root of q).
(11) If q<40000, n=6, r is even, and 22r≡1(mod q), then s2-s3=s3-s4 and s1-s2=s4-s5=2(s2-s3) (or s2-s3=s3-s4 and s1-s2=s4-s5=2(s3-s4) for some other primitive root of q).
(12) If q<40000, n=8, r is an odd square, and 22r≡1(mod q), then s1=s3=s5=s7 and s2=s4=s6=s8.
(13) If q<40000 and n=8, then s1=s3=s5=s7 and s2=s4=s6=s8 only if r is an odd square.
(14) If q<40000, n=8, r is odd, and 22r≡1(mod q), then s1=s3 and s5=s7.
(15) If q<40000, n=8, r is even, and 22r≠1(mod q), then s1=s3=s5=s7.
(16) If q<40000, n=8, r is even, and 22r≡1(mod q), then s1-s3=s5-s7.
(17) If q<40000, n=10, r is even, and 22r≠1(mod q), then s1=s6=s7 and s3=s5=s8 (for some primitive root of q).
(18) If q<40000, n=10, r is even, and 22r≡1(mod q), then s1-s2=s8-s9, s3-s4=s6-s7, and s2-s3-s7+s8=-2(s4-s5-s5+s6).
(19) If q<40000, n=10, r is odd, and 22r≡1(mod q), then s1-s2=s3-s4 and s6-s7=s8-s9 (for some primitive root of q).
(20) If q<40000, n=10, r is odd, and 22r≠1(mod q), then s1-s4=s4-s2 and s6-s9=s9-s7 (for some primitive root of q).
(21) If q<40000, n=14, r is even, and 22r≠1(mod q), then s1=s8 and s5=s12 (for some primitive root of q).
From Theorem (6), you would expect the condition 2r≡1(mod q) (or the condition 2r≠1(mod q)) to have an effect on the si values. It's surprising that r being a square has an effect on the si values (when n=3, 4, or 8). In the mathematical literature, there is theory for cubic, quartic, and octic reciprocity. This raises the question of whether there is a connection between the si values and higher order reciprocity. (When n=2, there is a connection between the si values and quadratic reciprocity, and this connection is provided by Perron's theorem.) Another reason for expecting such a connection is the special role 2 plays in quadratic and higher order reciprocity.
Quadratic and Higher Order Reciprocity
In the following, the relevance of the sets T1, T2, T3, ..., Tn to reciprocity is shown. The Legendre symbol (a/p) of a, relative to p, is defined to be 1 when a is a quadratic residue modulo p, or to be -1 when a is a quadratic non-residue modulo p. Gauss' Quadratic Reciprocity Law states that if p and q are distinct odd primes, then (p/q)(q/p)=(-1)[(p-1)/2][(q-1)/2]. The quadratic reciprocity law can be proved using properties of the square of the Gaussian sum. Let ζ be a primitive pth root of unity. The principal Gaussian sum is ∑(j/p)ζj where the summation is from j=1 to p-1. The square of the principal Gaussian sum equals p when p≡1(mod 4) or -p when p≡3(mod 4). (The rest of the proof of the quadratic reciprocity law is not relevant here and is omitted.) (2/p)=(-1)(pp-1)/8; this is called the Supplement to the Quadratic Reciprocity Law. There is a supplement to the cubic reciprocity law and a supplement to the quartic reciprocity law.The generalization of Gaussian sums for n>2 is straightforward; instead of multiplying powers of ζ by 1 or -1 (roots of x2=1), powers of ζ are multiplied by powers of a primitive nth root of unity. For n=3, ρ=e(2/3)πi=(1/2)(-1+i√3) is a primitive nth root of unity (here e=2.71828, π=3.14159, and i=√(-1)). (The numbers ξ=a+bρ where a and b are rational integers are called the integers of the field k(ρ). The norm of the integer a+bρ is a2-ab+b2. An integer whose norm is a rational prime is a prime in k(ρ). if ξ≡±1(mod 3), then ξ is said to be primary.) For example, for p=13, n=3, and g=2 (a primitive root of 13), the least residues modulo p of g1, g4, g7, and g10 are 2, 3, 11, and 10, and these powers of ζ are multiplied by 1, the least residues modulo p of g2, g5, g8, and g11 are 4, 6, 9, and 7, and these powers of ζ are multiplied by ρ, and the least residues modulo p of g3, g6, g9, and g12 are 8, 12, 5, and 1, and these powers of ζ are multiplied by ρ2. The generalized Gaussian sum is then ρ2ζ1+ζ2+ζ3+ρζ4+ρ2ζ5+ρζ6+ρζ7+ρ2ζ8+ρζ9+ζ10+ζ11+ρ2ζ12. The cube of the generalized Gaussian sum is pπ where π is a primary prime in k(ρ) having a norm of p (this is an empirically derived result). Let R be the set of primes of the form 3i+1. For distinct primes p and q in R, q is a rational cube modulo p (this is an abbreviated way of saying that q is congruent to the cube of an integer modulo p) if and only if pπp is a cube of an integer in k(ρ) modulo q (this is an empirically derived result). Also, p is a rational cube modulo q if and only if qπq is a cube of an integer in k(ρ) modulo p. Therefore q is a cube modulo p and p is a cube modulo q if and only if πp is a cube of an integer (in k(ρ)) modulo q and πq is a cube of an integer (in k(ρ)) modulo p.
For n=4, the generalized Gaussian sum would be similarly formed. The fourth power of this generalized Gaussian sum is pπ2 where π is a prime in k(i) (i=√(-1)) having a norm of p (this is an empirically derived result).
Perron's Theorem
Perron's theorem is; (1) Suppose p=4k-1. Let r1, r2, r3, ..., r2k be the 2k quadratic residues modulo p together with 0, and let a be a number relatively prime of p. Then among the 2k numbers ri+a, there are k residues (possibly including 0) and k non-residues. (2) Suppose p=4k-1. Let n1, n2, n3, ..., n2k-1 be the 2k-1 non-residues. Then among the 2k-1 numbers ni+a, there are k residues (possibly including 0) and k-1 non-residues. (3) Suppose p=4k+1. Among the 2k+1 numbers ri+a are, if a is itself a residue, k+1 residues (including 0) and k non-residues; and, if a is a non-residue, k residues (not including 0) and k+1 non-residues. (4) Suppose p=4k+1. Among the 2k numbers ni+a are, if a is itself a residue, k residues (not including 0) and k non-residues; and, if a is a non-residue, k+1 residues (including 0) and k-1 non-residues.When a=1, Perron's theorem concerns the number of consecutive elements in T1 and T2. (Perron's theorem may look complicated, but it has no more content than Theorems (4) and (5).)
