# Proof that every number has at least one prime factor

Prove that for $n \geq 2$, n has at least one prime factor.

I’m trying to use induction. For n = 2, 2 = 1 x 2. For n > 2, n = n x 1, where 1 is a prime factor. Is this sufficient to prove the result? I feel like I may be mistaken here.

#### Solutions Collecting From Web of "Proof that every number has at least one prime factor"

For a formal proof, we use strong induction. Suppose that for all integers $k$, with $2\le k\lt n$, the number $k$ has at least one prime factor. We show that $n$ has at least one prime factor.

If $n$ is prime, there is nothing to prove. If $n$ is not prime, by definition there exist integers $a$ and $b$, with $2\le a\lt n$ and $2\le b\lt n$, such that $ab=n$.

By the induction assumption, $a$ has a prime factor $p$. But then $p$ is a prime factor of $n$.

Inductive case: Assume $n$ has prime factors: It is either a prime, then it’s got a prime factor (itself), and then $n+1$ is even and has 2 as a prime factor. If $n$ isn’t prime, then the FTA says it has a unique prime factorization and $n+1$ is either prime or FTA says it has a prime factorization.

Induction seems a bit useless here.

You can use a proof by contradiction. If $n>1$ has no prime divisor, you can build an inifinite series of decreasing numbers.

let $n \in \mathbb{N}, n \geq 2$ and let’s consider cases:

$n\mbox{ is prime}$: done.

$n\mbox{ is not prime} \iff n \mbox{ is mixed} \implies n=\prod_{i=1}^j P_i^{q_i}$, where $P_k \mbox { is prime}$, $q_k \mbox { is the exponent}$ $\implies$ $n$ has prime factors: done.

If $n$ is prime, then we’re done, since $n$ is our desired prime factor of $n$. Otherwise, if $n > 2$ is not prime, then $n = ab$ for some $a,b \in \mathbb N$, where $1 < a \leq b < n$. But then since $a \geq 2$, it follows by the induction hypothesis that $a$ has at least one prime factor, say $p$, so that $a = pk$ for some $k \in \mathbb Z$. But then since $n = (pk)b = p\underbrace{(kb)}_{\in ~ \mathbb Z}$, we have that $p$ is also a prime factor of $n$, as desired.

Let n be a number greater than 2. It can be proved in following way.

Case 1:If n is a prime number and $n \geq 2$ , then the number n can be factorized like $n= 1 * n$, where n is the only prime factor.

Case 2:If n is not a prime number and $n \geq 2$, then the number n may be factorized in the following manner
$n = p_1^m * p_2^r *…p_i^a$ where $p_i$ denotes the prime factor and i denotes the number of prime numbers involved in its factorization such that $i > 1$.

If $i=1$ , it falls in the case 1.

Hence proved.