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