Kezdőlap


Feladat:	C.535	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Bohák András , Springer Éva
Füzet:	1999/október, 402 - 403. oldal		PDF \| MathML
Témakör(ök):	Prímtényezős felbontás, C gyakorlat
Hivatkozás(ok):	Feladatok: 1999/március: C.535

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.

A $285 = a + (285 - a)$ egyenlet azon pozitív egész megoldásait keressük, amelyekre $a$ és $285 - a$ relatív prímek. Ez pontosan azt jelenti, hogy $a$ és 285 relatív prímek. Valóban, ha egy $d$ egész osztója $a$ -nak is és 285-nek is, akkor ( $a$ -nak és) $(285 - a)$ -nak is osztója; megfordítva, ha egy $d$ egész osztója $a$ -nak is és $(285 - a)$ -nak is, akkor osztója ( $a$ -nak és) $a + (285 - a) = 285$ -nek is. Tehát $a$ és 285 legnagyobb közös osztója egyenlő $a$ és $(285 - a)$ legnagyobb közös osztójával.
Keressük tehát a 285-nél kisebb számok közül azokat, amelyek 285-höz relatív prímek.
Ismeretes, hogy ha az $n$ prímtényezős felbontása

\begin{matrix} n = p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \cdot ... \cdot p_{k}^{α_{k}}, \end{matrix}

akkor a hozzá relatív prím számok számát a

\begin{matrix} φ (n) = n \cdot (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) ... (1 - \frac{1}{p_{k}}) \end{matrix}

összefüggés adja.
Esetünkben

n = 285 = 3 \cdot 5 \cdot 19

, és így

\begin{matrix} φ (285) = 285 (1 - \frac{1}{3}) (1 - \frac{1}{5}) (1 - \frac{1}{19}) = 285 \cdot \frac{2}{3} \cdot \frac{4}{5} \cdot \frac{18}{19} = 144, \end{matrix}

a relatív prím számok száma. Mint láttuk, ezek páronként csoportosíthatók úgy, hogy a párok összege 285. Így összesen 72 megfelelő számpár van.

Springer Éva (Budapest, Szent István Gimn., 9. o.t.)

Megjegyzés. A feladatot megoldhatjuk a

φ

függvény ismerete nélkül is, ha megszámoljuk, hány olyan szám van 285-ig, amely osztható 3-mal, 5-tel, 19-cel,

3 \cdot 5 = 15

-tel,

3 \cdot 19 = 57

-tel,

5 \cdot 19 = 95

-tel és

3 \cdot 5 \cdot 19 = 395

-tel:

3-mal	95 darab szám,
5-tel	57 darab szám,
19-cel	15 darab szám osztható,

ezek összegéből kell levonni a 15-tel, 57-tel, 95-tel és

3 \cdot 5 \cdot 19 = 285

-tel osztható számok számát, azaz

95 + 57 + 15 - 18 - 5 - 3 + 1 = 141

-et, mert ezekből nem képezhetők relatív prím számpárok. A maradék

285 - 141 = 144

-ből viszont igen.

Bohák András (Budapest, Evangélikus Gimn., 10. o.t.)