New Algorithm Involving Quadratic Residues (Part IVd)

xs from Even p

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 x Values

This section is a continuation of Part IVc with r = 393 and using an even number p = 1564 where p may be factored as either 2(782) or 4(391). If p₁ = 782 then x = 317² = 393 + 728(128) and if p₂ = 391 then x² = 317² = 393 + 391(257) the only difference being in the quotients. It will be shown that the results instead of returning four x terms will return eight where the latter four x terms sum to 3×p = 4692 as opposed to the former p = 1564. In addition, since the factors for 931 are 17 and 21, it will be shown below that 393(mod 391) ≡ 2(mod 391) and will exhibit additional x values along with those found for 393(mod 1564).

Thus the values to be distributed directly into an ordered pair (Table IIa, column 2) consists of 2 multiplied by a composite number p₁ (as a sum of numbers) or 4 multiplied by a prime p₂ (as a sum of numbers) (see column 1, Table IIa). The only table values that are congruent to 393(mod 1564) and less than 1564 are:

These values are obtained by applying the algorithm to 4(391) and 391(4), where the second number is composed of a sum totaling that number and using the initial value of x = 317 (see Table I):

As one can see all the x terms in one form or the other (positive/negative) are produced.

Table of Valid Pairs

Table IIa shows a list of all the valid terms of p = 1564, r = 393. Column two shows the ordered pairs that are required to produce each term in column 2 and 3 when 317 is added to a or 317 subtracts b. If the p_n (= 2 or 4) divides a and b of the ordered pair, only those numbers that are congruent to 0(mod p_n) are present in the tables where p_n is 2 or p_n is 4. Note o denotes present and × not present in the tables consisting of each p_n (Tables IIb and IIc). Note that in column one of Table IIa, n may be 1 or 2.

Note that Table IIc corresponds to the left half of Table I.

Thus, while all the x values are present in Table Ia they are split up so that half go into Table IIa and the opposite x values go into Table IIb. Each table can, therefore, reproduce all the x values in either of their ± forms. So when a search is done using p_n using either 1 or 2 for the value of n one is assured that half of all the x terms will be captured. To get the other half just flip the polarities of each x term obtained.

x values for p = 391

Since 391 = 17×23 Table III will consist 23(17) on the left and 17(23) on the right. Using 2(mod 391) as mentioned earlier and an initial x of 28 obtained by inspection from x² = 28² = 2 + 391(2).

where the only values in common with 393(mod 1564) are ±317, ±363, ±419 and ±465.

These values are obtained by applying the algorithm to 4(391) and 391(4), where the second number is composed of a sum totaling that number and using the initial value of x = 28 (see Table III):

The result besides giving all the x values as positive or negative, also produces the next higher value of 419 in the sequence of numbers.

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