# 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)\).