Sequences from Quadratic Residues (Part I)

A Method for Generating New Sequences

An integer r is called a quadratic residue modulo p if it is congruent to a perfect square modulo p:

with the number of residues for a given prime given by the equation (p − 1)/2 where the one value x² = 0 is removed before division by 2.

According to the formula when p = 11 the number of residues is 5 and we depict the corresponding x and r values from the residues in Table I:

Let us say that each column of numbers corresponds to either of three type of expressions:

where q is the quotient and the values of r, r + p and r + pq in the above three types are perfect squares. Types I and II are easily determined. With large primes x² can be difficult to find in Type III cases especially if q is unknown. However, a method named The Method of Excludents for obtaining x² is known and is described in in pages 207-208 of Recreations in the Theory of Numbers by Albert H. Beiler (1966). In addition, a six line description in mathworld.wolfram.com-Excludents basically defines the method.

To determine the value of each type we take the square roots of p and 2p and use a floor function (also known as greatest integer) to convert the values to integers. Using p = 11 the following results are obtained:

where the symbol ⌊y⌋ signifies a floor function, i.e, the largest integer less than or equal to y and where y in this case is √p or √2p.
Accordingly, there are three numbers of Type I, one of Type II and one of Type III when p = 11.

There are three exceptions, however, when p are 3, 5 and 7, respectively:

Sequences Derived from the x²

A sequence can be derived from each p with its corresponding r by (1) taking as the first element the lowest positive x₀ and adding p to each subsequent element and −p to all prior elements as in rows 1 and 2 of Table II, then (2) taking the absolute values of |x| and rearranging with lowest to highest as in row four. Row three consists of two Δ values (Δ₁ and Δ₂) which are to be added to either of two adjacent elements and where Δ₁ + Δ₂ = p. In addition, in row four the sum of pairs starting with the first pair x₀ and x_-1 is equal to np, where n takes odd values, 1,3,5,.... Consequently, each element squared in the general sequence of table II is congruent to r (mod p), i.e., leaves no remainder on division by p. :

Using a specific number for instance p = 11 having an r value of 1 we can generate Table III, where row 2 gives a sequence based on Δ = 11 and row 4 the rearranged sequence with Δ values of 9 and 2.

The four other sequences |x| based on r values of 4, 9, 5 and 3 are shown in Table IV in that particular order:

The methods employed here also produce similar results with larger primes, viz, 1193 and 135287 see Part II.

Go back to homepage.