Feladat: F.3202 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Devecsery András ,  Gáli Gergely ,  Gerbicz Róbert ,  Gueth Krisztián ,  Gyenes Zoltán ,  Juhász András ,  Léka Zoltán ,  Lippner Gábor ,  Mansur Boase ,  Mecz Balázs ,  Papp Dávid ,  Pataki Péter ,  Pogány Ádám ,  Szabadka Zoltán ,  Székelyhidi Gábor ,  Terpai Tamás ,  Végh A. László ,  Zábrádi Gergely ,  Zawadowski Ádám 
Füzet: 1999/január, 32 - 33. oldal  PDF file
Témakör(ök): Prímtényezős felbontás, Feladat
Hivatkozás(ok):Feladatok: 1997/december: F.3202

Legyen n prímtényezős felbontása p1α1p2α2...ptαt. Jelölje r1, r2, ..., rm azokat az n-nél kisebb pozitív egész számokat, amelyek n-hez relatív prímek. Mutassuk meg, hogy
r12+r22+...+rm2=m3(n2+12(-1)tp1p2...pt).(2)


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.

Az N*=r12+r22+...+rm2 kifejezés értékét a logikai szita formula segítségével fogjuk meghatározni, azaz 1-től n-ig összeadjuk az egész számok négyzeteit, majd kivonjuk azon számok négyzeteit, amelyeknek van közös osztójuk n-nel. Ha k az n osztója, akkor jelölje N(k) az n-nél nem nagyobb, k-val osztható pozitív egész számok négyzetösszegét. Ekkor a logikai szita formula szerint

N*=N(1)-N(p1)-N(p2)-...-N(pt)+N(p1p2)+...+N(pt-1pt)--N(p1p2p3)-...-N(pt-2pt-1pt)+...+(-1)tN(p1p2...pt).
Felhasználva az ismert
N(k)=k2+(2k)2+...+n2=k2(12+22+...+(nk)2)==k2nk(nk+1)(2nk+1)6=n33k+n22+n6k
egyenlőséget, kapjuk, hogy
N*=n33(1-1p1-1p2-...-1pt+1p1p2...+1pt-1pt--1p1p2p3-...-1pt-2pt-1pt+...+(-1)t1p1p2...pt++n22(1-(t1)+(t2)-(t3)+...+(-t)t(tt))+n6(1-p1-p2-...-pt)++p1p2+...+pt-1tt-p1p2p3-...-pt-2pt-1tp+...+(-1)t(p1p2...pt)).

A binomiális tétel szerint:
1-(t1)+(t2)-(t3)+...+(-1)t(tt)=0,
tehát az n-ben másodfokú tag együtthatója 0. Az n-ben harmad-, illetve elsőfokú tagok együtthatója szorzattá alakítható, és így:
N*=n33(1-1p1)(1-1p2)...(1-1pt)+n6(1-p1)(1-p2)...(1-pt)==n3(1-1p1)(1-1p2)...(1-1pt)(n2+12(-1)tp1p2...pt).
Ismert összefüggés, hogy m=φ(n)=n(1-1p1)...(1-1pt). Ebből
N*=m3(n2+12(-1)tp1p2...pt)
valóban.