Teoria liczbWyzwanieZadanie nr 3888

Suma części całkowitych liczb k³/101 dla k od 1 do 100

Sumy części całkowitych Zadania konkursoweZadania olimpijskie

Oblicz sumę podaną poniżej.

\[\sum_{k=1}^{100}\left\lfloor\frac{k^3}{101}\right\rfloor\]

+18 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

Jak rozwiązać to zadanie?

Potrzebujesz pomocy? Pokaż wskazówkę

Liczba \(101\) jest pierwsza i daje resztę \(2\) z dzielenia przez \(3\). Jakie reszty z dzielenia przez \(101\) dają sześciany \(k^3\) dla \(k=1,\ldots,100\)?

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Dla \(1\le k\le100\) niech \(r_k\in\{1,\ldots,100\}\) będzie resztą z dzielenia \(k^3\) przez \(101\). Wtedy \(\bigl\lfloor\frac{k^3}{101}\bigr\rfloor=\frac{k^3-r_k}{101}\).
  2. Odwzorowanie \(k\mapsto r_k\) jest różnowartościowe: jeśli \(k^3\equiv l^3\pmod{101}\), to \(z=kl^{-1}\) spełnia \(z^3\equiv1\), a z małego twierdzenia Fermata \(z^{100}\equiv1\); ponieważ \(\operatorname{NWD}(3,100)=1\), mamy \(z\equiv1\), czyli \(k=l\). Zatem reszty \(r_k\) są permutacją liczb \(1,\ldots,100\) i \(\sum r_k=5050\).
  3. Ponadto \(\sum_{k=1}^{100}k^3=\Bigl(\frac{100\cdot101}{2}\Bigr)^2=25\,502\,500\).
  4. Suma wynosi \(\frac{25\,502\,500-5050}{101}=\frac{25\,497\,450}{101}=252\,450\).

Odpowiedź: \(252450\)

Czego warto się nauczyć?

Teoria liczb to podzielność, reszty i cykle potęg — dział, w którym krótki pomysł zastępuje długi rachunek.

Więcej zadań z teorii liczb →

Podobne zadania