On the complementary factor in a new congruence algorithm

Abstract

In an earlier paper the authors described an algorithm for determining the quasi-order, Qt(b), of tmodb, where t and b are mutually prime. Here Qt(b) is the smallest positive integer n such that tn=±1modb, and the algorithm determined the sign (−1) ϵ , ϵ =0,1, on the right of the congruence. In this sequel we determine the complementary factor F such that tn−(−1) ϵ =bF, using the algorithm rather that b itself. Thus the algorithm yields, from knowledge of b and t, a rectangular array a1a2…ark1k2…kr ϵ 1 ϵ 2… ϵ rq1q2…qr The second and third rows of this array determine Qt(b) and ϵ ; and the last 3 rows of the array determine F. If the first row of the array is multiplied by 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.

Keywords

• number theory
• quasi-order
• algorithm.