Teoria liczbTrudneZadanie nr 1455

Najmniejsze l, dla którego 2^l − 9 dzieli się przez 289

Kongruencje modulo kwadrat liczby pierwszej Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

Wyznacz najmniejszą dodatnią liczbę całkowitą \(l\), dla której liczba \(2^l-9\) jest podzielna przez \(289=17^2\).

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

Najpierw rozwiąż kongruencję modulo \(17\) (rząd dwójki modulo \(17\) jest mały), a potem zapisz \(2^8\) modulo \(289\) w postaci \(1-2\cdot17\) i skorzystaj ze wzoru dwumianowego.

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Modulo \(17\): \(2^4=16\equiv-1\), więc \(2^8\equiv1\), a potęgi \(2^1,\dots,2^8\) dają reszty \(2,4,8,16,15,13,9,1\). Zatem \(2^l\equiv9\pmod{17}\) wtedy i tylko wtedy, gdy \(l\equiv7\pmod8\). Piszemy \(l=7+8t\), \(t\ge0\).
  2. Modulo \(289\): \(2^8=256=289-33\equiv-33=1-34\). Ze wzoru dwumianowego \((1-34)^t\equiv1-34t\pmod{289}\), bo dalsze składniki dzielą się przez \(34^2\), a więc przez \(17^2\).
  3. Zatem \(2^{7+8t}\equiv128(1-34t)=128-4352t\equiv128-17t\pmod{289}\), gdyż \(4352=15\cdot289+17\).
  4. Warunek \(128-17t\equiv9\pmod{289}\) oznacza \(17t\equiv119=7\cdot17\pmod{289}\), czyli \(t\equiv7\pmod{17}\). Najmniejsze \(t\ge0\) to \(7\), więc \(l=7+8\cdot7=63\).

Odpowiedź: \(63\)

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