comp.programming

Kaz Kylheku

4/2/2015 2:44:00 AM

On 2015-04-01, Mark Tarver <dr.mtarver@ukonline.co.uk> 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/commonf...

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?