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 12, 2008
INTRODUCTION
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) where a congruence symbol is usually used instead of the equal sign), (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 x**(q-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 g**d is not congruent to 1 modulo q for any natural number d less than q-1 (there always exist primitive roots). (x**(p-1), e.g., denotes x to the (p-1)th power.)
THE PARTITIONING
Let g be a primitive root of q. The least residues modulo q of g**1, g**2, g**3, ..., g**(q-1) are in some order 1, 2, 3, ..., (q-1). (If g**i=g**j(mod q), 1<=i<=q-1, 1<=j<=q-1, j<i, then q**(i-j)=1(mod q), 1<=(i-j)<q-1, in contradiction of the definition of a primitive root. The least residues modulo q of g**1, g**2, g**3, ..., g**(q-1) must then be a permutation of 1, 2, 3, ..., (q-1).) Denote (q-1)/n by r. Let T[i], i=1, 2, 3, ..., n, denote the least residues modulo q of g**i, g**(i+n), g**(i+2n), g**(i+3n), ..., g**(i+(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. (The brackets "[]" denote subscripts and the brackets "{}" denote sets.) Let s[i] denote the number of consecutive integers in T[i]. For example, 2 is a primitive root of 13, so for q=13, n=3, and g=2, T[1]={2, 3, 11, 10}, T[2]={4, 6, 9, 7}, T[3]={8, 12, 5, 1}, s[1]=2, s[2]=1, and s[3]=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 g[1] is another primitive root of q, then g[1]=g**h(mod q) where h and q-1 are relatively prime. The least residues modulo q of g**i, g**(i+n), g**(i+2n), g**(i+3n), ..., g**(i+(r-1)n) are in some order the least residues modulo q of g[1]**j, g[1]**(j+n), g[1]**(j+2n), g[1]**(j+3n), ..., g[1]**(j+(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 T[1]={6, 9, 7, 4}, T[2]={10, 2, 3, 11}, and T[3]={8, 12, 5, 1} in this case. The T[1] set for g=2 maps to the T[2] set for g=6 and the T[2] set for g=2 maps to the T[1] set for g=6 [this corresponds to k=2]. The T[n] set is always the same no matter which primitive root is used.)
The least residues modulo q of g**i, g**(i+n), g**(i+2n), g**(i+3n), ..., g**(i+(r-1)n) are the roots of the congruence x**((q-1)/n)=y(mod q), 0<x<q, y**n=1(mod q), 0<y<q. This is another way of interpreting the sets T[1], T[2], T[3], ..., T[n]. If n=2, the set T[1] is said to consist of the quadratic non-residues of q, and the set T[2] is said to consist of the quadratic residues of q. (If n>2, the set T[n] 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 INTEGERS IN A SET
Theorems concerning s[1], s[2], s[3], ..., s[n] will now be stated. Proofs of the theorems are not difficult but are fairly lengthy and will be omitted. This is not a major loss since the theorems are of moderate interest. Let a, b, and c be integers.
(1) a**n+b**n=c**n(mod q), q=1(mod n), q does not divide abc, has a solution if and only if s[n] is not equal to 0.
(2) s[1]+s[2]+s[3]+...+s[n]=r-1.
(3) If r is even, exactly one of s[i] is odd.
(4) If r is odd and n is even, s[i]=s[i+n/2], i=1, 2, 3, ..., n/2.
(5) If n=2 and r is even, s[1]=s[2]+1.
(6) If 6 does not divide r and 2**r is not congruent to 1 modulo q, then 6 divides s[n]. If 6 divides r and 2**r is not congruent to 1 modulo q, then s[n]=2(mod 6). If 6 does not divide r and 2**r=1(mod q), then s[n]=3(mod 6). If 6 divides r and 2**r=1(mod q), then s[n]=5(mod 6).
The following is a brief explanation of Theorem (6). Let x**(-1) denote an integer such that x(x**(-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 x**2-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 x**2-x+1=0(mod q), 0<x<q). x**2-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 a, b, and c are integers such that a**p+b**p=c**p(mod q), then q divides abc, and (2) p is not congruent to the pth power of an integer modulo q. Then there are no solutions of a**p+b**p=c**p, 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 also a prime, then there are no solutions of a**p+b**p=c**p, p does not divide abc. Theorem (1) above can be used to easily demonstrate this. If n is an odd prime and q=2n+1 is a prime, then S[n]={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 the determinant of 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 S[n] 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 s[1], s[2], s[3], ..., s[n]. Some empirical results are;
(1) If q<40000, n=3, r is a square, and 2**r is not congruent to 1 modulo q, then s[1]-s[2]=s[2]-s[3] (or s[2]-s[1]=s[1]-s[3] for some other primitive root of q).
(2) If q<40000 and n=3, then s[1]-s[2]=s[2]-s[3] (or s[2]-s[1]=s[1]-s[3]) only if r is a square.
(3) If q<40000, n=3, r is a square, and 2**r=1(mod q), then s[3]-s[2]+2=s[1]-s[3].
(4) If q<40000 and n=3, then s[3]-s[2]+2=s[1]-s[3] only if r is a square.
(5) If q<40000 and n=3, then s[1]=s[3] (or s[2]=s[3]) only if r/2 is odd.
(6) If q<40000 and n=3, then s[1] is not equal to s[2].
(7) If q<40000, n=4, and r is an odd square, then s[1]=s[2]=s[3]=s[4].
(8) if q<40000 and n=4, then s[1]=s[2]=s[3]=s[4] only if r is an odd square.
(9) If q<40000, n=4, and r is even, then s[1]-s[2]=s[2]-s[3].
(10) If q<40000, n=6, r is even, and 2**(2r) is not congruent to 1 modulo q, then s[1]=s[3]=s[4] (or s[2]=s[3]=s[5] for some other primitive root of q).
(11) If q<40000, n=6, r is even, and 2**(2r)=1(mod q), then s[2]-s[3]=s[3]-s[4] and s[1]-s[2]=s[4]-s[5]=2(s[2]-s[3]) (or s[2]-s[3]=s[3]-s[4] and s[1]-s[2]=s[4]-s[5]=2(s[3]-s[4]) for some other primitive root of q).
(12) If q<40000, n=8, r is an odd square, and 2**(2r)=1(mod q), then s[1]=s[3]=s[5]=s[7] and s[2]=s[4]=s[6]=s[8].
(13) If q<40000 and n=8, then s[1]=s[3]=s[5]=s[7] and s[2]=s[4]=s[6]=s[8] only if r is an odd square.
(14) If q<40000, n=8, r is odd, and 2**(2r)=1(mod q), then s[1]=s[3] and s[5]=s[7].
(15) If q<40000, n=8, r is even, and 2**(2r) is not congruent to 1 modulo q, then s[1]=s[3]=s[5]=s[7].
(16) If q<40000, n=8, r is even, and 2**(2r)=1(mod q), then s[1]-s[3]=s[5]-s[7].
(17) If q<40000, n=10, r is even, and 2**(2r) is not congruent to 1 modulo q, then s[1]=s[6]=s[7] and s[3]=s[5]=s[8] (for some primitive root of q).
(18) If q<40000, n=10, r is even, and 2**(2r)=1(mod q), then s[1]-s[2]=s[8]-s[9]=s[6]-s[7] and s[2]-s[3]-s[7]+s[8]=-2(s[4]-s[5]-s[5]+s[6].
(19) If q<40000, n=10, r is odd, and 2**(2r)=1(mod q), then s[1]-s[2]=s[3]-s[4] and s[6]-s[7]=s[8]-s[9] (for some primitive root of q).
(20) If q<40000, n=10, r is odd, and 2**(2r) is not congruent to 1 modulo q, then s[1]-s[4]=s[4]-s[2] and s[6]-s[9]=s[9]-s[7] (for some primitive root of q).
(21) If q<40000, n=14, r is even, and 2**(2r) is not congruent to 1 modulo q, then s[1]=s[8] and s[5]=s[12] (for some primitive root of q).
That whether 2**r is congruent to 1 modulo q or not should have an effect on the s[1], s[2], s[3], ..., s[n] values is expected. That whether r is a square or not (when n=3, 4, or 8) should have an effect on these values is unexpected. Theory has been developed for cubic, quartic, and octic reciprocity. This raises the question of whether there is a connection between the properties of s[1], s[2], s[3], ..., s[n] and higher order reciprocity laws. (When n=2,there is a connection between the properties of s[1], s[2], s[3], ..., s[n] and the quadratic reciprocity law and this connection is provided via Perron's theorem.) Another reason for expecting there to be 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 T[1], T[2], T[3], ..., T[n] 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 lambda be a primitive pth root of unity. The principal Gaussian sum is SUM(j/p)(lambda**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 quadratic reciprocity law then follows from this. Excluded from the Quadratic Reciprocity Law is the fact that (2/p)=(-1)**[(p**2-1)/8]. This is called the Supplement to the Quadratic Reciprocity Law.
The generalization of the principal Gaussian sum for n>2 is straightforward; instead of multiplying powers of lambda by 1 or -1 (roots of x**2=1), powers of lambda are multiplied by powers of a primitive nth root of unity. For n=3, rho=e**[(2/3)pi*i]=(1/2)(-1+i*sqrt(3)) is a primitive nth root of unity. (The numbers tau=a+b*rho where a and b are rational integers are called the integers of the field k(rho). The norm of the integer a+b*rho is a**2-ab+b**2. An integer whose norm is a rational prime is a prime in k(rho). If tau=+1 or -1(mod 3), then tau is said to be primary.) For example, for p=13, n=3, and g=2 (a primitive root of p), the least residues modulo p of g**1, g**4, g**7, and g**10 are 2, 3, 11, and 10 and these powers of lambda are multiplied by 1, the least residues modulo p of g**2, g**5, g**8, and g**11 are 4, 6, 9, and 7, and these powers of lambda are multiplied by rho, and the least residues modulo p of g**3, g**6, g**9, and g**12 are 8, 12, 5, and 1, and these powers of lambda are multiplied by rho**2. The generalized Gaussian sum is then (rho**2)(lambda**1)+lamba**2+lambda**3+rho(lambda**4)+(rho**2)(lambda**5)+rho(lambda**6)+rho(lambda**7)+(rho**2)(lamdba**8)+rho(lambda**9)+lambda**10+lambda**11+(rho**2)(lambda**12). The cube of the generalized Gaussian sum is p*pi where pi is a primary prime in k(rho) having a norm of p. 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 if and only if p*pi[p] is a cube of an integer in k(rho) modulo q. Also, p is a rational cube modulo q if and only if q*pi[q] is a cube of an integer in k(rho) modulo p. Therefore q is a cube modulo p and p is a cube modulo q if and only if pi[p] is a cube of an integer (in k(rho)) modulo q and pi[q] is a cube of an integer (in k(rho)) modulo p. There is also a supplement to the cubic reciprocity law. For n=4, the generalized Gaussian sum would be similarly formed. The fourth power of this generalized Gaussian sum is p(pi**2) where pi is a prime in k(i) (i=sqrt(-1)) having a norm of p. 2 also has a quartic nature.
PERRON'S THEOREM
As previously mentioned, Perron's theorem is sometimes used to help prove the quadratic reciprocity law. Perron's theorem is: (1) Suppose p=4k-1. Let r[1], r[2], r[3], ..., r[2k] be the 2k quadratic residues modulo p together with 0, and let a be a number relatively prime to p. Then among the 2k numbers r[i]+a, there are k residues (possibly including 0) and k non-residues. (2) Suppose p=4k-1. Let n[1], n[2], n[3], ..., n[2k-1] be the 2k-1 non-residues, and let a be prime to p. Then among the 2k-1 numbers n[i]+a, there are k residues (possibly including 0) and k-1 non-residues. (3) Suppose p=4k+1. Among the 2k+1 numbers r[i]+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, n[i]+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 of T[1] and T[2].
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) where a congruence symbol is usually used instead of the equal sign), (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 x**(q-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 g**d is not congruent to 1 modulo q for any natural number d less than q-1 (there always exist primitive roots). (x**(p-1), e.g., denotes x to the (p-1)th power.)
THE PARTITIONING
Let g be a primitive root of q. The least residues modulo q of g**1, g**2, g**3, ..., g**(q-1) are in some order 1, 2, 3, ..., (q-1). (If g**i=g**j(mod q), 1<=i<=q-1, 1<=j<=q-1, j<i, then q**(i-j)=1(mod q), 1<=(i-j)<q-1, in contradiction of the definition of a primitive root. The least residues modulo q of g**1, g**2, g**3, ..., g**(q-1) must then be a permutation of 1, 2, 3, ..., (q-1).) Denote (q-1)/n by r. Let T[i], i=1, 2, 3, ..., n, denote the least residues modulo q of g**i, g**(i+n), g**(i+2n), g**(i+3n), ..., g**(i+(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. (The brackets "[]" denote subscripts and the brackets "{}" denote sets.) Let s[i] denote the number of consecutive integers in T[i]. For example, 2 is a primitive root of 13, so for q=13, n=3, and g=2, T[1]={2, 3, 11, 10}, T[2]={4, 6, 9, 7}, T[3]={8, 12, 5, 1}, s[1]=2, s[2]=1, and s[3]=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 g[1] is another primitive root of q, then g[1]=g**h(mod q) where h and q-1 are relatively prime. The least residues modulo q of g**i, g**(i+n), g**(i+2n), g**(i+3n), ..., g**(i+(r-1)n) are in some order the least residues modulo q of g[1]**j, g[1]**(j+n), g[1]**(j+2n), g[1]**(j+3n), ..., g[1]**(j+(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 T[1]={6, 9, 7, 4}, T[2]={10, 2, 3, 11}, and T[3]={8, 12, 5, 1} in this case. The T[1] set for g=2 maps to the T[2] set for g=6 and the T[2] set for g=2 maps to the T[1] set for g=6 [this corresponds to k=2]. The T[n] set is always the same no matter which primitive root is used.)
The least residues modulo q of g**i, g**(i+n), g**(i+2n), g**(i+3n), ..., g**(i+(r-1)n) are the roots of the congruence x**((q-1)/n)=y(mod q), 0<x<q, y**n=1(mod q), 0<y<q. This is another way of interpreting the sets T[1], T[2], T[3], ..., T[n]. If n=2, the set T[1] is said to consist of the quadratic non-residues of q, and the set T[2] is said to consist of the quadratic residues of q. (If n>2, the set T[n] 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 INTEGERS IN A SET
Theorems concerning s[1], s[2], s[3], ..., s[n] will now be stated. Proofs of the theorems are not difficult but are fairly lengthy and will be omitted. This is not a major loss since the theorems are of moderate interest. Let a, b, and c be integers.
(1) a**n+b**n=c**n(mod q), q=1(mod n), q does not divide abc, has a solution if and only if s[n] is not equal to 0.
(2) s[1]+s[2]+s[3]+...+s[n]=r-1.
(3) If r is even, exactly one of s[i] is odd.
(4) If r is odd and n is even, s[i]=s[i+n/2], i=1, 2, 3, ..., n/2.
(5) If n=2 and r is even, s[1]=s[2]+1.
(6) If 6 does not divide r and 2**r is not congruent to 1 modulo q, then 6 divides s[n]. If 6 divides r and 2**r is not congruent to 1 modulo q, then s[n]=2(mod 6). If 6 does not divide r and 2**r=1(mod q), then s[n]=3(mod 6). If 6 divides r and 2**r=1(mod q), then s[n]=5(mod 6).
The following is a brief explanation of Theorem (6). Let x**(-1) denote an integer such that x(x**(-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 x**2-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 x**2-x+1=0(mod q), 0<x<q). x**2-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 a, b, and c are integers such that a**p+b**p=c**p(mod q), then q divides abc, and (2) p is not congruent to the pth power of an integer modulo q. Then there are no solutions of a**p+b**p=c**p, 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 also a prime, then there are no solutions of a**p+b**p=c**p, p does not divide abc. Theorem (1) above can be used to easily demonstrate this. If n is an odd prime and q=2n+1 is a prime, then S[n]={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 the determinant of 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 S[n] 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 s[1], s[2], s[3], ..., s[n]. Some empirical results are;
(1) If q<40000, n=3, r is a square, and 2**r is not congruent to 1 modulo q, then s[1]-s[2]=s[2]-s[3] (or s[2]-s[1]=s[1]-s[3] for some other primitive root of q).
(2) If q<40000 and n=3, then s[1]-s[2]=s[2]-s[3] (or s[2]-s[1]=s[1]-s[3]) only if r is a square.
(3) If q<40000, n=3, r is a square, and 2**r=1(mod q), then s[3]-s[2]+2=s[1]-s[3].
(4) If q<40000 and n=3, then s[3]-s[2]+2=s[1]-s[3] only if r is a square.
(5) If q<40000 and n=3, then s[1]=s[3] (or s[2]=s[3]) only if r/2 is odd.
(6) If q<40000 and n=3, then s[1] is not equal to s[2].
(7) If q<40000, n=4, and r is an odd square, then s[1]=s[2]=s[3]=s[4].
(8) if q<40000 and n=4, then s[1]=s[2]=s[3]=s[4] only if r is an odd square.
(9) If q<40000, n=4, and r is even, then s[1]-s[2]=s[2]-s[3].
(10) If q<40000, n=6, r is even, and 2**(2r) is not congruent to 1 modulo q, then s[1]=s[3]=s[4] (or s[2]=s[3]=s[5] for some other primitive root of q).
(11) If q<40000, n=6, r is even, and 2**(2r)=1(mod q), then s[2]-s[3]=s[3]-s[4] and s[1]-s[2]=s[4]-s[5]=2(s[2]-s[3]) (or s[2]-s[3]=s[3]-s[4] and s[1]-s[2]=s[4]-s[5]=2(s[3]-s[4]) for some other primitive root of q).
(12) If q<40000, n=8, r is an odd square, and 2**(2r)=1(mod q), then s[1]=s[3]=s[5]=s[7] and s[2]=s[4]=s[6]=s[8].
(13) If q<40000 and n=8, then s[1]=s[3]=s[5]=s[7] and s[2]=s[4]=s[6]=s[8] only if r is an odd square.
(14) If q<40000, n=8, r is odd, and 2**(2r)=1(mod q), then s[1]=s[3] and s[5]=s[7].
(15) If q<40000, n=8, r is even, and 2**(2r) is not congruent to 1 modulo q, then s[1]=s[3]=s[5]=s[7].
(16) If q<40000, n=8, r is even, and 2**(2r)=1(mod q), then s[1]-s[3]=s[5]-s[7].
(17) If q<40000, n=10, r is even, and 2**(2r) is not congruent to 1 modulo q, then s[1]=s[6]=s[7] and s[3]=s[5]=s[8] (for some primitive root of q).
(18) If q<40000, n=10, r is even, and 2**(2r)=1(mod q), then s[1]-s[2]=s[8]-s[9]=s[6]-s[7] and s[2]-s[3]-s[7]+s[8]=-2(s[4]-s[5]-s[5]+s[6].
(19) If q<40000, n=10, r is odd, and 2**(2r)=1(mod q), then s[1]-s[2]=s[3]-s[4] and s[6]-s[7]=s[8]-s[9] (for some primitive root of q).
(20) If q<40000, n=10, r is odd, and 2**(2r) is not congruent to 1 modulo q, then s[1]-s[4]=s[4]-s[2] and s[6]-s[9]=s[9]-s[7] (for some primitive root of q).
(21) If q<40000, n=14, r is even, and 2**(2r) is not congruent to 1 modulo q, then s[1]=s[8] and s[5]=s[12] (for some primitive root of q).
That whether 2**r is congruent to 1 modulo q or not should have an effect on the s[1], s[2], s[3], ..., s[n] values is expected. That whether r is a square or not (when n=3, 4, or 8) should have an effect on these values is unexpected. Theory has been developed for cubic, quartic, and octic reciprocity. This raises the question of whether there is a connection between the properties of s[1], s[2], s[3], ..., s[n] and higher order reciprocity laws. (When n=2,there is a connection between the properties of s[1], s[2], s[3], ..., s[n] and the quadratic reciprocity law and this connection is provided via Perron's theorem.) Another reason for expecting there to be 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 T[1], T[2], T[3], ..., T[n] 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 lambda be a primitive pth root of unity. The principal Gaussian sum is SUM(j/p)(lambda**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 quadratic reciprocity law then follows from this. Excluded from the Quadratic Reciprocity Law is the fact that (2/p)=(-1)**[(p**2-1)/8]. This is called the Supplement to the Quadratic Reciprocity Law.
The generalization of the principal Gaussian sum for n>2 is straightforward; instead of multiplying powers of lambda by 1 or -1 (roots of x**2=1), powers of lambda are multiplied by powers of a primitive nth root of unity. For n=3, rho=e**[(2/3)pi*i]=(1/2)(-1+i*sqrt(3)) is a primitive nth root of unity. (The numbers tau=a+b*rho where a and b are rational integers are called the integers of the field k(rho). The norm of the integer a+b*rho is a**2-ab+b**2. An integer whose norm is a rational prime is a prime in k(rho). If tau=+1 or -1(mod 3), then tau is said to be primary.) For example, for p=13, n=3, and g=2 (a primitive root of p), the least residues modulo p of g**1, g**4, g**7, and g**10 are 2, 3, 11, and 10 and these powers of lambda are multiplied by 1, the least residues modulo p of g**2, g**5, g**8, and g**11 are 4, 6, 9, and 7, and these powers of lambda are multiplied by rho, and the least residues modulo p of g**3, g**6, g**9, and g**12 are 8, 12, 5, and 1, and these powers of lambda are multiplied by rho**2. The generalized Gaussian sum is then (rho**2)(lambda**1)+lamba**2+lambda**3+rho(lambda**4)+(rho**2)(lambda**5)+rho(lambda**6)+rho(lambda**7)+(rho**2)(lamdba**8)+rho(lambda**9)+lambda**10+lambda**11+(rho**2)(lambda**12). The cube of the generalized Gaussian sum is p*pi where pi is a primary prime in k(rho) having a norm of p. 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 if and only if p*pi[p] is a cube of an integer in k(rho) modulo q. Also, p is a rational cube modulo q if and only if q*pi[q] is a cube of an integer in k(rho) modulo p. Therefore q is a cube modulo p and p is a cube modulo q if and only if pi[p] is a cube of an integer (in k(rho)) modulo q and pi[q] is a cube of an integer (in k(rho)) modulo p. There is also a supplement to the cubic reciprocity law. For n=4, the generalized Gaussian sum would be similarly formed. The fourth power of this generalized Gaussian sum is p(pi**2) where pi is a prime in k(i) (i=sqrt(-1)) having a norm of p. 2 also has a quartic nature.
PERRON'S THEOREM
As previously mentioned, Perron's theorem is sometimes used to help prove the quadratic reciprocity law. Perron's theorem is: (1) Suppose p=4k-1. Let r[1], r[2], r[3], ..., r[2k] be the 2k quadratic residues modulo p together with 0, and let a be a number relatively prime to p. Then among the 2k numbers r[i]+a, there are k residues (possibly including 0) and k non-residues. (2) Suppose p=4k-1. Let n[1], n[2], n[3], ..., n[2k-1] be the 2k-1 non-residues, and let a be prime to p. Then among the 2k-1 numbers n[i]+a, there are k residues (possibly including 0) and k-1 non-residues. (3) Suppose p=4k+1. Among the 2k+1 numbers r[i]+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, n[i]+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 of T[1] and T[2].
