Prime number

Description:

• Let $p\in \mathbb{N}$ and $p>2,p$ is prime if its only positive divisors are 1 and $p$
• Otherwise, $p$ is composite, there exists $a$ such that $1<a\le \sqrt{p}$ and $a|p$theorem

The fundamental of theorem of arithmetic:

• Every natural number $n>1$ can be uniquely factored into a product of a sequence of non-decreasing primes, i.e. the unique prime factorizationtheorem
• Euclid theorem: there are infinitely many primestheorem

Prime number theorem:

• Let $\pi (N)$ be the number of primes $\le N$. Then: $\underset{N\to \infty }{\lim }\frac{\pi (N)}{N/\ln N}=1$

Relative primality:

• Two positive integers $a,b\in {\mathbb{N}}^{+}$ are relatively prime (or co-prime) if $gcd(a,b)=1$
  • Prime to each other
• Two positive integers $a,b\in {\mathbb{N}}^{+}$ are relatively prime if and only if there exists $s,t\in \mathbb{Z}$ such that $sa+tb=1$theorem
  • Extended Euclidean algorithm with prime number
• If $a$ and $b$ are relatively prime and $a|bc$, then $a|c$lemma

Pairwise relatively prime:

• The integers $a_{1,}{a}_2,...,a_n$ are pairwise relatively prime if $gcd(a_i,a_j)=1$ whenever $1\le i<j\le n$
• If integers $a_1,a_2,...,a_n$ are pairwise relatively prime, then $gcd(a_1.a_2.....a_{k+1})=1$ for all $k=1,2,...,n-1$lemma
• If integers $a_i,a_2,...,a_n$ are pairwise relatively prime, and $a_k|m$ for all $k=1,2,...,n$ and some integer $m$ then $a_1.a_2....a_n|m$theorem
  • If each of the prime divides $m$ then their product also divides $m$

Least common multiple:

• The least common multiple of the positive integers $a$ and $b$ is the smallest positive integer that is divisible by both $a$ and $b$, denoted by $lcm(a,b)$
• Let $a$ and $b$ be positive integers. Then $ab=gcd(a,b)\cdot lcm(a,b)$theorem

Multiplicative inverse:

• Let $a,b\in {\mathbb{N}}^{+}$. There exist an element $a^{-1}$ such that $a^{-1}\cdot a\equiv 1(\mathrm{mod}b)$ if and only if $a$ and $b$ are relatively prime.theorem
  • Solutions are not unique, some may not have solution
  • Inverse of a modulo

Primality

• If $p$ is prime and $p|{\Pi }_{i=1}^n{a}_i$, then there exist some $1\le j\le n$ such that $p|a_j$lemma
  • If a prime divides a product of $n$ numbers, then that prime divides at least 1 of the numbers