Teoria liczbTrudneZadanie nr 1455
Najmniejsze l, dla którego 2^l − 9 dzieli się przez 289
Wyznacz najmniejszą dodatnią liczbę całkowitą \(l\), dla której liczba \(2^l-9\) jest podzielna przez \(289=17^2\).
Świetnie.
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
- 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\).
- 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\).
- Zatem \(2^{7+8t}\equiv128(1-34t)=128-4352t\equiv128-17t\pmod{289}\), gdyż \(4352=15\cdot289+17\).
- 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.
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