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 x

The least residues modulo q of g

(1) a

(2) s

(3) If r is even, exactly one of s

(4) If r is odd and n is even, s

(5) If n=2 and r is even, s

(6) If 6 does not divide r and 2

The following is a brief explanation of Theorem (6). Let x

(1) If q<40000, n=3, r is a square, and 2

(2) If q<40000 and n=3, then s

(3) If q<40000, n=3, r is a square, and 2

(4) If q<40000 and n=3, then s

(5) if q<40000 and n=3, then s

(6) If q<40000 and n=3, then s

(7) If q<40000, n=4, and r is an odd square, then s

(8) If q<40000 and n=4, then s

(9) If q<40000, n=4, and r is even, then s

(10) If q<40000, n=6, r is even, and 2

(11) If q<40000, n=6, r is even, and 2

(12) If q<40000, n=8, r is an odd square, and 2

(13) If q<40000 and n=8, then s

(14) If q<40000, n=8, r is odd, and 2

(15) If q<40000, n=8, r is even, and 2

(16) If q<40000, n=8, r is even, and 2

(17) If q<40000, n=10, r is even, and 2

(18) If q<40000, n=10, r is even, and 2

(19) If q<40000, n=10, r is odd, and 2

(20) If q<40000, n=10, r is odd, and 2

(21) If q<40000, n=14, r is even, and 2

From Theorem (6), you would expect the condition 2

The generalization of Gaussian sums for n>2 is straightforward; instead of multiplying powers of ζ by 1 or -1 (roots of x

For n=4, the generalized Gaussian sum would be similarly formed. The fourth power of this generalized Gaussian sum is pπ

When a=1, Perron's theorem concerns the number of consecutive elements in T

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 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}≠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 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 g^{i-j}≡1(mod q), 1≤i-j<q-1, in contradiction to 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. 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 Elements 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. Let a, b, and c be integers relatively prime in pairs.(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}≠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}≠1(mod q), then 6 divides s_{n}. If 6 divides r and 2^{r}≠1(mod 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 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 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^{p}+b^{p}≡c^{p}(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 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 a prime, then there is no solution of a^{p}+b^{p}=c^{p}, 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 T_{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 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 T_{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 (for n≤16) are;(1) If q<40000, n=3, r is a square, and 2

^{r}≠1(mod 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}≠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}≠1(mod 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}≠1(mod 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}≠1(mod 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_{3}-s_{4}=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}≠1(mod 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}≠1(mod q), then s_{1}=s_{8}and s_{5}=s_{12}(for some primitive root of q).From Theorem (6), you would expect the condition 2

^{r}≡1(mod q) (or the condition 2^{r}≠1(mod q)) to have an effect on the s_{i}values. It's surprising that r being a square has an effect on the s_{i}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 s_{i}values and higher order reciprocity. (When n=2, there is a connection between the s_{i}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 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 ζ 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 x

^{2}=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 a^{2}-ab+b^{2}. 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 g^{1}, g^{4}, g^{7}, and g^{10}are 2, 3, 11, and 10, and these powers of ζ 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 ζ are multiplied by ρ, 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 ζ 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 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 of 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. 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 in T

_{1}and T_{2}. (Perron's theorem may look complicated, but it has no more content than Theorems (4) and (5).)**Software**

The above propositions were confirmed using MSVC++™. Readers may copy and modify the software in this section. No guarantee is made that it is error-free. Use testr to compute*s*values. A prime and primitive root look-up table used is input. Use test3r to test propositions for_{i}*n*=3. Use test4r to test propositions for*n*=4. Use test6r to test propositions for*n*=6. Use test8r to test propositions for*n*=8. Use test10r to test propositions for*n*=10. Use test14r to test propositons for*n*=14. A subroutine used is croots. Use gauss2 to compute the square of the Gaussian sum. Use gauss3 to compute the cube of the Gaussian sum. Use gauss4 to compute the fourth power of the Gaussian sum. Use solve3 to check cubic reciprocity. A prime and primitive root look-up table used is inputg.