A composite number has at least three factors [Proof]

A composite number has at least one prime factor; hence it has at least three factors. If n is a composite number then n is always divisible at least by three distinct numbers.

A composite number is divisible at least by one prime

Question: Prove that a composite number has at least one prime divisor.

Solution:

Let n be a composite number. Thus, by definition, it has a positive divisor other than 1 and n. Let S be the set of these positive divisors of n (which are different from 1 and n).

Clearly, S is non-empty.

By the well-ordering principle of natural numbers, S has a least element, say d.

Note 1< d < n.

Claim: d is a prime number.

If d is not a prime, then there is another number d’ that divides d.

So 1< d’ < d < n.

As d’ divides d and d divides n, we have that d’ divides n ⇒ d’ ∈ S.

Thus we arrive at a contradiction to the fact that d is the least element of S. Thus, d is a prime number and the result follows.

Therefore, a composite number has at least one prime divisor.

Read Also: If 2ⁿ-1 is a prime, then n is a prime

A composite number is divisible by at least three numbers

Question: Prove that a composite number has at least three factors.

Solution:

Let n be a composite number.

Then n is divisible by a prime number p by the above theorem.

Also, n is divisible by 1 and n.

As n≠p, the number n is divisible by three numbers 1, p, and n. So we have proved the following:

A composite number has at least three factors.

Read Also: Is 2 a prime number?

FAQs