Prime Numbers

A prime number is an integer \(p\) greater than one where only 1 and \(p\) divide it.
- e.g. 2, 3, 5, 7, 11, 13, 17, 19, … are primes.
Non-prime integers greater than one are composite.
- 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.
For example:
- \(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}\).∎
This gives us at least one algorithm to check if a number is prime.
- 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.∎

GCD and LCM

For two integers \(a\) and \(b\), the greatest common divisor of then is the largest integer \(d\) such that \(d\mid a\) and \(d\mid b\).
- For example, \(\mathrm{gcd}(360,756)=36\).
The GCD is the thing you need to divide by when reducing a fraction: \(360/756 = 10/21\).
We already saw the Euclidean Algorithm to find the GCD.
If we have the prime factorization, we can just read the GCD off.
- 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\).
But if we don't already have the prime factorizations, Euclid's algorithm will be much quicker.
The least common multiple of \(a\) and \(b\) is the smallest positive integer \(m\) such that \(a\mid m\) and \(b\mid m\).
We can also find the LCM with the prime factorizations.
- 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.∎
That theorem gives a much better algorithm than the prime factorization method: use Euclid's method and return \(a\times b/ \mathrm{gcd}(a,b)\).