---
title: Prime Number Theorem
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# Prime Number Theorem
The number of primes less than $N$ is about $\frac{N}{logN}$

## Lemma 1
- $n$ is prime if and only if the solutions of $x^2 \equiv 1\ (mod\ n)$ are $x = \pm1$

Proof:
$$
\begin{split}
x^2 &\equiv 1\ (mod\ n) \\
x^2 - 1 &\equiv 0\ (mod\ n) \\
(x+1)(x-1) &\equiv 0\ (mod\ n) \\
\end{split}
$$

有以下兩種情況能使上式成立
- $(x+1) \equiv 0\ (mod\ n)$
- $(x-1) \equiv 0\ (mod\ n)$

若 $n$ 是 prime，則 $x$ 只能是 $p-1$ 或 $1$
而 $p-1 \equiv -1\ (mod\ n)$，所以可以改寫為 $x = \pm 1$