NT: ggd's

Opgave - EGMO 2012 dag 2 vraag 1

De getallen p en q zijn priem en voldoen aan
$\frac{p}{p + 1}+\frac{q + 1}{q}
=
\frac{2n}{n + 2}$
voor een zeker positief geheel getal n. Vind alle mogelijke waarden van $q-p.$

Oplossing

Leuke vraag.

Eerst vereenvoudigen we het LL:
\[\frac{p}{p+1} + \frac{q+1}{q} = \frac{(p+1)-1}{p+1} + \frac{(q+1-1)+1}{q}\]
\[\frac{p+1}{p+1} - \frac{1}{p+1} + \frac{q}{q} + \frac{1}{q}\]
\[2 + \frac{1}{q} - \frac{1}{p+1}\]
nu het RL:
\[\frac{2n}{n+2} = \frac{(2n+4)-4}{n+2} = \frac{2n+4}{n+2} - \frac{4}{n+2}\]
\[2 - \frac{4}{n+2}\]
We krijgen
\[2 + \frac{1}{q} - \frac{1}{p+1} = 2 - \frac{4}{n+2} \]
\[\iff \frac{1}{p+1} - \frac{1}{q} = \frac{4}{n+2}\]
Wat duidelijk impliceert dat $q>p$ want voor $p\geq q$ is het LL negatief terwijl het RL positief is $(n\geq 0$ gegeven).
Nu bestuderen we eerst het ambetant gevalletje $p=2$.
\[\frac{1}{3} - \frac{1}{q} = \frac{4}{n+2}\]
\[(n+2)(q-3) = 12q\]
\[n = \frac{10q+6}{q-3}\]
\[\iff n = \frac{10q+6}{q-3} - 10 + 10\]
\[\iff n = \frac{10q+6}{q-3} - \frac{10(q-3)}{q-3} + 10\]
\[\iff n = \frac{10q+6 - (10q-30)}{q-3} + 10\]
\[\iff n = \frac{36}{q-3} + 10\]
en $q-3|36$ voor $q=5,7$ dus $q-p = 5$ of $q-p = 3$ zijn al de eerste oplossingen.

Nu bestuderen we de gevallen waarbij $p$ en $q$ beide oneven zijn (met nogsteeds $q>p$ dus $q$ kan niet $2$ zijn).
We krijgen
\[\iff \frac{1}{p+1} - \frac{1}{q} = \frac{4}{n+2}\]
Schrijf $q=p+2k$ voor een natuurlijk getal $k$.
We krijgen
\[\iff \frac{2k-1}{(p+1)(p+2k)} = \frac{4}{n+2}\]
Aangezien $2k-1$ niet deelbaar door $2$ is, impliceert dit rechtstreeks dat $n = 4c-2$ voor een natuurlijk getal $c$ (wordt duidelijker met kruislings vermenigvuldigen: we krijgen namelijk dat $(2k-1)(n+2) \equiv 0 \pmod 4 \iff n \equiv 2 \pmod 4$).
Als we $p+2k$ nu weer vervangen door $q$, krijgen we
\[\frac{1}{p+1} - \frac{1}{q} = \frac{1}{c}\]
\[\iff (p+1)q = c(q-(p+1))\]
Daar ggd($q,q-(p+1))$ = ggd$(q,p+1) = 1$ aangezien geldt dat $q>p+1$, want als $q=p+1$ wordt het RL $0$ en is gelijkheid onmogelijk. En $q$ is relatief priem met alle getallen kleiner dan zichzelf.
Dit impliceert dat $q|c$, schrijf $c$ dus als $kq$.
We krijgen
\[p+1 = k(q-(p+1)\]
\[\iff kq = (k+1)(p+1)\]
wat impliceert dat $k+1|q$ (want gdd($k,k+1) = 1$) en $q|k+1$ (want gdd($q,p+1) = 1$) dus $q = k+1$. Dit impliceert dat $k = p+1$ dus krijgen we dat $q-p = k+1 - (k-1) = 2$ wat de laatste oplossing is.
De enige oplossingen zijn $q-p = 2,3,5$.