International Journal of Mathematics and Mathematical Sciences
Volume 10 (1987), Issue 1, Pages 113-123

On the complementary factor in a new congruence algorithm

Peter Hilton1 and Jean Pedersen2

1Department of Mathematical Sciences, University Center at Binghamton, State University of New York, Binghamton 13901, New York, USA
2Department of Mathematics, Santa Clara University, Santa Clara 95053, CA, USA

Received 17 April 1986

Copyright © 1987 Peter Hilton and Jean Pedersen. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


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 a1a2ark1k2kr ϵ 1 ϵ 2 ϵ rq1q2qr 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.