[Teoria liczb] Interesująca teoryja liczb

[Swistak]

Dana jest nieparzysta naturalna liczba \(\displaystyle{ n}\). Udowodnij, że suma sześcianów liczb mniejszych od \(\displaystyle{ n}\) i względnie pierwszych z nią jest podzielna przez \(\displaystyle{ n^2}\).

[arek1357]

No a jeśli weźmiesz n=7 a te dwie liczby np 2 i 3 wszystkie te liczby spełniają warunki zadania
ale suma sześcianów 2 i 3 daje 35

i 49 nijak nie dzieli 35

[marcin_smu]

Ukryta treść:    

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.

[arek1357]

AAAA chodziło tu o wszystkie liczby względnie pierwsze z n ja chyba źle zrozumiałem sens zadania
ja myślałem że chodzi o 2 liczby tylko

[Swistak]

Świetnie marcin_smu . Moje rozwiązanie wygląda dokładnie tak samo i moim zdaniem jak na teorię liczb jest ono dość nietypowe :].

[jerzozwierz]

Kombinowanie.

Ukryta treść:    

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.