On the complementary factor in a new congruence algorithm (Q1088705)

In [ibid. 9, 245-251 (1986; Zbl 0592.10005)] the authors described an algorithm for determining the quasi-order, \(Q_ t(b)\), of t mod b, where t and b are mutually prime. Here \(Q_ t(b)\) is the smallest positive integer n such that \(t^ n\equiv \pm 1 mod b\), and the algorithm determined the sign \((-1)^{\epsilon}\), \(\epsilon =0,1\), on the right of the congruence. In this sequel we determine the complementary factor F such that \(t^ n-(-1)^{\epsilon}=bF\), using the algorithm rather that b itself. Thus the algorithm yields, from knowledge of b and t, a rectangular array with \(a_ i\), \(k_ i\), \(\epsilon_ i\), \(q_ i\), \(i=1,...,r\), in the first, second, third and forth row, respectively. The second and third rows of this array determine \(Q_ t(b)\) and \(\epsilon\) ; and the last 3 rows of the array determine F. If the first row of the array is multiplied to F, we obtain a canonical array, which also depends only on the last 3 rows of the given array; and we study its arithmetical properties.