Teoria liczbWyzwanieZadanie nr 3793

Wielomiany o współczynnikach całkowitych, których wartości W(n) dzielą 5ⁿ − 1

Podzielność wartości wielomianów Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

Ile jest wielomianów \(W\) o współczynnikach całkowitych takich, że dla każdej dodatniej liczby całkowitej \(n\) liczba \(5^n-1\) jest podzielna przez \(W(n)\)?

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

Niech \(q\) będzie dzielnikiem pierwszym \(W(n)\). Porównaj \(W(n)\) i \(W(n+q)\) modulo \(q\) i użyj małego twierdzenia Fermata. Potem zbadaj potęgę dwójki w \(5^n-1\) dla \(n\) nieparzystych.

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Niech \(q\) będzie liczbą pierwszą dzielącą \(W(n)\) dla pewnego \(n\). Ponieważ \(W(n+q)\equiv W(n)\equiv0\pmod q\), mamy \(q\mid5^n-1\) i \(q\mid5^{n+q}-1\). Oczywiście \(q\ne5\), więc z małego twierdzenia Fermata \(5^{n+q}\equiv5^{n+1}\pmod q\), czyli \(q\mid5^{n+1}-5^n=4\cdot5^n\). Stąd \(q=2\).
  2. Zatem każda wartość \(W(n)\) jest postaci \(\pm2^j\) (wartość \(0\) nie dzieli \(5^n-1\ne0\)). Dla \(n\) nieparzystego \(5^n-1=4\,(5^{n-1}+\dots+1)\), a druga liczba jest sumą nieparzystej liczby nieparzystych składników, więc \(2^j\mid 5^n-1\) daje \(j\le2\), tzn. \(|W(n)|\le4\).
  3. Wielomian przyjmujący nieskończenie wiele razy wartości ze skończonego zbioru \(\{\pm1,\pm2,\pm4\}\) przyjmuje któryś z nich nieskończenie wiele razy, więc jest stały: \(W\equiv c\).
  4. Stała \(c\) musi dzielić \(5^1-1=4\), a każdy dzielnik \(4\) dzieli wszystkie \(5^n-1\) (bo \(5\equiv1\pmod4\)). Zatem \(c\in\{\pm1,\pm2,\pm4\}\).
  5. Takich wielomianów jest \(6\).

Odpowiedź: \(6\)

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