2.4. Fundamental theorem

I will present to you a more modern treatment of this very old theorem than what you are likely to find in textbooks. I need some basic notation for this.

Notation.

1. ${\sum }_{i=1}^n{\alpha }_i:={\alpha }_1+\cdots +{\alpha }_n$. (Summation)
2. ${\prod }_{i=1}^n{\alpha }_i:={\alpha }_1\cdots {\alpha }_n$ (Product)

If $S$ is a finite set of integers, ${\sum }_{x\in S}x$ is the sum over all elements of $S$. The product is defined the same way. In the case when $S=\varnothing$, I define ${\sum }_{x\in \varnothing }=0$ (the additive identity) and ${\prod }_{x\in \varnothing }=1$ (the multiplicative identity).

Multiplicity

Definition.

Given a positive integer $a$ and a prime $p$, the multiplicity of $a$ with respect to $p$, in symbols, ${\mathrm{mult}}_p(a)$, is the largest integer $k$ such that $p^k\mid a$.

Reflect.

Why does the multiplicity exist? In other words, is it clear to you that the aforementioned set always has a largest element?

Examples.

$p$	$a$	${\mathrm{mult}}_p(a)$
$2$	$4$	$2$
$2$	$6$	$1$
$3$	$6$	$1$
$5$	$7$	$0$

The fundamental theorems

Old fundamental theorem of arithmetic.

Every positive integer is the product of primes. This product is unique up to permutations.

I will give a precise definition of the word permutation in a later chapter. For now, it just means that the order of the primes with positive multiplicity might change and yet I do not consider them different products. The examples below illustrate this idea.

Reflect.

Most textbooks state the theorem by adding “every integer bigger than 1.” Did I make a typo above?

Here is my preferred way of stating the main result of this section.

Fundamental theorem of arithmetic (FTA).

For any $n>0$,

$$n=\prod _{p\text{ prime}}{p}^{{\mathrm{mult}}_p(n)}.$$

Reflect.

I have not (and will not, in this course) defined the concept of an infinite product. There are infinitely many primes, so how is the above well-defined?

A crucial observation is that in the above product, primes with zero multiplicity do not contribute to the product (since they add a factor of $1$), so I only ever need to consider the primes with positive multiplicity, of which there could be none as in the first example below.

Examples.

1. $1={\prod }_{p\in \varnothing }$ (empty product)
2. $7=7$ (product with a single factor, a prime)
3. $14=2\cdot 7$ (product with two different primes)
4. $9=3^2$ (product with one prime but of higher multiplicity)

Proof of the fundamental theorems

I divide the proof of the fundamental theorem into its two basic components.

Lemma ( Existence part of FTA).

Every integer bigger than 1 is the product of primes.

Lemma ( Uniqueness part of FTA).

Two products of primes are equal only if the factors are permutations of each other. (In other words, the set of primes are the same.)

Reflect.

How do the two lemmas actually prove FTA?

Proof of Existence:

Suppose that the lemma fails. Then, by the well-ordering principle, there must exist a least counterexample $n>1$. That is, $n$ is not the product of primes. Obviously, $n$ itself cannot be prime, so there exist two integers $a$ and $b$ such that $1<a,b<n$ and $ab=n$. By minimality (this word is defined in Induction), both $a$ and $b$ are products of primes. But then, $n=ab$ must also be a product of primes. This contradiction proves the lemma.

Sketch of proof of Uniqueness:

Note:

This proof follows an informal discussion given in class. It is inadequate for these notes.

---

The GCD and LCM can be computed in terms of the multiplicities.

Hard exercise.

Let $\{a_1,\dots ,a_n\}\ne \{0\}$. Then,

$$\gcd (a_1,\dots ,a_n)=\prod _{p\text{ prime}}{p}^{\min \{{\mathrm{mult}}_p(a_i):0<i\le n\}};$$

and

$$\mathrm{lcm}(a_1,\dots ,a_n)=\prod _{p\text{ prime}}{p}^{\max \{{\mathrm{mult}}_p(a_i):0<i\le n\}}.$$

Exercise.

Use the above (even if you did not solve it) to show that for any integers not both zero $a$ and $b$,

$$\gcd (a,b)\mathrm{lcm}(a,b)=ab.$$