Kezdőlap


Feladat:	2007. évi Nemzetközi Matematika Diákolimpia 22. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Korándi Dániel
Füzet:	2007/október, 390 - 391. oldal		PDF \| MathML
Témakör(ök):	Legnagyobb közös osztó, Másodfokú (és arra visszavezethető) egyenletek, Oszthatósági feladatok, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 2007/szeptember: 2007. évi Nemzetközi Matematika Diákolimpia 22. feladata

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.

Korándi Dániel megoldása. Legyen $r$ és $s$ egész szám. Ha a legnagyobb közös osztójuk $d$ , akkor $r = d r_{1}$ és $s = d s_{1}$ , ahol az $r_{1}$ és $s_{1}$ egészek egymáshoz relatív prímek. Tegyük fel, hogy $r$ osztója $s^{2}$ -nek; ekkor $d r_{1} ∣ d^{2} s_{1}^{2}$ miatt $r_{1} ∣ d s_{1}^{2}$ . Mivel $r_{1}$ relatív prím $s_{1}^{2}$ -hez is, $r_{1}$ osztója $d$ -nek. Ebből következik, hogy ha $d$ osztója egy $t$ egésznek, akkor $r = d r_{1}$ osztója $t^{2}$ -nek.
$4 a b - 1$ és $4 a^{2} - 1$ legnagyobb közös osztója osztja a két szám különbségét, $4 a (b - a)$ -t is, és mivel (mindkét eredeti számhoz hasonlóan) relatív prím $4 a$ -hoz, osztója $(b - a)$ -nak is. Az előbbi megjegyzés szerint tehát

\begin{matrix} 4 a b - 1 ∣ {(b - a)}^{2} . \end{matrix}

Megmutatjuk, hogy ez pozitív egész

a

-ra és

b

-re csak

a = b

esetén teljesül. Tegyük fel ezzel szemben, hogy

b \neq a

; legyen például

b > a

. Ekkor

\begin{matrix} k = \frac{{(b - a)}^{2}}{4 a b - 1} pozitív egész. \end{matrix}

Rendezve:

0 = b^{2} - 2 a (1 + 2 k) b + (a^{2} + k)

, azaz

b

gyöke az

\begin{matrix} x^{2} - 2 a (1 + 2 k) x + (a^{2} + k) = 0 \end{matrix}

másodfokú egyenletnek. Jelölje az egyenlet másik gyökét

c

; ekkor

b + c = 2 a (1 + 2 k)

egész, ezért

c

is egész, és

b c = a^{2} + k > 0

miatt

c

is pozitív. Valamivel pontosabban:

\begin{matrix} k = \frac{{(b - a)}^{2}}{4 a b - 1} < \frac{{(b - a)}^{2}}{4 a b - 4 a^{2}} = \frac{(b - a)}{4 a}, \end{matrix}

ezért

2 a (1 + 2 k) < 2 a (1 + \frac{b - a}{2 a}) = b + a

, tehát

0 < c < (b + a) - b = a

. Erre a

c

egészre (

b

-hez hasonlóan)

\begin{matrix} k = \frac{{(c - a)}^{2}}{4 a c - 1}, \end{matrix}

azaz

4 c a - 1 ∣ {(a - c)}^{2}

, és

0 < c < a

. Az

a = b_{1} > c = a_{1}

pozitív egész számpár tehát ugyanazt az oszthatósági feltételt teljesíti, mint a

b > a

számpár, csak éppen

b_{1} < b

. Az előbbi gondolatmenet így megismételhető

b

és

a

helyett

b_{1}

-gyel és

a_{1}

-gyel stb. Ezzel pozitív egészek végtelenül csökkenő

b > b_{1} > ...

sorozatát kapjuk, ami lehetetlen. Ez az ellentmondás igazolja állításunkat, és ezzel a feladat állítását is.