Finite Sequences from Quadratic Residues (Part III)

A Method for New Finite 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.

When a number is divided by p there are only p possible remainders including 0. Every integer, positive, negative or zero with its remainder modulo p is, therefore, partitioned into residue classes. Each residue is usually depicted as a number between 0 and m but may also be depicted as (r + m) where m is some multiple of p. However, the congruency, (r + m) ≡ r (mod p), is reduced back to r, a member of the same residue class modulo p.

Quadratic residues may be depicted as in Table I according to increasing r as shown for p = 23 where the first five rs are square numbers in ascending order while the next seven appear to be scattered at random. However, row 2 in Table I can also be depicted, as in row 3, with every r as ordered square numbers where the latter seven x² now range from 25 to 121 but are congruent to their respective seven latter r values in row 2. Not so random after all.

This page will show an alternative method for generating incremental values of r by adding an 2x + 1 terms to each r in order to to generate the next higher r term. Each 2x + 1 may be derived from an x in row 1 or by initially setting x to zero and incrementing each subsequent 2x + 1 term by 2. The sequence derived from rs is not arithmetic, i.e., having a common difference between terms, since the difference (Δ) between terms increases by two for the next addition. Before depicting this in Table II the following expressions which were defined in Part I shows that the numbers in Table I correspond to either of three types 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.

The number of values in each type is found by taking the square roots of p and 2p in the following expressions when p = 23:

Sequence of rs with p=23

Tables IIa and IIb show how to increment the x by using the expression 2x + 1 in row 3. We can increment 2x + 1 by initially setting x = 0 and incrementing its value by 2 or by setting the 2x + 1 using the x from the previous column. For example, r = 9 is found by adding the previous r = 4 to the Δ value of 5 in row three and then adding 2 to 5 to get the next Δ addend. Furthermore, as shown above when x = 5 the r value could be depicted as 2 or 25 depending on whether one adds Δ to the last Type I number r = 16 or retains the lower r = 2 as the new starting point, but keeping the Δ values the same. Since having all square rs is not the preferred way to go, the most preferable choice would be to use the lower r and do either of two things: Continue as in Tables IIa and IIb or proceed as in Table IIc.

In Table IIa we can start by adding the first 2x + 1 to 0 and generating all four r of Type I numbers. In the next step since the addition of Δ = 9 to 16 produces a perfect square. So we keep the original value of 2 (in red), producing a Type I and Type II discontinuity, but continue the addition of Δs until the calculation of the last r.

Although this method places every r of Type III number in ascending order we can, alternatively, set r ≡ 0 (mod 23) equal to −23 (mod 23) and use −23 as the initial r value to which the first Δ = 1 is added followed by further 2x + 1 additions as in Table IIc. A third option is to square each x from start and subtract 23. That would produce Table IIc in one fell swoop:

This then generates a finite sequence without the discontinuity between x = 4 and x = 5 as depicted in Table IIa. Note that all the − r values are congruent to x² (mod 23).

These new r values I will designate as r_n may also be obtained directly from x² as follows:

Thus we have an alternative way of forming the sequences by generating r_n from each x² and stringing together each value of r_n starting with x² = 0. Moreover, r_n produced in this manner is randomly and not sequentially generated.

Sequence of rs with p=1193

The second larger prime used in Part II, 1193, will be used as a second example in Tables IIIa, IIb and IIIc.

As before a discontinuity again occurs this time between x = 34 and x = 35. This discontinuity disappears upon setting r ≡ 0 (mod 1193) to r ≡ −1193 (mod 1193) as the initial r value as was done for p = 23. Note that these sequences do not end at x = 596 but can be continued indefinitely by adding increasing amounts of Δ to r. For instance, adding 1193, the next number in the arithmetic sequence of row three, to r = 354023, affords r = 353216 both of which are congruent to 895 (mod 1193). After x = 596 the r values are in descending order starting with 895 and decreasing to zero.

Again we may use the equation:

to generate all r_n values. The advantage of using the latter method is that Δ doesn't have to be explicitly spelled out but may be omitted from the table. However, the best option is to subtract 1193 from each x starting from x = 0. This would start the sequence at −1193 as in p = 23 example.

As an afterword we have been dealing with regular r values and with non regular (r + m) values which I have designated as r_n. In the first expression below, the latter r_n has been set equal to the right side of the first expression where p(q − 1) is the multiple m required for generating the incremental values of r with again q being the quotient. x² is then the value shown in the second expression where we add p to r_n.

Go to Part IV, Go back to Part II. Go back to homepage.