My number theory - The prime part of the blog is 5part：
Basic concepts 、 nature 、 guess 、 Theorem
Prime sieve method （ A sieve 、 Euler screen 、 Interval sieve ）
Prime judgment （ Simple method 、 model 6 Law 、Rabin-Miller And improvement ）
The decomposition of numbers （Pollard-rho）
Mason prime number （Lucas_Lehmer Judgment method ）

Basic concepts and properties

• $>1$, Positive integer , except 1 And itself cannot be divided by other numbers
• $d>1,d\in N^{\ast },pyesplainCount,d|p\Rightarrow d=p$
• $p$ Prime number ,$p|ab\Rightarrow p|aorp|b$
• There are infinite primes
• Each is greater than 1 All positive integers have a prime factor
• $n$ Is the sum , Then there will be $\le \sqrt{n}$ The prime factor of

Theorem and conjecture

guess

• Bertrand conjectures ： Arbitrary positive integer $n$ （ Greater than 1）, There are prime numbers $p$ Yes $n<p<2n$
• Twin prime conjecture ： There are an infinite number of $p$ and $p+2$ The prime number of is right
• Goldbach conjectures ： Each is greater than $2$ The positive even number of can be written as the sum of two prime numbers

Prime number theorem

• Definition $\pi (x)$ Say less than $x$ The prime number of ,$\pi (x)=\frac{x}{\ln x}$

• inference ： Definition $p_n$ For the first time $n$ Prime number ,$p_n\sim n\ln n$

Basic theorem of arithmetic

• Theorem ： Each is greater than $1$ The positive integer $n$ Can be uniquely written as the product of prime numbers $n={p_1}^{{\alpha }_1}{p_2}^{{\alpha }_2}\cdots {p_k}^{{\alpha }_k},p_1<p_2<\cdots <p_k$ And it's prime ,${\alpha }_1,{\alpha }_2,\cdots {\alpha }_k$ It's a positive integer. .

• set up $d(n)$ by $n$ Number of positive factors ,$\varphi (n)$ by $n$ The sum of all the factors of , Then there are
  $$\begin{gathered} d(n)=({\alpha }_1+1)({\alpha }_2+1)\cdots ({\alpha }_k+1) \\ \varphi (n)=\frac{{p_1}^{{\alpha }_1+1}-1}{p_1-1}\cdot \frac{{p_2}^{{\alpha }_2+1}-1}{p_2-1}\cdots \frac{{p_k}^{{\alpha }_k+1}-1}{p_k-1} \end{gathered}$$

• set up $a={{\rho }_1}^{r_1}{{\rho }_2}^{r_2}\cdots {{\rho }_k}^{r_k},b={{\rho }_1}^{s_1}{{\rho }_2}^{s_2}\cdots {{\rho }_k}^{s_k}$, be
  $$\begin{gathered} \gcd (a,b)={{\rho }_1}^{\min (r_1,s_1)}{{\rho }_2}^{\min (r_2,s_2)}\cdots {{\rho }_k}^{\min (r_k,s_k)} \\ \text{lcm}(a,b)={{\rho }_1}^{\max (r_1,s_1)}{{\rho }_2}^{\max (r_2,s_2)}\cdots {{\rho }_k}^{\max (r_k,s_k)} \end{gathered}$$

• $n!$ Prime number in prime factorization of $p$ The power of is $[\frac{n}{p}]+[\frac{n}{p^2}]+\cdots$

Wilson's theorem

• if $p$ Prime number , be $(p-1)!\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)$

Fermat's small Theorem

• If $p$ It's a haunting number , And $(a,p)=1$, that $a^{p-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$

• inference ： if $p$ Is prime and $a$ It's a positive integer. , that $a^p\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$

Euler theorem

• Euler function $\phi (n)$ ： No more than $n$ And with the $n$ The number of reciprocal positive integers ,$n$ Is a positive integer
• set up $m$ Is a positive integer , $a$ Is an integer $(a,m)=1$, that $a^{\phi (m)}\equiv$ $1(\mathrm{m}\mathrm{o}\mathrm{d}m)$.