Expanded Algorithm Involving Quadratic Residues (Part Ia)

Generation of many x and rs

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 Tables

In Part IVa I introduced the concept of a new algorithm that could be used in lieu of the Chinese Remainder Theory to find all the xs belonging to a known quadratic residue. There it was shown how to generate all the xs using ordered pairs (or tuples) using a new algorithm. Since then I have revised the method since the algorithm not only provides the xs in question but produces an entire group of xs from several different quadratic residues. I will show that all the residues generated appear to be related thru their factors. This can be shown in Tables I and II where the composite number is the same as the one used in Part IVa, p = 91, which is factored into the product of two odd primes (13×7):

The tables are set up according to the instructions in Part IVa with the addition of a residue (r) column at the end. In addition, column two was eliminated and the distributed numbers placed directly into the ordered pair. Employing x = 25 with its initial r value of 79 we obtain all the xs belonging to that residue (shown in bold). Moreover, I decided to modify the initial algorithm into one that includes xs that are generated that do not belong to the original x/r pair since this was not taken into account.

Tables I and II show that except for one row in each table all the r values are generated as nested pairs as shown in the picture of the r pairs of column 5, Table I:

For instance, there are two or more r values for every four numbers except for r = 65 in Table I and r = 14 in Table II (shown in red). The former correspond to four xs having the same r value in p = 91 while the latter correspond to only two x values per x. For p = 91 there are 36 xs that behave as nested pairs and nine which do not. The nine xs (as absolute values) and their correponding r value in tuple format:

Using the computer program below Table I and setting x = 1, r = 1, p1 = 1 and p = 91 gives all 91 possible values of x and r including the eight above. A table similar to those found on Part Ic would be the output.

The starting point of the algorithm is entering an x which has been calculated from a known r, in this case x=25 from r=79. Columns 3 and 4 are used to generate the new values of x from columns 1 and 2. The residues (r) in column five are calculated from the new xs in columns three and four. This method differs from row one in which we are given r to start. Importantly, it also differs from the Chinese Remainder Theory which requires previous knowledge of r. It's like putting the cart before the horse. Thus, the xs are calculated without having to know their r values, yet its important to perform their calculations at the end since it allows us to group all the possible combinations of xs via the use of nested pairs as was shown in the picture above.

Note that the difference between rs in Table I is 7 or multiples of 7 while those for Table II (except for rows 1 and 2) is 13 or multiples of 13, i.e., according to their p1 values of 7 and 13, respectively.

Computer Coded Example

We can change the values of x to 23 and r to 74 and make use of a JS computer program to perform the calculations. All the r values using these two initial x and r numbers are different from those obtained in Table I, while the non nested row is the fifth tuple in the list above, (26,39). A text version of this program is also being made available.

Summary of x and r Values

The absolute values of all the x values in Tables I and II, can be used to construct Table III where the xs are listed in ascending order based on their r values. The numbers in red correspond to those missing from Tables I and II and which may be calculated from 91 − x_i, the lowest initial x.

Note that the number of x values are less than p = 91 and that any values greater than p correspond to those xs in the next higher group (column 6). In order to show that an x value in red, such as x = 73, is actually present, one can rerun the computer program using the values of r = 51 and x_i = 18. This gives a different order of listing of the first six rows of r and x values from Table I, with the missing red x value on the first row.

Taking the absolute values of the xs in row one of Table III we can produce the sequence in Table IV along with the Δ (difference) between xs Since Δ must equal 91, the value of the last Δ is obtained by subtracting the sum of 13 + 15 + 13 from 91 affording 50, a connecting number that links to the higher groups which is where 116 fits in. Every r row in Table III can be treated in this manner to give sequences with different Δ values, as shown in Tables IV and V.

The upshot from these findings is that we can generate a host of x and r values from just the x=25/r=79 pair (for p = 91) and tables constructed from the corresponding factors of p.

Go to Part Ib Expanded Algorithm Involving Quadratic Residues. Go back to Part IV. Go to homepage.