# Relatively Prime Set of Integers

• 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.

$\displaystyle a = 2\times 3\times 5,$
$\displaystyle b = 2\times 3\times 7,$
$\displaystyle c = 2\times 5\times 7,$
$\displaystyle 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 $\displaystyle 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 $\displaystyle p_1,p_2,\ldots,p_n$. For $\displaystyle 1\leqslant k\leqslant n$, let $\displaystyle a_k$ be the product of all the $\displaystyle p$s except for $\displaystyle p_k$. Then $\displaystyle p_k$ will divide all the $\displaystyle a$s except for $\displaystyle a_k$. But there will be no common divisor (greater than 1) of all the $\displaystyle a$s.