• e.g. 2, 3, 5, 7, 11, 13, 17, 19, … are primes.

• That is, $n$ is a composite number if there is some integer $a$ with $1<a<n$ and $a\mid n$.
• e.g. 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, … are composite.

Theorem: [Fundamental Theorem of Arithmetic] Every positive integer greater than one can be written uniquely as a product of primes.

• $483=3\times 7\times 23$.
• $567=3^4\times 7$.
• $645868=2^2\times 61\times 2647$.

Theorem: A composite integer $n$ has a prime factor less than or equal to $\sqrt{n}$.

Proof: By the definition, we know that there is an $a$ with $1<a<n$ and $a\mid n$. Thus, $n=ab$ for some integer $b$. Either $a$ or $b$ must be at most $\sqrt{n}$. Without loss of generality, assume that $a\le\sqrt{n}$.

By the fundamental theorem, $a$ can be written as a product of primes. Let $p$ be one of the primes in the factorization of $a$. Now, $p$ is a prime, and $p\le a\le \sqrt{n}$.∎

• Try primes 2 up to $\lfloor\sqrt{n}\rfloor$ to see if any divide ($n \mathop{\mathrm{mod}} a =0$). If none, then it's prime.
• Or instead of checking all primes, just check all integers: probably faster than calculating the primes.

Theorem: There is an infinite number of prime numbers.

Proof: Suppose not, that we can list all prime numbers: $p_1,p_2,\ldots,p_n$. Then let $q=p_1 p_2 \cdots p_n + 1$.

The value $q$ is not divisible by any of the primes in our list: it has a remainder of one when divided by each of them. Thus it must either be another prime, or be divisible by some other prime not listed.∎

• For example, $\mathrm{gcd}(360,756)=36$.

• e.g. $360=2^3\times 3^2\times 5$ and $756=2^2\times 3^3\times 7$.
• We know whatever divides both will have $2^2$ (at most), since any larger a power wouldn't divide 756.
• So we can just read off the minimum power on each prime in both factorizations.
• In this example, that's $2^2\times3^2=36$.

• e.g. $360=2^3\times 3^2\times 5$ and $756=2^2\times 3^3\times 7$.
• We know whatever both of those divide both will have $2^3$ (or more), since any smaller a power wouldn't be a multiple of 360.
• We can read off the maximum power on each prime in both factorizations.
• In this example, that's $2^3\times3^3\times 5\times 7=7560$.

Theorem: For positive integers $a$ and $b$, we have $ab=\mathrm{gcd}(a,b)\cdot\mathrm{lcm}(a,b)$.

Proof idea: Given that stuff about finding them with prime factorizations, we can multiply the two results together and get all of the same powers of the primes.∎