Relatively Prime Set of Integers

Printable View

May 14th 2010, 09:19 AM
1337h4x

Relatively Prime Set of Integers

Hello all,

Does anyone know of a set of 4 integers S=[a,b,c,d] where where a,b,c,d >0, and that 3 of the integers in S have a common divisor 'x' > 1 , but also that the GCD(a,b,c,d)=1 ?

This is essentially plugging and playing in my mind, but I'm sure there is a more sophisticated method to this madness.
May 14th 2010, 09:34 AM
Opalg

Quote:

Originally Posted by 1337h4x

Hello all,

Does anyone know of a set of 4 integers S=[a,b,c,d] where where a,b,c,d >0, and that 3 of the integers in S have a common divisor 'x' > 1 , but also that the GCD(a,b,c,d)=1 ?

This is essentially plugging and playing in my mind, but I'm sure there is a more sophisticated method to this madness.

$a = 2\times 3\times 5,$
$b = 2\times 3\times 7,$
$c = 2\times 5\times 7,$
$d = 3\times 5\times 7.$
May 14th 2010, 09:45 AM
1337h4x

How did you reach this conclusion? Is there some sort of generic way to solve this? For example, if there was a set of 5 integers where 4 had a common divisor > 1 but the GCD was still equal to 1.
May 15th 2010, 12:32 AM
Opalg

Quote:

Originally Posted by 1337h4x

How did you reach this conclusion? Is there some sort of generic way to solve this? For example, if there was a set of 5 integers where 4 had a common divisor > 1 but the GCD was still equal to 1.

The pattern is this. Suppose you want to find a set of n positive integers $a_1,a_2,\ldots,a_n$ for which every subset containing n–1 of them has a common divisor > 1, but the GCD of the whole set of n integers is equal to 1. The method is to take n distinct prime numbers $p_1,p_2,\ldots,p_n$ . For $1\leqslant k\leqslant n$ , let $a_k$ be the product of all the $p$ s except for $p_k$ . Then $p_k$ will divide all the $a$ s except for $a_k$ . But there will be no common divisor (greater than 1) of all the $a$ s.