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