New Algorithm Involving Quadratic Residues (Part IVa)

Sequences of x from known Quadratic Residues

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 only composite p.

Algorithm and Sequences

The x using known quadratic residues in Part IV were generated using the Chinese Remainder Theory on the web page of B. Ikenaga on Quadratic Residues. A newer algorithm has been found which basically does the same using an ordered pair to generate the x values as ± pairs. We start by setting p = 91 into the product of two odd primes (13×7) and generate Table I where:

We can find x either via the Chinese Remainder Theory or using the equation x² = r + pq. For r = 79 we can try various values of q and if we're lucky q can be low (in this case q = 6) whereby x² = 79 + 91(6) = 625 = 25². A third option is to generate the number using a simple computer program if q appears to be out of reach.

We set up Table I according to the instructions and find that x = ±38 and ±53 are the only values besides 25 and a fourth number = 66. In addition, we could have employed x = −25 just as well since both are valid values for x. Moreover, when the ordered pairs are reversed the x values obtained (in red) are not congruent to 79(mod 91). The values in red, however, are values having different x values and it will be shown in Part Ia and Part Ib that the whole table can be filled with xs of different r values so that the method can be extended to generate a host of xs without knowing r.

We can take the values obtained in Table I and generate a sequence by placing the negative numbers to the left and the positive to the right of x = 25 in Table II, where the negative numbers decrease without bound and the positives increase without bound. The Δ₁ values in row one take on the corresponding ordered pair values (either ±) from Table I. If we take the absolute values of the xs in row two of Table II we can produce the sequence in row four starting with the lowest positive x. Since all terms in row four are positive the last term in the group could also have been generated as a positive value from 91 − 25. Moreover, the fourth Δ₂ value in row four, is obtained by subtracting the sum of 13 + 15 + 13 from 91 affording 50, a connecting number that links adjacent groups. In addition, as stated in Part IV, the pattern for the sums of four terms/group in this sequence is p,3p,5p...

We can find x either via the Chinese Remainder Theory or using the equation x² = r + pq. For r = 88 we find that q = 3 whereby x² = 88 + 91(3) = 361 = 19². Repeating the algorithm for x = 19 affords x = ±33 and ±58:

Repeating the process as above the x values ±33 and ±58 along with 19 and ±72 were inserted into Table IV giving the sequences on row two and four.

A good thing about this algorithm is that it allows us to use the same tables whenever p is kept constant and the least positive x is varied.

Go to Part IVb Algorithm and Sequences from Quadratic Residues. Go back to Part IV. Go to homepage.