New Algorithm Involving Quadratic Residues (Part IVb)

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.

Algorithm and Tables

This section is a continuation of Part IVa with r = 79 and p = 105 comprised of the three odd primes 3, 5 and 7 and where x² = 79 + 105(2) = 17². While Part IVa used two tables of ordered pairs one for generating the two x values 33 and −53 and the other for the opposite values of −33 and 53. In this section, however, in order to cut down on duplication, only three sections in one table out of a possible six are all that are required. In addition, one table with only one section was all that was needed to produce all six numbers as positive or negative values.

Thus, setting up Table I according to the instructions layed out in Part IVa with slight differences, the distribution (Dstr) columns have been eliminated with the ordered pair acting as a "distributed" ordered pair. Plus the values to be distributed consist of a composite number (p₁p₂) multiplied by a prime (p₃) as a sum of numbers (see column 1, Table I). Thus, the only table values that are congruent to 79(mod 105) and less than 105 are:

Again to obtain the x values we add the initial value 17 to a, b, or c and subtract b, d or f from 62 as shown in the header in Table Ia.

I've chosen to set up four tables to depict the results. For instance in Table I, 15 is multiplied by a sum of numbers totaling to 7, while in the smaller Tables Ib, Ic and Id, the composite numbers 35, 21 and 15 are multiplied by their respective smaller primes 3, 5 and 7. Either way all values for x are depicted in the latter three tables whether they be positive or negative.

It will be shown in Part Ia and Part Ib that the whole tables 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.

Table of Valid Pairs

Table IIe shows a list of all the valid terms for the three smaller tables Ib thru Id, including the initial and final values in the first and last rows. Column one shows the ordered pairs that are required to produce each term in column 2 and 3 when 17 is added to a or 17 subtracts b. If the p₁ (= 3, 5 or 7) divides a and b of the ordered pair, only those numbers that are congruent to 0(mod p₁) are present in the tables where p₁ is the prime and p₂p₃ the composite. This not apply to the first ordered pair, however, since the first column number of each table start at one. Note o denotes present and × not present in the smaller four column table.

We can take the values obtained from either of the tables and generate a sequence by placing the negative numbers to the left of 17 and the positives to the right in Table II, where the former decreases and the latter increases without bound, respectively. One of the pair of values, 38 and −67, is converted into the pair 67 and −38 for use in Table II (note:x could take on positive or negative values in 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 is generated from 105 − 17. Moreover, the last Δ₂ value in row three is obtained by subtracting the sum of 15 + 6 + 14 + 1 + 14 + 6 + 15 from 105 affording the Δ₂ = 34, a connecting number that links adjacent groups. In addition, as stated in Part IV, the pattern for the sums of eight terms/group in this sequence is 4p,12p,20p...

A Second Example

The next example uses the equation x² = r + pq. For r = 99 we find that q = 6 whereby x² = 99 + 105(6) = 729 = 27². Repeating the algorithm for x = 99 affords x = ±48 and ±57 along with the initial value ±27 and the final value ±78 (from 105 − 27).

Note that only one section of the table was utilized giving only the two two values above congruent to 99(mod 105) along with the non table initial and final x values. In total four terms make up each group in the sequence.

Taking the xs from Table III and sequencing as was done above, we generate Table IV with the two sequences on rows two and four and the last Δ₂ = 54.

Go to Part IVc Algorithm and Sequences from Quadratic Residues. Go back to Part IVa. Go to homepage.