Harda teoria liczba

Tw. Lagrange’a Wielomian stopnia n ma najwyzej n różnych pierwiastków modulo p.

Reszty kwadratowe modulo pJest \frac{p+1}{2} reszt kwadratowych i \frac{p−1}{2} niereszt kwadratowych. Dla (\frac{a}{p}) = 1, jeśli a jest niezerow _{}a reszt _{}a kwadratow _{}a modulo p albo -1, jeśli a jest niereszt _{}a, albo 0, jeśli a jest podzielne przez p.

Kryterium Eulera Dla a ≠ 0 (\frac{a}{p}) ≡ a^{\frac{p−1}{2}} (mod p).

Prawo multiplikatywności Dla (\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p}).

Prawo wzajemności reszt kwadratowychDla p, q ∈ ℙ, p, q > 2 zachodzi (\frac{p}{q})(\frac{q}{p}) = (−1)^{\frac{p−1}{2} \frac{q−1}{2}} .

Fakt x^{2} + y^{2} (dla x, y ∈ ℕ, GCD(x, y) = 1) nie dzieli si_{}e przez liczby postaci 4k + 3.

Twierdzenie Każda liczba pierwsza p przystaj _{}aca do 1 modulo 4 przedstawia si_{}e w postaci x^{2} + y^{2} dla x, y ∈ ℕ.

Twierdzenie Każda liczba naturalna, której czynniki pierwsze daj _{}a reszt_{}e 1 modulo 4 lub wyst_{}epuj _{}a w pot_{}egach parzystych przedstawia si_{}e w postaci x^{2} + y^{2} dla x, y ∈ ℕ.

Twierdzenie Lagrange’a Dowolna liczba naturalna jest sum _{}a czterech kwadratów liczb całkowitych.

Fakt Niech p_{1} < p_{2} < … < p_{π(n)} b_{}ed _{}a wszystkimi liczbami pierwszymi mniejszymi niż n. Wówczas p_{1}p_{2} …p_{n} 4^{n}.

Asymptotyka \frac{π(n)}{n/ln(n)} → 1 dla n → ∞.

Postulat Bertranda Wśród liczb n, n + 1, n + 2, …, 2n (dla każdego n ∈ ℕ) wyst_{}epuje liczba pierwsza.

Generator Istnieje generator modulo p^{α} i 2p^{α} dla p ∈ ℙ, 2 ∤ p.