Expanded Algorithm Involving Quadratic Residues (Part Ib)

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

This is a continuation of Part Ia where the composite number 105 is used to construct the tables according to the method of Part Ia. The values of x and r were set at 17 and 79, respectively, providing all the xs belonging to that residue (shown in bold). These xs are listed as follows as ± pairs (from square root of x).

For instance, there are two or more r values for the majority of rs except for r = 30 in Table I and r = 49 in Table II (shown in red). The former correspond to four or more xs having the same r value while the latter correspond to only two x values per x. For p = 105 there are 44 xs that behave as nested pairs and eight which do not. The eight lowest x valuess (as absolute values) and their correponding r values in tuple format are:

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

To employ the algorithm one starts with an x which has been calculated from a known r, in this case x=17 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.

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 15 or multiples of 15, i.e., according to their p1 values of 7 and 15, respectively. We can change the values of x to 14 and r to 91 and use a JS computer program to perform the calculations. All the r values are different from those obtained in Table I, where the non nested 14th row, is (105,0), a tuple not listed above. So the method not only provides the tuples on the list but also the one, where x² = 105² ≡ 0 (mod 105) .

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 105 − x_i, the lowest initial x.

Note that the number of x values are less than p = 105 and that any values greater than p correspond to those xs in the next highest group.

Go to Part Ic Expanded Algorithm Involving Quadratic Residues. Go back to Part Ia. Go to homepage.