7

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.

John A
  • 71
  • 8
    1 is not a prime – AgentS Sep 17 '14 at 06:02
  • Isn't this basically by definition? Either, a number is a prime number, then it is divisible by itself, or it is not a prime number, which means that it is divisible by a prime factor? – Thomas Sep 17 '14 at 06:07
  • What axioms can you assume? Your method as you've stated it doesn't work (partially because 1 isn't prime, but also because the prime factors of $n$ don't really relate to the prime factors of $n+1$, so induction would be silly). – Zubin Mukerjee Sep 17 '14 at 06:08
  • @Thomas By definition, if a number $n > 1 $ is not prime then it is has a positive divisor other than $1$ and itself. Specifically there exists an integer $ 1 < a < n $ such that $ a \mid n $. It is not part of the definition that a composite number, a non prime integer $n>1 $, is divisible by a prime factor. See here. – john Oct 29 '20 at 09:12
  • We might as well prove the stronger statement, every integer $ n > 1 $ can be written as a product of primes. Then it immediately follows every integer $ n > 1 $ has at least one prime divisor. The proof method is the same as proofs below, by strong induction. – john Oct 29 '20 at 11:10

6 Answers6

27

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$.

André Nicolas
  • 507,029
  • 2
    nice and elegant +1 – Frank Sep 17 '14 at 07:07
  • Could one use this result to prove that every integer $n >1 $ can be factored into primes completely, and that this factorization is unique up to order. – john Jun 10 '18 at 10:26
  • Proof: Given $ n > 1 $ if $n $ is prime we are done, $n$ is factored into primes. If $n$ is not prime, then $ n = p_1 \times k_1 $ with $ 1 < p_1<n $ and $1 < k_1 < n $. We then ask the same question about $k_1$. If $k_1$ is prime, we are done. If $k_1$ is not prime, then $k_1 = p_2 \times k_2$ with $1 < p_2 < k_1$ and $1 < k_2 < k_1$. So far we have $ n = p_1 \times p_2 \times k_2 $. Ask the same question about $k_2$.This process must terminate eventually, otherwise we get an infinite list of decreasing positive integers $ n > k_1 > k_2 >... $ which is impossible. – john Jun 10 '18 at 11:23
  • @André Nicolas "If $n$ is not prime, by definition there exist integers a and b, with $2\le a<n$ and $2\le b<n$, such that $ab=n$." How do you get this from the definition that $n$ is not prime, i.e. that $n$ has a factor other than $1$ and itself. – john Dec 03 '19 at 12:39
2

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

john
  • 860
Sylvain Biehler
  • 478
2

If $n \ge 2$ is prime, then we're done, since $n$ is our desired prime factor of $n$. Otherwise, if $n \ge 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.

john
  • 860
Adriano
  • 41,576
1

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.

Sheheryar Zaidi
  • 2,714
0

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.

Frank
  • 2,348
0

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.

selva kumar
  • 125
  • I didn't downvote, but the problem was not in $i>1$ versus $i\ge1$: you're using the factorization of $n$ into primes, which is much stronger than the property to be proved. – egreg Oct 06 '15 at 14:40