Kezdőlap


Feladat:	B.4832	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	2018/január, 21. oldal		PDF \| MathML
Témakör(ök):	Feladat, Oszthatóság, Konstruktív megoldási módszer
Hivatkozás(ok):	Feladatok: 2016/december: B.4832

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Jelölje $d$ az $a$ és $b$ legnagyobb közös osztóját: $d = (a; b)$ . Legyen $r_{1} = \frac{b}{d}$ és $s_{1} = \frac{a}{d}$ . Ekkor nyilván $(r_{1}, s_{1}) = 1$ és $a r_{1} = b s_{1} = \frac{a b}{d}$ , tehát $a r_{1} + b \cdot (- s_{1}) = 0$ , ami osztható $c$ -vel.
De egyelőre $s = - s_{1} < 0$ . Keressünk olyan, $c$ -vel osztható $k$ pozitív egész számot, melyre $s_{2} = k - s_{1} > 0$ és $(r_{1}, s_{2}) = (\frac{b}{d}; k - \frac{a}{d}) = 1$ továbbra is teljesül. Mivel $c ∣ k$ , ezért $c ∣ b k = (a r_{1} - b s_{1}) + b k = a r_{1} + b (k - s_{1}) = a r_{1} + b s_{2}$ .
Legyen $k = k' c \cdot \frac{b}{d}$ , ahol $k'$ elég nagy ahhoz, hogy $k' c \cdot \frac{b}{d} - \frac{a}{d} > 0$ fennálljon.
Azt állítjuk, hogy $(r_{1}, s_{2}) = 1$ is igaz. Ha ugyanis

\begin{matrix} 1 < m = (r_{1}, s_{2}) = (\frac{b}{d}, k' c \frac{b}{d} - \frac{a}{d}) \end{matrix}

valamely

m

pozitív egészre, akkor

m ∣ \frac{b}{d}

miatt

m ∣ k' c \frac{b}{d}

is igaz, amiből

m ∣ s_{2}

miatt

m ∣ \frac{a}{d}

következik, de ekkor

m ∣ \frac{a}{d}

és

m ∣ \frac{b}{d}

, ami ellentmond annak, hogy

\frac{a}{d}

és

\frac{b}{d}

relatív prímek. Tehát valóban

(r_{1}, s_{2}) = 1

.
Tehát

r = \frac{b}{d}

és

s = k' c \cdot \frac{b}{d}

, ahol

k'

megfelelően nagy, jó választás.