Kezdőlap


Feladat:	Gy.2943	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Gáspár László , Reviczky Ágnes
Füzet:	1995/április, 211 - 213. oldal		PDF \| MathML
Témakör(ök):	Legnagyobb közös osztó, Legkisebb közös többszörös, Diofantikus egyenletek, Gyakorlat
Hivatkozás(ok):	Feladatok: 1994/november: Gy.2943

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öljük $a$ és $b$ legnagyobb közös osztóját $A$ -val, és legyen $a = a_{1} \cdot A$ ,
$b = b_{1} \cdot A$ . Ekkor a legkisebb közös többszörös $A \cdot a_{1} \cdot b_{1}$ , amiről meggyőződhetünk a számok prímtényezős alakját vizsgálva: ha $a = p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \cdot ... \cdot p_{r}^{α_{r}}$ , $b = p_{1}^{β_{1}} \cdot p_{2}^{β_{2}} \cdot ... \cdot p_{r}^{β_{r}}$ ( $α_{i} \geq 0$ , $β_{i} \geq 0$ ), akkor

\begin{matrix} \begin{matrix} A = (a, b) = p_{1}^{{min}_{}^{} (α_{1}, β_{1})} \cdot ... \cdot p_{r}^{{min}_{}^{} (α_{r}, β_{r})}, [a, b] = p_{1}^{{max}_{}^{} (α_{1}, β_{1})} \cdot ... \cdot p_{r}^{{max}_{}^{} (α_{r}, β_{r})}, \\ a_{1} = p_{1}^{α_{1} - {min}_{}^{} (α_{1}, β_{1})} \cdot ... \cdot p_{r}^{α_{r} - {min}_{}^{} (α_{r}, β_{r})}, b_{1} = p_{1}^{β_{1} - {min}_{}^{} (α_{1}, β_{1})} \cdot ... \cdot p_{r}^{β_{r} - {min}_{}^{} (α_{r}, β_{r})}, \end{matrix} \end{matrix}

azaz

\begin{matrix} A \cdot a_{1} \cdot b_{1} = p_{1}^{α_{1} + β_{1} - {min}_{}^{} (α_{1}, β_{1})} \cdot ... \cdot p_{r}^{α_{r} + β_{r} - {min}_{}^{} (α_{r}, β_{r})} = p_{1}^{{max}_{}^{} (α_{1}, β_{1})} \cdot ... \cdot p_{r}^{{max}_{}^{} (α_{r}, β_{r})}, \end{matrix}

hiszen tetszőleges

α

β

esetén

α + β - {min}_{}^{} (α, β) = {max}_{}^{} (α, β)

.
Az előbbieket az egyenletbe helyettesítve és azt átalakítva:

\begin{matrix} \begin{matrix} A \cdot a_{1} \cdot b_{1} + A + A \cdot a_{1} + A \cdot b_{1} & = A a_{1} \cdot A b_{1}, \\ A \cdot (a_{1} b_{1} + a_{1} + b_{1} + 1) & = A \cdot (A a_{1} b_{1}), \\ A (a_{1} + 1) (b_{1} + 1) & = A (A a_{1} b_{1}) . \end{matrix} \end{matrix}

Vizsgáljuk meg először az

A = 0

esetet. Ha

a \neq 0

és

b \neq 0

, akkor

A \neq 0

, így

a

és

b

közül valamelyik biztosan nulla. Definíció szerint

(a,0) = a

, ha

a \neq 0

, vagyis egyedül az

a = b = 0

eset marad. A

(0,0)

számot nem szokás értelmezni; ha mégis megtesszük, akkor

(0,0) = 0

esetén az

a = b = 0

számpár megoldás, míg

(0,0) \neq 0

esetén nem. Más kérdés, hogy a

0

-t nem mindig tekintik természetes számnak; mindenesetre sem az

a = b = 0

hiánya, sem a megléte nem befolyásolja a megoldás további (és egyben lényegi) részét (sem pedig a pontozást).
Feltehetjük tehát, hogy

A \neq 0

, és ekkor egyszerűsíthetünk vele:

\begin{matrix} (a_{1} + 1) (b_{1} + 1) = A a_{1} b_{1} . \end{matrix}

(1)

Látható, hogy az

a_{1} = 0

, illetve

b_{1} = 0

esetek nem adnak megoldást, így megengedett a következő átrendezés:

\begin{matrix} A = \frac{a_{1} + 1}{a_{1}} \cdot \frac{b_{1} + 1}{b_{1}} . \end{matrix}

Mivel

1 \leq a_{1}

és

1 \leq b_{1}

, azért

\begin{matrix} 1 < \frac{a_{1} + 1}{a_{1}} \leq 2, 1 < \frac{b_{1} + 1}{b_{1}} \leq 2; \end{matrix}

ennek alapján csak

A = 2

; 3; 4 lehetséges.
1. eset:

A = 2

. Ekkor (1)-et átrendezve

\begin{matrix} a_{1} b_{1} + a_{1} + b_{1} + 1 = 2 a_{1} b_{1}, \end{matrix}

majd 2-t mindkét oldalhoz hozzáadva,

\begin{matrix} 2 = a_{1} b_{1} - a_{1} - b_{1} + 1 = (a_{1} - 1) (b_{1} - 1) . \end{matrix}

Ez csak úgy lehet, ha

a_{1} - 1 = 1

és

b_{1} - 1 = 2

, vagy fordítva. Az előbbi esetén

a_{1} = 2

b_{1} = 3

, azaz

a = 4

b = 6

; míg a másiknál

a = 6

b = 4

.
2. eset:

A = 3

. Most (1)-ből

\begin{matrix} \begin{matrix} 3 a_{1} b_{1} = a_{1} b_{1} + a_{1} + b_{1} + 1, \\ 2 a_{1} b_{1} - a_{1} - b_{1} - 1 = 0, \\ 4 a_{1} b_{1} - 2 a_{1} - 2 b_{1} - 2 = 0, \\ (2 a_{1} - 1) (2 b_{1} - 1) = 3. \end{matrix} \end{matrix}

Ekkor szükségképpen

2 a_{1} - 1 = 3

és

2 b_{1} - 1 = 1

, vagy fordítva, amiből

a = 6

b = 3

, illetve

a = 3

b = 6

adódik.
3. eset:

A = 4

. Ekkor

\begin{matrix} \begin{matrix} 4 a_{1} b_{1} = a_{1} b_{1} + a_{1} + b_{1} + 1, \\ 3 a_{1} b_{1} - a_{1} - b_{1} - 1 = 0, \\ 9 a_{1} b_{1} - 3 a_{1} - 3 b_{1} - 3 = 0, \\ (3 a_{1} - 1) (3 b_{1} - 1) = 4. \end{matrix} \end{matrix}

Mivel

3 a_{1} - 1 = 4

és

3 b_{1} - 1 = 1

nem lehetséges, így

3 a_{1} - 1 = 3 b_{1} - 1 = 2

, amiből

a = b = 4

.
Öt számpárt találtunk, s könnyen ellenőrizhető, hogy ezek mindegyike valóban jó is; a megoldások tehát:

\begin{matrix} (3; 6), (4; 6), (4; 4), (6; 4), (6; 3) . \end{matrix}

Reviczky Ágnes (München, Gymansium Der Armen Schulschwestern, II. o.t.)

dolgozata alapján