Teoria liczbTrudneZadanie nr 3705

Liczby pierwsze mniejsze od 200 dzielące a² + 5b² przy a, b niepodzielnych przez p

Reszty kwadratowe Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

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

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

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
  1. \(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\).
  2. \(\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\).
  3. 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}\).
  4. 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.

Więcej zadań z teorii liczb →

Podobne zadania