New Algorithm Involving Quadratic Residues (Part IVc)

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 IVb with r = 379 and p = 1155 comprised of the four odd primes 3, 5, 7 and 11 and where x² = 379 + 1155(3) = 62². While Part IVb used one table for the six ordered x pairs this section, however, will use five tables of two sections each, to generate the fourteen x values besides the initial and final values, for a total of 16 terms.

The first two tables consists of a composite number p₁p₂p₃ multiplied by a prime p₄ as a sum of numbers, while the latter three tables consists of composite numbers p₁p₂ multiplied by a prime p₃ as a sum of numbers. These are set up according to the instructions layed out in Part IVa, with the ordered pair acting as a "distributed" ordered pair, i.e., the composite numbers are distributed and the sum of terms are converted directly into an ordered pair. The initial positive value x is added to the first term of the ordered pair and subtracted from the second term of the ordered pair to obtain an x value. Both xs obtained in this manner must be congruent to 379 (mod 1155). Thus the only table values that are congruent to 379(mod 1155) and less than 1155 are:

Again to recapitulate to obtain the terms we add the initial value of 62 to a, b, or c and subtract b, d or f from 62 as shown in the headers.

The first two tables for p = 1155 consists of a p₁p₂p₃ multiplied by a p₄ with p₁p₂p₃ equal to 105 and 165 in Table Ia, and 231 and 385 in Table Ib.

The number of x terms obtained in Parts IVa and Part IVb were four and eight, respectively. If the number is based on 2ⁿ then the number of x terms could be as high as sixteen. Since only a total of ten values were obtained, eight (from the tables) and two non table terms. A further search using three sub tables consisting of a p₁p₂ multiplied by a p₃p₄ where p₁p₂ is equal to 55 and 35 in Table IIa, 15 and 21 in Table IIb and 33 and 77 in Table IIc provided six more x terms plus additional duplicate terms in red.

Table of Valid Pairs

It was shown in Part IVb that it is possible to have generate all the terms in one table. The same is possible with the larger number 1155. Column one of Table IId shows the ordered pairs, employed in all of the above tables, that are required to produce each term in column 2 and 3 when 62 is added to a or 62 subtracts b. If the p₁ (= 3, 5, 7 or 11) 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₃p₄ is the composite number.

For instance, when p₁ = 7 and (a,b) = (506,649) division of a or b by 7 leaves 2 and 5, respectively, as remainders. Therefore, x = 568 and −587, will not appear together as terms in Table IIe where p₁ = 7, although their exact opposites will. Thus, for p = 1155 the four tables composed of a single prime, p₁, multiplied by a composite number of three primes produces only 7×2 terms per table along with the initial and final terms in the first and last rows. Note that terms present in each subtable are labeled as o and terms not present as ×.

The terms in Table IIe run thru numbers 1 to 164 and give positions where the pair of terms are found starting at 7(20+145) thru 7(143+23) with the requisite term values taken from Table IId where o is in red. So all the terms except for the initial and final are to be found as a mix of positive and negative terms in a table constructed with p₁ = 7 as prime and a p_c composite number = 165, broken down into sums. Similar results are obtained from the other three p₁ primes.

Sequences from the Tables

The terms obtained from the tables along with the initial and final values were strung together in two sequences, one in which the negative terms were added to the left of 62 and the positive to the right in sequential order (see Table III rows two and four). Ten values, however, were converted to their opposite values before placement into the sequence. The second sequence was generated by taking the absolute values of all the x terms and stringing together each term in sequential order starting with the lowest positive x = 62 and proceeding to the highest, 1093 (in blue). By subtracting the first 14 Δ₂ values from 1155 we get the value of 124 which is used to connect to the next term 1217 and consequently higher x terms.

A JS program is used to confirm the values of each each term in the sequence. A JS text program is also avaiable for viewing.

And to conclude the Δ₁ terms shown in row five and six above can be interpreted as 1)Each equal to the sum of a nested pair of Δ₂ terms as shown in Table IV where the left Δ₂ term is added to the Δ₂ term to its right or as 2)A pair formed by hopscotching from one term to another in the left direction. Either description may be correct.

Go to Part IVd where p is an even number and, therefore, the initial and final values are indeed represened in the table.

Go back to Part IVb. Go to homepage.