Finding 2 or more numbers having the given number as GCF

I don't want to find the GCF of given numbers. I use Euclidean for that. I want to generate a series of numbers having a given GCF. For example if I choo开发者_运维百科se 4, I should get something like 100, 72 or 4, 8 etc.,

Any pointers would be appreciated.

A series of pairs of numbers having N as a GCF is {N,N}, {N,2N}, {N,3N}, ....

In fact, any set consisting of N and 1 or more multiples of N has N as its GCF.

1.Maybe this question can be better answered at http://math.stackexchange.com

2.Just construct the numbers you are interested in by multiplying the numbers that are not factors of the GCD. for your example of given GCD=4 that means $k_1=4$ the GCD itself $k_2=4 * 2$ since 4 does not divide 2 $k_3=4 * 3$ since 4 does not divide 3 $not k_4=4 * 4$ since 4 divides 4 but $ k_4=4 * 5$ since 4 does not divide 5 etc.

If 4 is the input, you want a list of numbers whose greatest common factor is 4. You can ensure this by making 4 the only factor in the entire series. Therefore, you multiply the number (4) by all primes to ensure that.

prime-list = 3, 5, 7, 11, 13, 17

gcf-list for 4 -> (3*4)12, (4*5)20, (4*7)28, (4*11)44, (4*13)52, (4*17)68, ...

This will give you a list such that the GCF of any two numbers is 4

Choose a set of numbers that are pairwise-independent (that is gcd(x,y) = 1 for every x<>y in the set). Multiply each number by your target GCD.

I realize that this is an old question but I am going to provide my own answer along with an explanation of how I got there. First, let's call the GCF n.

Initially I would have suggested doing something like picking random integers and multiplying them each by n to get the set of numbers, this would of course give you numbers evenly divisible by n but not necessarily numbers with a GCF of n. If the integers happened to all have a GCF other than '1' then the GCF of the resulting set would actually have a GCF of n times that number, not n. That being said multiplying n by a set of integers seems the best way of ensuring that each number in the set is at least divisible by n

One option would be to make one of those numbers 1 but that would reduce the randomness of the set as n would always be in the resulting set.

Next you could use some prime numbers and multiply them by n but that would also reduce randomness as there would be less possible numbers, and the numbers don't actually need to be prime, just co-prime (GCF = 1 for the entire set)

You could also pick a set of numbers where each pair of numbers were co-prime but again, the entire set needs to be co-prime not co-prime pair-wise (which would be pretty processor intensive with larger sets).

So if you are going for fairly random numbers I would start by determining how many numbers you want in the set (whether that is randomly determined or predetermined) and then generating one less than that number completely 'randomly'. I would then compute the common prime factors for those numbers and then pick a random number that does not have any of those prime factors. Merely ensuring it does not have the same GCF is not sufficient as the GCF could have common factors to the final number. It only requires one number in a set that does not have any of the same prime factors as the other numbers in the set to make the GCF of that set '1'. I would then take that set of numbers and multiply each by n to get the set of numbers you want.