Let $S$ be the set of positive integers. For any $a$ and $b$ in the set we have $GCD(a, b)>1$. For any $a$, $b$ and $c$ in the set we have $GCD(a, b, c)=1$. Is it possible that $S$ has $2012$ elements? Proposed by Ognjen Stipetić.
Problem
Source: European Mathematical Cup 2012, Junior Division, Problem 2
Tags: number theory, greatest common divisor, function, prime numbers, number theory proposed
ssilwa
27.07.2013 05:24
The constriction can be easily thought out by considering small examples. Here is my attempt: Suppose we have $2012$ sets of prime numbers $a_{2012}, \cdots , a_1$ where $a_n$ has $n$ elements and no prime appears in more than $1$ set.
Now let the numbers in $S$ be called $b_i$. Then we let $b_1 = a_{2012}$. Take one prime out. Then let each of the $2011$ primes left in $a_{2012}$ go to only one of $b_i, i \ne 1$. Then let $b_2 = qa_{2011}$ where $q \in a_{2012}$ Then choose $2010$ primes in $a_{2011}$ to go to only one of $b_i, i \ne 1, 2$. Continuing in this fashion, we are done. It is easy to verify that the gcd conditions do indeed hold.
randomusername
30.11.2013 23:22
Draw a $K_{n}(V,E)$ graph, define a bijective function $f:E(K_{n})\to\left\{1,2,\dots,\binom{n}2\right\}$, then take $a_i:=\prod_{j\neq i} p_{f(v_iv_j)}$, where $p_k$ denotes the $k^{th}$ prime number (and $\{v_1,v_2,\dots,v_n\}=V(K_n)$). $n:=2012$, $S:=\{a_1,a_2,\dots,a_{n}\}$ is the example of such a set $S$, because trivially $\text{GCD}(a_i,a_j)=p_{f(v_iv_j)}>1$, and every prime number divides the elements of $S$ at most twice.
lfetahu
03.12.2013 02:15
Let S={a1, a2, ..., an}. For i not equal to j, let gcd(ai,aj)=pij, where p is a prime and pij different from pi'j', when (i,j) different from (i',j'). Then ai = (product of pji, where j<i) * (product of pij, where i<j) and 1<=i<=n satisfies the condition for every n>=3.
anantmudgal09
13.09.2015 01:39
Consider a $\gcd(a_i,a_j)=p_{i,j} \forall 1\le i< j\le 2012$ with $p_{i,j}$ being distinct and large primes.Crt kills it immediately.
MR.1
16.12.2024 18:27
I think "s" can be any size. Lets create s=4 s={a,b,c,d} a=a1 x a2 x a3 x a4 b=a1 x b2 x b3 x b4 c=a2 x c2 x c3 x c4 d=a3 x d2 x d3 x d4 Such that a1 a2... b1... ...d4 are primes After thath if we want to add new member let's just say "e" then we make this changes a=a1 x a2 x a3 x a4 x a5 b=a1 x b2 x b3 x b4 x b5 c=a2 x c2 x c3 x c4 x c5 d=a3 x d2 x d3 x d4 x d5 e=a5 x b5 x c5 x d5 x e5 and also e5 is prime i honestly don't see any problem in this so if you do plz tell me