Sequences from Quadratic Residues (Part IV)

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.

This page, however, will deal with p as composite (consisting of two odd primes) and will note the differences between sequences generated from prime and composite p.

Sequences Derived from x

The first sequence I will be discussing is derived according to details in Part I and are values obtained from the web page of B. Ikenaga on Quadratic Residues where he calculates the first four lowest positive values for x using the Chinese Remainder Theory. The web page gives details into calculating the x values of the composite number 91 comprised of the two odd primes 7 and 13 and having an r value of 79. Using the difference, Δ = ± p, to generate each prior and subsequent term in the sequence as was shown in Part I is no longer feasible here since p is now composite. Instead four Δ differences are present with two being identical as shown in row one. The partial sequence is shown in Table I, row two, showing the first group of four terms followed by a second group of four terms.

Taking the values supplied by Ikenaga for x of 25, 38, 54 and 66 the following four Δ values (13, 15, 13, 50) were obtained as differences between terms in row two. Importantly, the last Δ term, 50, was found to be a term connecting the first four x terms to the next subsequent x values. In addition, the four Δ terms appear to be composed of a nested pair where the sum of the inner pair equals 28 and the sum of the outer pair equals 63. At the moment it's difficult to determine which nested numbers pair up but it will be shown in Part IVa that the inner/outer nesting may be the correct one.

These two nested values, 28 and 63, are all that are required to generate the sequence in row four of Table I using these two numbers in either of their ± form. In addition, although x in Table I is shown as positive it's just as likely to be −25 since the square root of x² is ±x.

Previously it was shown in Part I that the sum of a group of two x terms in the |x| row of the table followed the pattern p, 3p, 5p, 7p.... However, when p is composite the number of terms doubles as well the sum of these terms. For instance, for a composite p consisting of two primes p₁×p₂, four terms per group in the sequence are summed and the pattern now becomes 2p, 6p, 10p, 14p.... Thus doubling the number of terms per group doubles the pattern of sums. This can be seen by summing up the first and the second group of four terms in row 2 of Tables I and II and comparing their values.

Thus, given the four x terms, we can generate the sequence in row two. However, is it possible to generate the three other positive xs 38, 53 and 66 given only x = 25? Part IVa will show that the three other values belonging to x as well as the the two Δ values of 28 = (15+13) and 63 = (13+50) may be obtained using the a new algorithm in lieu of the Chinese Remainder Theory.

As a second example, and using the Chinese Remainder Theory with p = 91 and r = 88, we obtain the first four positive terms which we expand into an eight term sequence using the four Δ values (see row 2, Table II. This time, as shown in the third row, the inner pair Δ differences sum up to 39 = (14+25) and the outer pair to 52 = (14+38).

Go to Part IVa for New Algorithms for Quadratic Residues. Go back to Part III. Go to homepage.