Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic (FTA), also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than $1$ either is prime itself or is the product of a unique combination of prime numbers.

For every integer $n\geq2$, it can be expressed as a product of prime numbers:

$$n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_i^{\alpha_i}.$$

The following proof shows that every integer greater than $1$ is prime itself or is the product of prime numbers. It is adapted from the Strong Induction wiki:

Base case: This is clearly true for $n=2$.

Inductive step: Suppose the statement is true for $n=2,3,4,\dots, k$.

If $(k+1)$ is prime, then we are done. Otherwise, $(k+1)$ has a smallest prime factor, which we denote by $p$. Let $k+1=p\times N$. Since $N<k$, by our inductive hypothesis, $N$ can be written as the product of prime numbers. That means $k+1=p \times N$ can also be written as a product of primes. We're done! $_\square$

The following proof shows that there is only one way to express an integer with the product of an unordered set of primes.

The proof uses Euclid's lemma: If a prime $p$ divides the product of two positive integers $a$ and $b$, then $p$ divides $a$ or $p$ divides $b$ (or both).

Assume that integer $n$ is the product of prime numbers in two different ways: $$\begin{aligned} n &= p_1p_2\dots p_i \\ &= q_1q_2\dots q_j. \end{aligned}$$ For simplicity, we let the arrangements of prime be in ascending order.

By Euclid's lemma, since $q_1, q_2, \dots, q_j$ are coprime integers (in fact, they are all primes), $p_1$ can and must divide only one of the primes. Note that $q_1$ is the smallest prime, then we have $p_1=q_1$. By the same method, we reach that all $p_k=q_k$ and thus $i=j$. Then we conclude that the combination of primes are the same. $_\square$

Finding the number of divisors:

If $n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_i^{\alpha_i}$, then $n$ has $d(n)=(\alpha_1+1)(\alpha_2+1)\cdots (\alpha_i+1)$ positive divisors.

Finding the greatest common divisor of integer $a$ and $b$:

If

$$a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\qquad \text{ and } \qquad b=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k},$$

then

$$\gcd(a,b) = p_1 ^{\min(\alpha_1, \beta_1)} p_2 ^{\min(\alpha_2, \beta_2)} \ldots p_k ^{\min(\alpha_k, \beta_k)}.$$

Finding the lowest common multiple of integer $a$ and $b$:

If $$a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\qquad \text{ and } \qquad b=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k},$$

then

$$\mbox{lcm}(a,b) = p_1 ^{\max(\alpha_1, \beta_1)} p_2 ^{\max(\alpha_2, \beta_2)} \ldots p_k ^{\max(\alpha_k, \beta_k)} .$$

Given the polynomial $$f(x)=x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots + a_{n-1}x+a_n$$ with integer coefficients $a_1,a_2,a_3,\ldots, a_n$ and given that there exist four distinct integers $a,b,c$ and $d$ such that $$f(a)=f(b)=f(c)=f(d)=5,$$ show that there is no integer $k$ for which $f(k)=8$.

---

Let $g(x)=f(x)-5$. Then we must have $$g(x)=k(x-a)(x-b)(x-c)(x-d)h(x)$$ for some $h(x) \in \mathbb{Z}[x]$. Let $k$ be such that $f(k)=8$, Then $g(k)=3$ and we get $$3=k(x-a)(x-b)(x-c)(x-d)h(x).$$ By the fundamental theorem of arithmetic, we can express 3 as a product of at most three different integers $(-1,-3,1)$. Since, $(x-a),(x-b),(x-c)$ and $(x-d)$ are all distinct, this is an obvious contradiction. $_\square$