Fundamental Theorem of Arithmetic

Statement: Every integer greater than 1 can be uniquely expressed as a product of prime numbers, up to the order of the factors.

In formal terms, if $n$ is an integer greater than 1, then there exists a unique sequence of primes $p_1, p_2, \ldots, p_k$ and positive integers $e_1, e_2, \ldots, e_k$ such that: $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ where $p_1 < p_2 < \cdots < p_k$.

Proof:

The proof consists of two main parts: existence and uniqueness.

1. Existence:

We need to show that every integer greater than 1 can be factored into a product of primes.

• Base Case: Consider the smallest integer greater than 1, which is 2. Since 2 is a prime number, it can trivially be written as itself.

• Inductive Step: Assume that every integer from 2 up to some $n$ can be written as a product of primes. Now consider $n + 1$. There are two possibilities:

  • $n + 1$ is prime. In this case, $n + 1$ is already a product of primes, namely itself.
  • $n + 1$ is composite. Then $n + 1$ can be written as $ab$, where $a$ and $b$ are integers greater than 1 and less than $n + 1$. By the inductive hypothesis, both $a$ and $b$ can be written as a product of primes. Thus, $n + 1 = ab$ can also be written as a product of primes.

By mathematical induction, every integer greater than 1 can be expressed as a product of primes.

2. Uniqueness:

We need to show that this prime factorization is unique, apart from the order of the factors.

• Suppose an integer $n$ can be written as two different products of primes: $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} = q_1^{f_1} q_2^{f_2} \cdots q_m^{f_m}$ where $p_1, p_2, \ldots, p_k$ and $q_1, q_2, \ldots, q_m$ are prime numbers.

• Reduction to a Contradiction: Assume that the prime factorization is not unique. Without loss of generality, suppose $p_1 \neq q_1$. Since $p_1$ divides the left-hand side, it must also divide the right-hand side. But $q_1$ is prime, and since $p_1 \neq q_1$, $p_1$ does not divide $q_1$. Hence, $p_1$ must divide one of the other primes in the factorization on the right side.

• However, since primes have no divisors other than 1 and themselves, this means $p_1 = q_1$. This contradiction shows that our assumption was incorrect.

By using similar arguments for all primes, we conclude that the prime factorization must be unique.

Conclusion:

Thus, every integer greater than 1 has a unique prime factorization, up to the order of the factors. This completes the proof of the Fundamental Theorem of Arithmetic.

---

Would you like more details or have any questions about this topic?

Related Questions:

1. What is a prime number?
2. How can we find the prime factorization of a given integer?
3. What is the significance of the Fundamental Theorem of Arithmetic in number theory?
4. How does the Fundamental Theorem of Arithmetic apply to cryptography?
5. What is the difference between a prime and a composite number?
6. Can prime factorization be extended to complex numbers?
7. What are some applications of the Fundamental Theorem of Arithmetic in real-world problems?
8. How does the Fundamental Theorem of Arithmetic relate to the concept of greatest common divisors (GCD)?

Tip: To ensure accuracy when finding the prime factorization of a number, start dividing by the smallest prime and proceed to the next smallest only if the current prime no longer divides the number.