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 file
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

Bizonyítsuk be, hogy minden számnak legalább annyi 4k+1 alakú osztója van, mint ahány 4k-1 alakú!

"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 N1 szám esetén jelölje L(N) és K(N) az N szám 4k+1, illetve 4k-1 alakú osztóinak a számát. Legyen még D(N)=L(N)-K(N), azt kell megmutatnunk, hogy D(N)0. Ehhez szükségünk lesz a D(N) függvénynek az alábbi tulajdonságára:
Ha N1 és N2 relatív prímek, akkor
D(N1N2)=D(N1)D(N2).(1)
(1) bizonyításához legyenek N1 és N2 relatív prímek. Az N1N2 páratlan osztói pontosan azok az n1n2 alakban írható számok, melyekre n1 az N1-nek, n2 pedig az N2-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:
L(N1N2)=L(N1)L(N2)+K(N1)K(N2),(2)
K(N1N2)=K(N1)L(N2)+L(N1)K(N2).(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=p1α1p2α2...pnαn, akkor (1) ismételt alkalmazásával
D(N)=D(p1α1)D(p2α2)...D(pnαn).(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 p0,p,p2,...,pα. Ezek közül biztosan 4k+1 alakúak azok, ahol p kitevője páros ‐ ha p 4k-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α)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 4k-1 alakú, akkor közvetlenül adódik, hogy a kétféle páratlan osztók száma egyenlő. Ilyenkor ugyanis a dN/d megfeleltetés kölcsönösen egyértelműen képezi le a 4k-1 alakú osztók halmazát a 4k+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 4k-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.