Kezdőlap


Feladat:	1990. évi Kürschák matematikaverseny 1. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Boncz András , Faragó Gergely , Harcos Gergely , Lakos Gyula , Matolcsi Máté , Pór Attila , Szegedy Balázs , Szegedy Krisztián , Szendrői Balázs , Tokodi Tamás , Újváry-Menyhárt Zoltán
Füzet:	1991/február, 51 - 54. oldal		PDF \| MathML
Témakör(ök):	Prímszámok, Oszthatóság, Prímtényezős felbontás, Oszthatósági feladatok, Legnagyobb közös osztó, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 1991/február: 1990. évi Kürschák matematikaverseny 1. 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.

I. megoldás: A számelmélet alaptétele értelmében $d$ prímszámhatványok szorzatára történő felbontásában csak azok a prímszámok szerepelhetnek, amelyek $p n^{2}$ felbontásában szerepelnek, és legfeljebb akkora kitevőn, mint az utóbbi felbontásban. Így két esetet különböztethetünk meg. Ha $p$ nem szerepel $d$ felbontásában, akkor $d$ osztója $n^{2}$ -nek is, ha pedig szerepel, akkor $d = p d'$ , ahol $d'$ osztója $n^{2}$ -nek.
Feltétel szerint van olyan $m$ pozitív egész, amelyre az első esetben

\begin{matrix} d + n^{2} = m^{2}, a másodikban p d' + n^{2} = m^{2} . \end{matrix}

Véve

d

, illetőleg

d'

egy tetszés szerinti

q

prím osztóját, azzal

n^{2}

és

m^{2}

is osztható. Mivel a prímtényezős felbontás lényegében egyértelmű, ez csak úgy lehetséges, ha az alapok is oszthatók

q

-val, és így

n^{2}

és

m^{2}

osztható

q^{2}

-tel.
Ekkor

d

, illetőleg

d'

is osztható

q^{2}

-tel, kivéve a második esetben, ha

q = p

. Az említett eset kivételével tehát egyszerűsíthetünk

q^{2}

-tel, és

\begin{matrix} d^{*} + n'^{2} = m'^{2}, illetőleg p d^{*} + n'^{2} = m'^{2} \end{matrix}

alakú összefüggésekhez jutunk, ahol

d^{*}

osztója

n'^{2}

-nek.
Ha a második esetben

q = p

, akkor is oszthatunk

q^{2}

-tel, csak akkor a fenti első típusú egyenlethez jutunk, ahol

d^{*}

most is osztója lesz

n'^{2}

-nek.
Az eljárást megismételhetjük sorra

d^{*}

minden prím osztójára, és így azt kapjuk, hogy van olyan pozitív egész

n_{1}

és

m_{1}

, amelyekkel fennáll, hogy

\begin{matrix} 1 + n_{1}^{2} = m_{1}^{2} vagy p + n_{1}^{2} = m_{1}^{2} . \end{matrix}

(1)

Az eljárás során minden lépésben

n

egy

q

prím osztójának a négyzetével egyszerűsítettünk, tehát végül is egy olyan

n_{2}^{2}

egésszel, amelyikre

\begin{matrix} n = n_{1} n_{2} és d = n_{2}^{2}, illetőleg d = p n_{2}^{2} . \end{matrix}

Az (1) alatti első egyenlet nem állhat fenn, mert két pozitív négyzetszám különbsége legalább

3

. A második egyenlőségből

\begin{matrix} p = (m_{1} + n_{1}) (m_{1} - n_{1}) . \end{matrix}

Mivel

p

prímszám, így ebből

\begin{matrix} m_{1} + n_{1} = p, m_{1} - n_{1} = 1, tehát 2 n_{1} = p - 1. \end{matrix}

Ezzel azt kaptuk, hogy a feladat feltételei akkor teljesülhetnek, ha

\begin{matrix} n = \frac{1}{2} (p - 1) n_{2} és d = p n_{2}^{2} . \end{matrix}

Ezekre

\begin{matrix} d + n^{2} = {p + {[\frac{1}{2} (p - 1)]}^{2}} n_{2}^{2} = {[\frac{1}{2} (p + 1)]}^{2} n_{2}^{2} = {[\frac{1}{2} (p + 1) n_{2}]}^{2} \end{matrix}

valóban négyzetszám.
Eszerint valóban legfeljebb egy megfelelő

d

van, éspedig akkor van ilyen, ha

n

osztható

\frac{1}{2} (p - 1)

-gyel.

Megjegyzés: Nem használtuk ki a megoldás során, hogy

p

páratlan, viszont

p = 2

esetben az (1) alatti második egyenlőség sem állhat fenn, tehát nincs a feladat feltételeit kielégítő

d

szám. Ennek bizonyítását kívánta az 1953. évi verseny 2. feladata.^{$^{*}$}
Valamivel rövidebb megoldást kapunk, ha felhasználjuk az úgynevezett eukleidészi lemmát, amelyik szerint ha egy szám osztója egy szorzatnak, de relatív prím az egyik tényezőhöz, akkor osztója a másik tényezőnek.

II. megoldás: Feltétel szerint van olyan

k

és

m

egész, amelyekre

\begin{matrix} p n^{2} = d k és d + n^{2} = m^{2} . \end{matrix}

Jelöljük

n

és

m

legnagyobb közös osztóját

d'

-vel. Ekkor

n = d' n', m = d' m'

, ahol

m'

és

n'

egymáshoz relatív prím.
A fenti második egyenlőséget

k

-val végigszorozva és felhasználva az elsőt és az utolsó két egyenlőséget, az előbbi így írható:

\begin{matrix} (p + k) d'^{2} n'^{2} = k d'^{2} m'^{2}, amiből (p + k) n'^{2} = k m'^{2} . \end{matrix}

A prímtényezős felbontás egyértelműsége folytán

m'^{2}

-nek és

n'^{2}

-nek csak olyan prímek lehetnek osztói, és így közös osztói is, amelyek az alapoknak is osztói, ami esetünkben azt jelenti, hogy a két négyzet relatív prím. Az eukleidészi lemma szerint tehát

n'^{2}

, ami osztója a jobb oldalnak, kell, hogy az első tényezőnek legyen osztója. Alkalmas

k'

egésszel tehát

\begin{matrix} k = n'^{2} k' . \end{matrix}

Ezt beírva utolsó egyenlőségünkbe és egyszerűsítve azt kapjuk, hogy

\begin{matrix} p + n'^{2} k' = k' m'^{2}, \end{matrix}

vagy átrendezve

\begin{matrix} p = k' (m'^{2} - n'^{2}) = k' (m' - n') (m' + n') . \end{matrix}

Mivel

p

(pozitív) osztói csak

1

és

p

, így a jobb oldalon egy tényező értéke

p

, a másik kettőé

1

, és mivel az utolsó tényező nagyobb az előtte állónál, így

\begin{matrix} m' + n' = p, k' = m' - n' = 1, tehát n' = \frac{1}{2} (p - 1), n = \frac{1}{2} (p - 1) d' . \end{matrix}

Mindezeket beírva az első feltételi egyenlőségbe és egyszerűsítve azt kapjuk, hogy

\begin{matrix} d = p d'^{2}, \end{matrix}

tehát

p

és

n

meghatározza

d

-t ‐ feltéve, hogy egyáltalán létezik megfelelő

d

; ennek pedig az a feltétele, hogy

n

osztható legyen

\frac{1}{2} (p - 1)

-gyel.

III. megoldás: Legyen

m

olyan egész szám, amelyikre

d + n^{2} = m^{2}

, azaz

\begin{matrix} d = m^{2} - n^{2} = (m + n) (m - n) . \end{matrix}

Jelöljük

m + n

és

m - n

legnagyobb közös osztóját

d'

-vel. Ekkor alkalmas

b

és

c

egészekkel

\begin{matrix} m + n = b d', m - n = c d', \end{matrix}

ahol

b

és

c

relatív prím egymáshoz,

b > c

és

\begin{matrix} d = b c d'^{2}, 2 n = (b - c) d' . \end{matrix}

Az, hogy

d

osztója

p n^{2}

-nek, azt jelenti, hogy van olyan

k

egész, amellyel

\begin{matrix} p n^{2} = d k, \end{matrix}

vagyis

4

-gyel szorozva és a fent találtakat beírva

\begin{matrix} p {(b - c)}^{2} d'^{2} = 4 b c d'^{2} k, amiből p {(b - c)}^{2} = 4 b c k . \end{matrix}

Mivel

b

-nek és

c

-nek nincs

1

-nél nagyobb közös osztója, így

b

-nek és

c

-nek

b - c

-vel sem lehet

1

-nél nagyobb közös osztója. Ekkor azonban mind a kettő

p

-nek kell, hogy osztója legyen, tehát

\begin{matrix} b = p, c = 1, így k = {[\frac{1}{2} (p - 1)]}^{2}, d' = \frac{2 n}{p - 1}; \end{matrix}

ezekből pedig

\begin{matrix} d = p {(\frac{2 n}{p - 1})}^{2} . \end{matrix}

Ezzel azt kaptuk, hogy

p

és

n

már meghatározza

d

-t. Egyben azt is kaptuk, hogy ilyen

d

akkor van, ha

n

\frac{1}{2} (p - 1)

többszöröse.

Megjegyzések: 1. Ha

p = 2

, akkor csak annyi változik, hogy

\frac{1}{2} (p - 1)

nem egész, s így semmilyen

n

-hez nincs megfelelő

d

.
2. Mind a három megoldás módot ad az alkalmas

d

osztók megkeresésére akkor is, ha

p

helyébe tetszés szerinti összetett számot írunk. Ekkor lehet több ilyen

d

is.

^{$^{*}$}Lásd, Hajós Gy. ‐ Neukomm Gy. ‐ Surányi J.: Matematikai versenytételek II. köt., 3. kiad., Tankönyvkiadó, Budapest, 1988. 157-158.old.