Proof that a natural number can be expressed as a product of prime numbers
- Get link
- X
- Other Apps
Hello everyone. Today we will prove that any natural number greater than \(1 \) can be expressed as a product of a prime number and number one or as a product of few prime numbers. We will use the method of mathematical induction as a proof method.
Theorem: Let \(n \) be a natural number greater than \(1 \). Then \(n \) can be expressed as the product of one prime number and number one or as the product of few prime numbers.
Proof:
Note that if \(n \) is a prime number, the statement is automatically proved because any number can be written as the product of that number and number one.
1. Base case (n = 2)
Since \(2 \) is a prime number the statement is automatically proved.
2. Induction hypothesis (n = m)
Suppose that \(\forall k \in \mathbb {N}, \quad 2 \le k \le m \), \(k \) can be expressed as the product of a prime number and number one or as a product of few prime numbers.
3. Inductive step (n = m + 1)
Using the assumption from the second step, we will prove that: \(\forall k \in \mathbb {N}, \quad 2 \le k \le m + 1 \), \( k \) can be expressed as the product of one prime number and number one or as the product of few prime numbers.
For all \(k \) less than \(m + 1 \) the truth of the statement automatically follows from the inductive hypothesis. Let us now consider the case when \(k = m + 1 \). If \(m + 1 \) is a prime number, the statement is automatically proved. Otherwise \(m + 1 \) is a composite number which can be expressed in the form \(m + 1 = pq \), where \(p \) and \(q \) are natural numbers such that \(2 \le p <m+1\) and \(2 \le q <m+1\) , i.e. \(2 \le p \le m\) and \(2 \le q \le m\) . According to the inductive hypothesis, both numbers \(p \) and \(q \) can be expressed as products of few primes or as products of one prime number and number one, therefore the same is true for the number \(m + 1 \).
\(\blacksquare \)
- Get link
- X
- Other Apps
Comments
Post a Comment