mss wel mooiste B6
Opgave - Putnam 1999 dag 2 vraag 6
Zij $S$ een eindige verzameling van natuurlijke getallen groter dan $1$. Veronderstel dat voor alle $n \in \mathbb N$ geldt dat er een $s\in S$ bestaat zodat $\ggd(s,n)=1$ of $\ggd(s,n)=s$. Bewijs dat er $s,t\in S$ zijn zodat $\ggd(s,t)$ priem is.
opm. : $s,t$ moeten niet verschillend zijn (anders klopt de vraag niet)
- login om te reageren
Oplossing
Stel dat er een verzameling S bestaat waarvoor geldt dat voor alle $n \in \mathbb N$ geldt dat er een $s\in S$ bestaat zodat $\ggd(s,n)=1$ of $\ggd(s,n)=s$, maar dat er geen enkele $s,t\in S$ bestaat zodat $\ggd(s,t)$ priem is. (zelfs als s=t).
Het is meteen duidelijk dat S geen priemgetallen mag bevatten: als $x\in S$ priem is, dan is $\ggd(x,x)$ ook priem.
Alle $s\in S$ hebben dus minstens 2 priemfactoren. (1)
[ eventueel meerdere keren dezelfde priemfactor]
S bevat ook meer dan 1 element, anders zou de grootste gemene deler van dit element en een priemfactor ervan verschillend zijn van zowel dit element als 1.
Als $x,y\in S$ één gemeenschappelijke priemfactor a hebben, dan hebben ze automatisch ook een tweede gemeenschappelijke priemfactor. Anders zou $\ggd(x,y)=a$ en a is priem. (2)
Neem nu een willekeurige priemfactor $b$ die in een element van S voorkomt. Zoek nu een $s\in S$ waarin deze priemfactor het minst vaak voorkomt, maar wel voorkomt.
Noem nu $s/b=c$. $c$ is verschillend van 1, omdat $s$ meerdere priemfactoren heeft. Dit volgt uit (1).
$1\neq \ggd(s,c) \neq s$, want ze hebben gemeenschappelijke priemfactoren, maar $s$ is $b$ keren groter dan $c$. Hetzelfde geldt voor enig andere $l\in S$ die de priemfactor $b$ bezit. Dit volgt uit (2). Ze hebben namelijk sowieso een priemfactor gemeen, maar $b$ komt minder vaak in $c$ voor.
Neem nu alle $s\in S$ die een priemfactor $b$ hebben, en kopieer deze naar de verzameling T. Kopieer ook $b$ naar de verzameling U.
(3) Kijk of er een $q\in S$ met $q\notin T$ bestaat.
Als een dergelijke $q$ bestaat, neem dan een willekeurige priemfactor $d$ van $q$, en zoek een element $z\in S$ $d$ het minst vaak voorkomt, maar wel voorkomt.
Dus zodat $z \in \{ r \in Z |v_d(t)>0 EN v_d(t) < v_d(z)$, $\forall z \in Z | v_d(z)>0 \}$
Vervang $c$ dan met $kgv(\frac{z}{d},c)$
Definieer $U$ als een verzameling waar de reeds gebruikte priemfactoren in "opslaan" worden, zodat we zeker c niet nog eens met zo'n factor zouden vermenigvuldigen want dan zou het bewijs ongeldig zijn.
Momenteel zitten dus $b,d$ in $U.$
We bekijken nu $2$ gevallen:
Als $z\notin T$:
Omdat alle elementen van T nog steeds gemeenschappelijke priemfactoren hebben met $c$, en omdat er geen extra priemfactor $\in U$ kan komen in $c$ (want alle elementen met een priemfactor $\in U$ zijn $\in T$), geldt nog steeds $1\neq \ggd(t,c) \neq t$ $ \forall t \in T$.
Als $z\in T$:
Omdat alle elementen van T nog steeds gemeenschappelijke priemfactoren hebben met $c$, en omdat er geen extra priemfactor $\in U$ kan komen in $c$, geldt nog steeds $1\neq \ggd(t,c) \neq t$ $ \forall t \in T$.
We steken dus alle getallen die een veelvoud van $d$ zijn ook in $T$ en wegens $(2)$ blijft onze conclusie gelden:
Er blijft $1\neq \ggd(t,c) \neq t$ $ \forall t \in T$ gelden als we alle getallen $z\in S$ met priemfactor $d$ aan T toevoegen.
Ga nu terug naar (3) en bekijk iedere keer een verschillend priemgetal die getallen uit $T $ zonder $S$ delen, zolang die laatste verzameling elementen bevat.
Als er echter geen dergelijke $z\in S$ met $z\notin T$ bestaat, volgt S=T.
Aangezien $1\neq \ggd(t,c) \neq t$ $ \forall t \in T$ geldt: $1\neq \ggd(s,c) \neq s$ $ \forall s \in S$.
Dit zal sowieso ooit voorkomen, want er komen alsmaar meer elementen in T, en S is een eindige verzameling. Tegenstrijdigheid.
eleganter alternatief:
Stel dat er een verzameling $S$ met $k$ elementen bestaat waarvoor geldt dat voor alle $n \in \mathbb N$ geldt dat er een $s\in S$ bestaat zodat $\ggd(s,n)=1$ of $\ggd(s,n)=s$, maar dat er geen enkele $s,t\in S$ bestaat zodat $\ggd(s,t)$ priem is. (zelfs als s=t).
Het is meteen duidelijk dat $S$ geen priemgetallen mag bevatten: als $x\in S$ priem is, dan is $\ggd(x,x)$ ook priem.
Alle $s\in S$ hebben dus minstens 2 priemfactoren. (1)
[ eventueel meerdere keren dezelfde priemfactor]
$S$ bevat ook meer dan 1 element, anders zou de grootste gemene deler van dit element en een priemfactor ervan verschillend zijn van zowel dit element als 1.
Als $x,y\in S$ één gemeenschappelijke priemfactor $a$ hebben, dan hebben ze automatisch ook een tweede gemeenschappelijke priemfactor. Anders zou $\ggd(x,y)=a$ en a is priem. (2)
Neem van een element van $s_1 \in S$ een priemfactor en noem deze $c_{1}$. Neem nu een tweede element $s_2$ en kijk of $c_1$ een priemfactor gemeenschappelijk heeft. Indien dit zo is, dan is $c_2=c_1$. Anders vermenigvuldig je $c_1$ met een priemfactor van $s_2$ om $c_2$ te bekomen.
Ga zo de volledige verzameling $S$ af. Er moet nu een $r \in S$ bestaan waarvoor $\ggd(r,c_k)=r$. (Want $c_k$ heeft met alle elementen een priemfactor gemeen.)
Omdat alle priemfactoren van $c_k$ er één voor één bijkomen, en omdat (1) moeten er één of meer $c_i, i\le k$ bestaan, waarvoor $c_i$ alle priemfactoren van $r$ heeft behalve één. Neem nu de grootste $i$ waarvoor dit het geval is. Dan moet $s_{i+1}$ deze ene priemfactor hebben. Uit (2) volgt echter dat hij nog een priemfactor gemeen heeft met $r$. En omdat alle andere priemfactoren van $r$ ook in $c_i$ zitten, is $c_i=c_{i+1}$. Tegenstrijdigheid.