Teoria liczbWyzwanieZadanie nr 3888
Suma części całkowitych liczb k³/101 dla k od 1 do 100
Oblicz sumę podaną poniżej.
Świetnie.
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
- 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}\).
- 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\).
- Ponadto \(\sum_{k=1}^{100}k^3=\Bigl(\frac{100\cdot101}{2}\Bigr)^2=25\,502\,500\).
- 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.