Teoria liczbTrudneZadanie nr 3705
Liczby pierwsze mniejsze od 200 dzielące a² + 5b² przy a, b niepodzielnych przez p
Ile jest liczb pierwszych \(p<200\), dla których istnieją liczby całkowite \(a,b\), obie niepodzielne przez \(p\), takie że \(p\mid a^2+5b^2\)?
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Dla \(p\ne2,5\) warunek oznacza, że \(-5\) jest resztą kwadratową modulo \(p\). Rozłóż symbol Legendre’a na czynniki i zastosuj prawo wzajemności.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- \(p=2\): \(a=b=1\) spełnia warunek. \(p=5\): z \(5\mid a^2\) wynika \(5\mid a\) — odpada. Dla \(p\ne2,5\) warunek jest równoważny \((ab^{-1})^2\equiv-5\pmod p\), czyli \(\left(\frac{-5}{p}\right)=1\).
- \(\left(\frac{-5}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac5p\right)\); z prawa wzajemności \(\left(\frac5p\right)=\left(\frac p5\right)\), co równa się \(1\) dokładnie dla \(p\equiv\pm1\pmod5\), a \(\left(\frac{-1}p\right)=1\iff p\equiv1\pmod4\).
- Warunek: (\(p\equiv1\pmod4\) i \(p\equiv\pm1\pmod5\)) lub (\(p\equiv3\pmod4\) i \(p\equiv\pm2\pmod5\)), czyli \(p\equiv1,3,7,9\pmod{20}\).
- Liczby pierwsze mniejsze od \(200\) tej postaci: \(3,7,23,29,41,43,47,61,67,83,89,101,103,107,109,127,149,163,167,181\) — jest ich \(20\). Razem z \(p=2\): \(21\).
Odpowiedź: \(21\)
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