Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail From: Kaz Kylheku Newsgroups: comp.programming Subject: Re: computing the list of common factors - any applications? Date: Thu, 2 Apr 2015 02:43:47 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 37 Message-ID: <20150401192816.254@kylheku.com> References: <5f5aa117-020f-4300-82ea-4c11ab69ab6a@googlegroups.com> NNTP-Posting-Host: OGJi3KNpFOhM58UHZwXj0w.user.speranza.aioe.org X-Complaints-To: abuse@aioe.org User-Agent: slrn/pre1.0.0-18 (Linux) X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:5371 On 2015-04-01, Mark Tarver wrote: > Computing the *list* of common factors of two numbers is an introductory exercise in maths e.g. see > > http://www.calculatorsoup.com/calculators/math/commonfactors.php That consistently lists 1 as a factor! Ouch! PHP number theory? Factors begin at 2. The factors of 16 are 2, 4, 8 and 16. 1 has no factors. To be fair, GCD functions in programming languages tend to return 1 when two numbers have *no* factors in common (and I think I've seen the gcd function defined that way in some number theory texts). This should be regarded as a special indication, and not as an assertion that there exists a common factor, and it is 1! Since neither of a pair of integers has 1 as a factor, it cannot be in common. > Recently I proposed running a concurrent algorithm for doing this and a > friend objected that he has never heard of a practical application for > finding such a list. Can anybody cite an application? The list of common factors is nothing more than the factorization of the greatest common factor. So perhaps, would you agree that we can decompose the question like this? 1. Is it ever of practical use to compute the GCD of a pair of integers? 2. Is it ever of practical use to factor an integer? 3. Is it ever useful for (2) to be applied to the result of (1)? Let us assume that 1) and 2) are yes: gcd is useful by itself, and so is factorization. Is (3) the factorization of a gcd ever useful? Or how about splitting hairs further: 4. is the *complete* factorization of a gcd ever useful, or just knowing whether the gcd is prime or composite?