Kezdőlap


Feladat:	F.2470	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Argay Gy. , Bán Rita , Bujdosó L. , Edvi T. , Fülöp T. , Füst Ágnes , Gáspár Zsuzsanna , Hajdú S. Z. , Hetyei Judit , Hraskó A. , Karácsony P. , Kerner Anna , Kós G. , Kovács 111 S. , Köpösdi P. , Ladányi L. , Magyar Á. , Megyesi G. , Pfeil T. , Pintér A. , Szabó Sz. , Uhlmann E. , Varga K.
Füzet:	1985/január, 17 - 18. oldal		PDF \| MathML
Témakör(ök):	Prímtényezős felbontás, Osztók száma függvény, Számelméleti függvények, Feladat
Hivatkozás(ok):	Feladatok: 1984/április: F.2470

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.

"Szám''-on a feladat szövegében és a megoldás során is értelemszerűen pozitív egész számot értünk.
Adott $N \geq 1$ szám esetén jelölje $L (N)$ és $K (N)$ az $N$ szám $4 k + 1$ , illetve $4 k - 1$ alakú osztóinak a számát. Legyen még $D (N) = L (N) - K (N)$ , azt kell megmutatnunk, hogy $D (N) \geq 0$ . Ehhez szükségünk lesz a $D (N)$ függvénynek az alábbi tulajdonságára:
Ha $N_{1}$ és $N_{2}$ relatív prímek, akkor

\begin{matrix} D (N_{1} \cdot N_{2}) = D (N_{1}) \cdot D (N_{2}) . \end{matrix}

(1)

(1) bizonyításához legyenek

N_{1}

és

N_{2}

relatív prímek. Az

N_{1} \cdot N_{2}

páratlan osztói pontosan azok az

n_{1} \cdot n_{2}

alakban írható számok, melyekre

n_{1}

N_{1}

-nek,

n_{2}

pedig az

N_{2}

-nek páratlan osztója. Két páratlan szám szorzata pedig

4

-gyel osztva aszerint ad

1

vagy

- 1

maradékot, hogy maga a két szám

4

-gyel osztva egyforma maradékot ad-e vagy sem. Ennek alapján az alábbi összefüggésekhez jutunk:

\begin{matrix} L (N_{1} \cdot N_{2}) = L (N_{1}) \cdot L (N_{2}) + K (N_{1}) \cdot K (N_{2}), \end{matrix}

(2)

\begin{matrix} K (N_{1} \cdot N_{2}) = K (N_{1}) \cdot L (N_{2}) + L (N_{1}) \cdot K (N_{2}) . \end{matrix}

(3)

(2)-ből (3)-at kivonva éppen (1)-et kapjuk.

A feladat állítása most már könnyen adódik a következők alapján. A számelmélet alaptétele szerint minden szám egyértelműen felírható különböző prímszámok nem negatív egész kitevős hatványainak szorzataként. Mivel pedig különböző prímek hatványai egymáshoz relatív prímek, így ha

N = p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} ... p_{n}^{α_{n}}

, akkor (1) ismételt alkalmazásával

\begin{matrix} D (N) = D (p_{1}^{α_{1}}) \cdot D (p_{2}^{α_{2}}) \cdot ... \cdot D (p_{n}^{α_{n}}) . \end{matrix}

(4)

Vizsgáljuk most meg

D (N) = D (p^{α})

értékét, ahol

p

prím,

α

pedig pozitív egész!
Ha

p = 2

, akkor

D (p^{α}) = 1 - 0 = 1

, hiszen

2^{α}

egyetlen páratlan osztója az

1

.
Ha

p

páratlan prím, akkor

p^{α}

osztói

p^{0}

p

p^{2}

...

p^{α}

. Ezek közül biztosan

4 k + 1

alakúak azok, ahol

p

kitevője páros ‐ ha

p

4 k - 1

alakú, akkor pontosan ezek, egyébként valamennyi. Mivel pedig az

α

-nál nem nagyobb nem negatív egészeknek legalább a fele páros, azért

D (p^{α}) \geq 0

.
Azt kaptuk, hogy

D (N)

nem negatív számok szorzataként áll elő, így maga sem lehet negatív. Ezzel a bizonyítást befejeztük.

Megjegyzések. Ha

N

4 k - 1

alakú, akkor közvetlenül adódik, hogy a kétféle páratlan osztók száma egyenlő. Ilyenkor ugyanis a

d \to N / d

megfeleltetés kölcsönösen egyértelműen képezi le a

4 k - 1

alakú osztók halmazát a

4 k + 1

alakú osztók halmazára.
A bizonyítás alapján általában is jellemezhetjük azokat a számokat, amelyekre

L (N) = K (N)

. A (4) felbontás szerint erre pontosan akkor kerül sor, ha

N

prímfelbontásában van olyan

p^{α}

tényező, melyre

D (p^{α}) = 0

. Ez pedig nyilván akkor és csak akkor igaz, ha

p

4 k - 1

alakú és

α

páratlan.
Azokat a számelméleti függvényeket, amelyekre teljesül (1), azaz a prímhatványokon fölvett értékeik a megoldásban látható módon határozzák meg őket, multiplikatív függvényeknek nevezzük. Többek között ilyen az

n

szám osztóinak

d (n)

száma,

σ (n)

összege és az Euler-féle nevezetes

φ (n)

függvény is, amely az

n

-nél kisebb,

n

-hez relatív prím számok száma.