Teoria liczbTrudneZadanie nr 1308

Reszta iloczynu (k⁴ + 1) dla k od 1 do 100 przy dzieleniu przez 101

Kongruencje i reszty kwadratowe Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

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\).

+16 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ę

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
  1. 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)\).
  2. Liczby \(\pm10\) nie są resztami kwadratowymi modulo 101: z kryterium Eulera \((\pm10)^{50}=(10^2)^{25}\equiv(-1)^{25}=-1\pmod{101}\).
  3. 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)\).
  4. 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\).
  5. 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.

Więcej zadań z teorii liczb →

Podobne zadania