Prime Number

A natural number $p>1$ is called prime (or a prime number) if its only positive divisors are 1 and $p$ itself. Otherwise, $p$ is called composite.

Converting this page mostly for Competitive Programming.

Problems:

• Generate Prime Numbers → use Sieve of Erastosthenes
• Primality Test
• Prime Factorization
  • A lot of ways to do this, I’m not sure which one to choose
  • Apparently you can use Floyd’s Cycle-Finding Algorithm to solve!! That is insane

Propositions and Theorems (From MATH135)

Prime Factorization (PF) Every natural number $n>1$ can be written as a product of prime.

Euclid’s Theorem (ET) The number of primes is infinite.

Euclid’s Lemma (EL) For all integers $a$ and $b$, and prime numbers $p$, if $p|ab$, then $p|a$ or $p|b$.

Proposition 14 Let $p$ be a prime number, $n$ be a natural number, and $a_1,a_2,\dots ,a_n$ be integers. If $p|(a_1{a}_2\dots a_n)$ , then $p|a_i$ for some $i=1,2,\dots ,n$

Unique Factorization Theorem (UFT) Every natural number $n>1$ can be written as a product of prime factors uniquely, apart from the order of factors.

Finding a Prime Factor (FPF) Every natural number $n>1$ is either prime or has a prime factor less than or equal to $\sqrt{n}$.

Divisors From Prime Factorization (DFPF) Let $n$ and $c$ be positive integers, and let
$n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_k^{{\alpha }_k}$ be a way to express $n$ as a product of the distinct primes $p_1,p_2,\dots ,p_k,$ where some or all of the exponents may be zero. The integer $c$

$c|n⟺c=p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_k^{{\beta }_k},\text{where }0\le {\beta }_i\le {\alpha }_i\text{ for }i=1,2,\dots ,k$

GCD From Prime Factorization (GCD PF) Let $a$ and $b$ be positive integers, and let
$a=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_k^{{\alpha }_k}$, and $b=p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_k^{{\beta }_k}$ be ways to express $a$ and $b$ as products of the distinct primes $p_1,p_2,\dots ,p_k$, where some or all of the exponents may be zero. We have $\gcd (a,b)=p_1^{{\lambda }_1}{p}_2^{{\lambda }_2}\dots p_k^{{\lambda }_k}\text{where }{\lambda }_i=\min \{{\alpha }_i,{\beta }_i\}\text{for }i=1,2,\dots ,k$