A modular integer GCD algorithm

This paper describes the first algorithm to compute the greatest common divisor (GCD) of two n-bit integers using a modular representation for intermediate values U, V and also for the result. It is based on a reduction step, similar to one used in the accelerated algorithm [T. Jebelean, A generalization of the binary GCD algorithm, in: ISSAC '93: International Symposium on Symbolic and Algebraic Computation, Kiev, Ukraine, 1993, pp. 111–116; K. Weber, The accelerated integer GCD algorithm, ACM Trans. Math. Softw. 21 (1995) 111–122] when U and V are close to the same size, that replaces U by (U−bV)/p, where p is one of the prime moduli and b is the unique integer in the interval (−p/2,p/2) such that . When the algorithm is executed on a bit common CRCW PRAM with O(nlognlogloglogn) processors, it takes O(n) time in the worst case. A heuristic model of the average case yields O(n/logn) time on the same number of processors.     

Two efficient algorithms for the computation of ideal sums in quadratic orders

This paper deals with two different asymptotically fast algorithms for the computation of ideal sums in quadratic orders. If the class number of the quadratic number field is equal to 1, these algorithms can be used to calculate the GCD in the quadratic order. We show that the calculation of an ideal sum in a fixed quadratic order can be done as fast as in up to a constant factor, i.e., in where bounds the size of the operands and denotes an upper bound for the multiplication time of -bit integers. Using Schönhage-Strassen's asymptotically fast multiplication for -bit integers, we achieve

     

On v-Domains and Star Operations

Let * be a star operation on an integral domain D. Let f (D) be the set of all nonzero finitely generated fractional ideals of D. Call D a *-Prüfer (respectively, (*, v)-Prüfer) domain if (FF ^?1)* = D (respectively, (F ^v F ^?1)* = D) for all F ∈  f (D). We establish that *-Prüfer domains (and (*, v)-Prüfer domains) for various star operations * span a major portion of the known generalizations of Prüfer domains inside the class of v-domains. We also use Theorem 6.6 of the Larsen and McCarthy book [30 Larsen , M. D. , McCarthy , P. J. ( 1971 ). Multiplicative Theory of Ideals . New York : Academic Press . [Google Scholar]], which gives several equivalent conditions for an integral domain to be a Prüfer domain, as a model, and we show which statements of that theorem on Prüfer domains can be generalized in a natural way and proved for *-Prüfer domains, and which cannot be. We also show that in a *-Prüfer domain, each pair of *-invertible *-ideals admits a GCD in the set of *-invertible *-ideals, obtaining a remarkable generalization of a property holding for the “classical” class of Prüfer v-multiplication domains. We also link D being *-Prüfer (or (*, v)-Prüfer) with the group Inv*(D) of *-invertible *-ideals (under *-multiplication) being lattice-ordered.     

On unitary analogs of GCD reciprocal LCM matrices

A divisor d ∈ ?₊ of n ∈ ?₊ is said to be a unitary divisor of n if (d, n/d) = 1. In this article we examine the greatest common unitary divisor (GCUD) reciprocal least common unitary multiple (LCUM) matrices. At first we concentrate on the difficulty of the non-existence of the LCUM and we present three different ways to overcome this difficulty. After that we calculate the determinant of the three GCUD reciprocal LCUM matrices with respect to certain types of functions arising from the LCUM problematics. We also analyse these classes of functions, which may be referred to as unitary analogs of the class of semimultiplicative functions, and find their connections to rational arithmetical functions. Our study shows that it does make a difference how to extend the concept of LCUM.     

A topological approach to divisibility of arithmetical functions and GCD matrices

Considering lower closed sets as closed sets on a preposet (P, ≤), we obtain an Alexandroff topology on P. Then order preserving functions are continuous functions. In this article we investigate order preserving properties (and thus continuity properties) of integer-valued arithmetical functions under the usual divisibility relation of integers and power GCD matrices under the divisibility relation of integer matrices.     

A parallel extended GCD algorithm

A new parallel extended GCD algorithm is proposed. It matches the best existing parallel integer GCD algorithms of Sorenson and Chor and Goldreich, since it can be achieved in O(n/logn) time using at most n¹⁺ processors on CRCW PRAM. Sorenson and Chor and Goldreich both use a modular approach which consider the least significant bits. By contrast, our algorithm only deals with the leading bits of the integers u and v, with uv. This approach is more suitable for extended GCD algorithms since the coefficients of the extended version a and b, such that au+bv=gcd(u,v), are deeply linked with the order of magnitude of the rational v/u and its continuants. Consequently, the computation of such coefficients is much easier.     

Divisibility properties of power LCM matrices by power GCD matrices on gcd-closed sets

Let e and n be positive integers and S={x₁,…,x_n} a set of n distinct positive integers. For x∈S, define . The n×n matrix whose (i,j)-entry is the eth power (x_i,x_j)^e of the greatest common divisor of x_i and x_j is called the eth power GCD matrix on S, denoted by (S^e). Similarly we can define the eth power LCM matrix [S^e]. Bourque and Ligh showed that (S)∣[S] holds in the ring of n×n matrices over the integers if S is factor closed. Hong showed that for any gcd-closed set S with |S|≤3, (S)∣[S]. Meanwhile Hong proved that there is a gcd-closed set S with max_x∈S{|G_S(x)|}=2 such that (S)?[S]. In this paper, we introduce a new method to study systematically the divisibility for the case max_x∈S{|G_S(x)|}≤2. We give a new proof of Hong’s conjecture and obtain necessary and sufficient conditions on the gcd-closed set S with max_x∈S{|G_S(x)|}=2 such that (S^e)|[S^e]. This partially solves an open question raised by Hong. Furthermore, we show that such factorization holds if S is a gcd-closed set such that each element is a prime power or the product of two distinct primes, and in particular if S is a gcd-closed set with every element less than 12.     

On inverses of GCD matrices associated with multiplicative functions and a proof of the Hong-Loewy conjecture

Let C={1,2,…,m} and f be a multiplicative function such that (f∗μ)(k)>0 for every positive integer k and the Euler product converges. Let (C_f)=(f(i,j)) be the m×m matrix defined on the set C having f evaluated at the greatest common divisor (i,j) of i and j as its ij-entry. In the present paper, we first obtain the least upper bounds for the ij-entry and the absolute row sum of any row of (C_f)^-1, the inverse of (C_f), in terms of ζ_f. Specializing these bounds for the arithmetical functions f=N^ε,J_ε and σ_ε we examine the asymptotic behavior the smallest eigenvalue of each of matrices (C_N^ε),(C_Jε) and (C_σε) depending on ε when m tends to infinity. We conclude our paper with a proof of a conjecture posed by Hong and Loewy [S. Hong, R. Loewy, Asymptotic behavior of eigenvalues of greatest common divisor matrices, Glasg. Math. J. 46 (2004) 551-569].