Kezdőlap


Feladat:	1980. évi Kürschák matematikaverseny 2. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Beleznay Ferenc , Bohus Géza , Gellér János , Horváth István , Király Zoltán , Szabó Endre , Szabó László , Tardos Gábor , Umann Gábor
Füzet:	1981/február, 55 - 57. oldal		PDF \| MathML
Témakör(ök):	Maradékos osztás, Természetes számok, Egyenletek, Oszthatóság, Prímszámok, Prímtényezős felbontás, Legnagyobb közös osztó, Egyenlőtlenségek, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 1981/február: 1980. évi Kürschák matematikaverseny 2. 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.

2. feladat. Legyen $n > 1$ páratlan egész szám. Bizonyítsuk be, hogy akkor és csak akkor léteznek olyan $x$ , $y$ természetes számok, melyekre

\begin{matrix} \frac{4}{n} = \frac{1}{x} + \frac{1}{y}, \end{matrix}

(1)

n

-nek van

4 k - 1

alakú prímosztója.

I. megoldás. Tegyük fel, hogy van az egyenletnek pozitív egész

x

y

megoldása. Legyen a két szám legnagyobb közös osztója

d

, azaz

\begin{matrix} x = d x_{1}, y = d y_{1}, \end{matrix}

ahol

x_{1}

és

y_{1}

pozitív egész és nincs 1-nél nagyobb közös osztójuk, más szóval relatív prímek. Ezt beírva az egyenletbe és a törteket eltávolítva, azt kapjuk, hogy

\begin{matrix} 4 d x_{1} y_{1} = n (x_{1} + y_{1}) . \end{matrix}

(2)

Itt

n

páratlan volta miatt a jobb oldal csak úgy lehet 4-gyel osztható, ha

x_{1} + y_{1}

osztható 4-gyel. Ekkor

x_{1}

és

y_{1}

vagy mindkettő páros vagy mindkettő páratlan. Mivel ezen kívül relatív prímek is, csak a második eset következhet be. Minthogy pedig az összegük osztható 4-gyel, ez csak úgy lehet, ha az egyik

4 k + 1

alakú, a másik

4 k - 1

alakú.
A (2) összefüggés szerint

x_{1}

osztója az

n (x_{1} + y_{1})

szorzatnak.

x_{1} + y_{1}

-hez azonban relatív prím, hiszen ha volna 1-nél nagyobb közös osztójuk, az osztója volna

(x_{1} + y_{1}) - x_{1} = y_{1}

-nek is, azonban

x_{1}

és

y_{1}

relatív prímek. Ismeretes, hogy ebben az esetben

x_{1}

csak úgy lehet osztója a szorzatnak, ha a másik tényezőjének,

n

-nek is osztója. Ugyanígy következik, hogy

y_{1}

is osztója

n

-nek.
Az

x_{1}

-re és

y_{1}

-re tett megállapításaink alapján következik, hogy ha megoldható az egyenlet, akkor van

n

-nek

4 k - 1

alakú osztója. Ekkor azonban van ilyen alakú prímosztója is. Ha ugyanis egy

4 k - 1

alakú számot akárhogy felbontunk tényezőkre, akkor azok közt van

4 k - 1

alakú. Valóban, számunk páratlan, így a felbontás tényezői is páratlanok, akkor pedig vagy

4 k + 1

vagy

4 k - 1

alakúak. Két előbbi alakú szám szorzata is ilyen alakú:

\begin{matrix} (4 k_{1} + 1) (4 k_{2} + 1) = 4 (4 k_{1} k_{2} + k_{1} + k_{2}) + 1, \end{matrix}

és ez az alak újabb ilyen tényezőkkel szorozva sem változik meg. Elő kell tehát fordulnia

4 k - 1

alakúnak is. Ez igaz akkor is, ha prímtényezőkre bontottuk a számot. Így

n

4 k - 1

alakú osztójának van

4 k - 1

alakú prímosztója, de ez osztója

n

-nek is.
Tegyük most fel, hogy

p = 4 k - 1

n

-nek egy prímosztója:

n = p \cdot m

. Ekkor

\begin{matrix} \frac{4}{n} = \frac{4 k}{k \cdot p \cdot m} = \frac{p + 1}{k \cdot p \cdot m} = \frac{1}{k m} + \frac{1}{k p m}, \end{matrix}

tehát

x = k m

y = k p m

megoldása az egyenletnek. Ezzel a feladat állítását bebizonyítottuk.

Megjegyzések. 1. Felhasználtuk azt a tételt, hogy ha egy egész szám osztója egy szorzatnak, de annak egyik tényezőjéhez relatív prím, akkor osztója a másik tényezőnek. Ez következik a számelmélet alaptételéből, ami szerint minden 1-nél nagyobb természetes szám felbontható véges sok (pozitív) prímszám szorzatára és ez a felbontás a tényezők sorrendjétől eltekintve egyértelmű. Fordítva, az alaptétel is következik a fent kimondott tételből, az pedig bizonyítható az alaptétel felhasználása nélkül.
2. A bizonyítás befejező részében nem használtuk ki, hogy

p

prím, tehát képleteink

n

minden

4 k - 1

alakú osztójához megadnak egy megoldást.
3. A megoldás első részének gondolatmenetét folytatva

n = n' x_{1}

és

x_{1}

y_{1}

relatív prím volta miatt a jobb oldali szorzat csak úgy lehet

y_{1}

-gyel osztható, ha

n'

osztható vele:

n' = m y_{1}

. Ezeket beírva (2)-be

m (x_{1} + y_{1}) = 4 d

adódik.
Láttuk továbbá, hogy

x_{1} + y_{1}

osztható 4-gyel, így

x_{1} + y_{1} = 4 e

jelöléssel

\begin{matrix} (3_{1}) n = m x_{1} (4 e - x_{1}), (3_{2}) x = e m x_{1}, (3_{3}) y = e m (4 e - x_{1}) . \end{matrix}

Ebből is világos, hogy

x_{1}

és

4 e - x_{1} = y_{1}

közül az egyik

4 k + 1

, a másik

4 k - 1

alakú.
Mivel

x

és

y

szerepe szimmetrikus, feltehetjük, hogy

x_{1}

4 k + 1

alakú. Tudjuk már, hogy

x_{1}

és

4 e - x_{1}

relatív prímek.
Azt kaptuk tehát, hogy az (1) egyenlet összes megoldását megkapjuk, ha vesszük

n

-nek

(3_{1})

alakú felbontásait, amelyekben

x_{1}

és

4 e - x_{1}

relatív prímek, és képezzük hozzájuk a

(3_{2})

(3_{3})

képletek szerinti értékeket, továbbá a két szám felcserélésével keletkező számpárt.

x

és

y

mindig különböző, mert

x_{1}

és

4 e - x_{1}

nem lehet egyenlő.

n

-nek minden

t = 4 j - 1

alakú osztójához van legalább egy

(3_{1})

alakú felbontása. Válasszuk ugyanis

t - t

4 e - x_{1}

-nek,

x_{1}

-nek pedig az

n / t

bármelyik

4 k + 1

alakú és

t

-hez relatív prím osztóját (az 1 mindig ilyen). Ekkor

e = (t + x_{1}) / 4

egész és

m = n / (t x_{1})

. (Megoldást kapunk akkor is, ha

t

és

x_{1}

nem relatív prím, csak így egyes megoldásokat többször is megkaphatunk.)

II. megoldás. A feladatnak csak azt a részét bizonyítjuk, hogy ha az (1) egyenlet megoldható, akkor van

n

-nek

4 k - 1

alakú prímosztója. A törteket eltávolítva és 0-ra redukálva a

\begin{matrix} 4 x y - n (x + y) = 0 \end{matrix}

összefüggést kapjuk. Szorozzunk 4-gyel és adjunk mindkét oldalhoz

n^{2}

-et, ekkor a bal oldal szorzattá alakítható.

\begin{matrix} (4 x - n) (4 y - n) = n^{2} . \end{matrix}

Itt a bal oldali tényezők pozitívok, mert (1)-ből

1 / x

is,

1 / y

is kisebb

4 / n

-nél, s így

\begin{matrix} 4 x > n, 4 y > n . \end{matrix}

n

-nek nincs

4 k - 1

alakú prímosztója, akkor nem állhat fenn az egyenlet, ekkor ugyanis

4 x - n

is,

4 y - n

4 k - 1

alakú, tehát mint az előző megoldásban láttuk, van

4 k - 1

alakú prímosztójuk. Ekkor azonban a bal oldalt prímtényezőkre bontva, azok közt lennének

4 k - 1

alakú prímek, a jobb oldalon viszont beírva

n

prímtényezős felbontását, csupa

4 k + 1

alakú prímszám szorzata állna, ez pedig ellentmond annak, hogy minden 1-nél nagyobb természetes szám a tényezők sorrendjétől eltekintve egyértelműen írható fel prímtényezők szorzataként.

Megjegyzés. Lényeges volt, hogy a természetes számok körére szorítkozunk, s ezért meg kellett állapítani, hogy a szorzat tényezői pozitívok. Ezt a legtöbb versenyző, aki ezt az utat választotta, elmulasztotta. Pedig írhatjuk az egyenlőséget

\begin{matrix} (n - 4 x) (n - 4 y) = n^{2} \end{matrix}

alakban is, és ekkor semmi probléma nem látszik adódni abból, ha

n

minden prímosztója

4 k + 1

alakú. Valóban van is megoldása az (1) egyenletnek, ha csak azt kívánjuk, hogy

x

és

y

egész legyen és

n = 4 k + 1

\begin{matrix} \frac{4}{n} = \frac{4 k}{k n} = \frac{n - 1}{k n} = \frac{1}{k} - \frac{1}{k \cdot n} = \frac{1}{k} + \frac{1}{- k n} . \end{matrix}