Matematyka.pl

Suma sześcianów liczb od jednego do \(\displaystyle{ n}\) jest równa \(\displaystyle{ f(n)=\frac{n^4+2 \cdot n^3 + n^2}{4}}\) (Poprawność tego wzoru można dowieść np.: tym ze spełnia on równanie \(\displaystyle{ f(n-1)+n^3=f(n)}\) ). Ponieważ \(\displaystyle{ n}\) jest nieparzyste, łatwo dowieść, że \(\displaystyle{ f(n)}\) jest podzielne przez \(\displaystyle{ n^2}\). Teza zadania jest, więc równoważna sprawdzeniu, czy suma sześcianów liczb mniejszy od \(\displaystyle{ n}\) i nie względnie pierwszych z \(\displaystyle{ n}\) jest podzielna przez \(\displaystyle{ n^2}\). Tę sumę można łatwo zapisać dzięki zasadzie włączeń i wyłączeń jako sumę czynników postaci \(\displaystyle{ \pm \sum_{i=1}^{n/x}(xi)^3}\) (x jest pewnym dzielnikiem n). Łatwo dowieść, że każdy z tych czynników jest podzielny przez \(\displaystyle{ n^2}\).
c.k.d.

Dwa proste, istotne spostrzeżenia:
1) \(\displaystyle{ k}\) jest względnie pierwsze z \(\displaystyle{ n}\) wtedy i tylko wtedy, gdy \(\displaystyle{ n-k}\) jest względnie pierwsze z \(\displaystyle{ n}\).
2) Jeśli \(\displaystyle{ k}\) jest względnie pierwsze z \(\displaystyle{ n}\), to \(\displaystyle{ 2k \ (mod \ n)}\) również.
Toteż:

\(\displaystyle{ 2 \sum_{(k,n)=1}^{} k^3 = \sum_{(k,n)=1}^{} \left( k^3 + (n-k)^3 \right) = \sum_{(k,n)=1}^{} \left( n^3 - 3n^2k + 3nk^2 \right) \equiv 3n \sum_{(k,n)=1}^{} k^2 \ (mod \ n^2)}\)

Funkcja \(\displaystyle{ f(k) = 2k \ (mod \ n)}\) jest bijekcją na zbiorze liczb naturalnych mniejszych od \(\displaystyle{ n}\) względnie pierwszych z \(\displaystyle{ n}\), więc

\(\displaystyle{ \sum_{(k,n)=1}^{} k^2 \equiv \sum_{(k,n)=1}^{} (2k)^2 \ (mod \ n) \Leftrightarrow 3 \sum_{(k,n)=1}^{} k^2 \equiv 0 \ (mod \ n)}\),

co było potrzebne do zakończenia dowodu.