International Journal of Mathematics and Mathematical Sciences
Volume 10 (1987), Issue 1, Pages 113-123
doi:10.1155/S0161171287000140
On the complementary factor in a new congruence algorithm
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.
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.