John Campbell's lcm refinement algorithm
Here a0,...,an-1 are integers, with a0,...,an-1 positive.
We replace them by an array of positive integers b0,...,bn-1, where
The algorithm is due to T.J. Stieltjes, Oeuvres Complètes, Tome II, 280-283 (from Sur la theorie des nombres, Ann. Fac. Toulouse 4 (1890), 1-103, especially Sections 18-19) and was rediscovered by John Campbell in 2003. See note.
- bi divides ai for 0 ≤ i < n;
- gcd(bi, bj)=1 for 0 ≤ i < j < n;
Last modified 11th August 2006
Return to main page