ggd(a,b)>ggd(a,b,c)
Opgave - JEMC 2012 dag 1 vraag 2
Zij $S$ een verzameling van strikt natuurlijke getallen (> $0$). Voor elke $a$ en $b$ uit $ S$ geldt dat
$ggd(a, b) $ > $1$. Voor elke $a,b,c\in S$ hebben we dat $ggd(a,b, c) = 1$.
Is het mogelijk dat $S$ $2012$ elementen heeft?
Hierbij is $ggd(x,y,z)$ de grootste gemene deler van $x, y$ en $z$.
- login om te reageren
Oplossing
Stel $S$ heeft $n$ elementen, waarbij elk element uit $S$ een product is van $n-1$ verschillende priemfactoren, te kiezen uit $n*(n-1)/2$ priemgetallen.
Noem de elementen $a_1,a_2,\cdots a_n$ en neem voor ieder koppel $i,j$ een ander priemgetal uit de ${ n\choose 2} $ gekozen priemgetallen.
Dit betekent dat $3$ getallen nu geen gemeenschappelijke priemfactor kregen per constructie.
Maar iedere twee uiteraard wel.
Bijgevolg kan het voor iedere waarde van $n$ en dus ook voor $2012$ is het mogelijk.