Teoria liczbTrudneZadanie nr 1308
Reszta iloczynu (k⁴ + 1) dla k od 1 do 100 przy dzieleniu przez 101
Oblicz resztę z dzielenia liczby \(\displaystyle\prod_{k=1}^{100}\left(k^4+1\right)=(1^4+1)(2^4+1)\cdots(100^4+1)\) przez liczbę pierwszą \(101\).
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Rozłóż \(k^4+1\) modulo 101 na dwa czynniki postaci \(k^2-c\), korzystając z tego, że \(-1\) jest kwadratem modulo 101. Sprawdź kryterium Eulera dla \(c\) i użyj wielomianu, którego pierwiastkami są wszystkie niezerowe reszty kwadratowe.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Ponieważ \(10^2=100\equiv-1\pmod{101}\), mamy \(k^4+1\equiv k^4-100=(k^2-10)(k^2+10)\pmod{101}\). Szukany iloczyn przystaje więc do \(\prod_{k=1}^{100}(k^2-10)\cdot\prod_{k=1}^{100}(k^2+10)\).
- Liczby \(\pm10\) nie są resztami kwadratowymi modulo 101: z kryterium Eulera \((\pm10)^{50}=(10^2)^{25}\equiv(-1)^{25}=-1\pmod{101}\).
- Niech \(R\) będzie zbiorem 50 niezerowych reszt kwadratowych modulo 101. Każda \(q\in R\) spełnia \(q^{50}\equiv1\), a wielomian stopnia 50 ma nad \(\mathbb Z_{101}\) co najwyżej 50 pierwiastków, więc \(x^{50}-1\equiv\prod_{q\in R}(x-q)\).
- Gdy \(k\) przebiega \(1,\dots,100\), liczba \(k^2\) przyjmuje każdą wartość z \(R\) dokładnie dwa razy (dla \(k\) i \(101-k\)). Dla \(c=\pm10\): \(\prod_{k=1}^{100}(k^2-c)=\prod_{q\in R}(q-c)^2=\Big(\prod_{q\in R}(c-q)\Big)^2\equiv\left(c^{50}-1\right)^2\equiv(-2)^2=4\).
- Cały iloczyn daje więc resztę \(4\cdot4=16\).
Odpowiedź: \(16\)
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.
Podobne zadania
- NWW i kalendarz: basen co 6 i co 9 dni, pierwszy wspólny dzień w listopadzie
- Strony książki z numerem podzielnym przez 4 lub przez 10: NWW i strony liczone dwa razy
- Dwie zamazane cyfry numeru 2□5□ podzielnego przez 4 i przez 9: ile możliwości
- Numery biletów od 150 do 400 podzielne przez 6, ale niepodzielne przez 9