0

I want show by well founded induction, that every natural number > 1 is divisible by a prime number.

Let $(N, <)$ a set and $P \subset N$.

$P(x)$ is the property that $x$ is divisible by a prime and $x$ is a natural number $>1$.

Assume $P(y)$ is true for all predecessors of $x$.

To show that $P(x)$ is also true.

Case 1: $x$ is a prime number -> $x$ is divisible by itself -> $P(x)$ is true.

Case 2: $x$ is not a prime...how can I show that case 2 is also true?

Max Mustermann
  • 1
  • 2
    Does this answer your question? Proof that every number has at least one prime factor – José Carlos Santos Nov 16 '21 at 14:10
  • I suggest this proof : Let $N>1$ be an integer and define $M$ as the set of the divisors of $N$ greater than $1$. Because of $N\mid N$ , this set is non-empty. Now show that the smallest element must be a prime by a simple contradiction proof. – Peter Nov 16 '21 at 14:11
  • 1
    @Peter A more induction-y proof would be the following. Suppose the claim is true for $2,\ldots,N-1$. If any of $2,\ldots,N-1$ are divisors of $N$, then whatever prime divides that number also divides $N$, finishing the proof. If none of the numbers are divisors of $N$, then $N$ is prime by definition. Back in uni, I used to get points docked for using WOP instead of induction, despite the equivalence. – Rushabh Mehta Nov 16 '21 at 14:19

1 Answers1

1

It is true for n=2, since 2|2. Now suppose it is true for all n from 2 to k−1. We must show that k is divisible by a prime. If k is prime, then k is divisible by the prime k, and we are done. If kis not prime, it must be composite. Thus k=ab, where a and b are integers less than k and greater than 1. By the inductive hypothesis, a is divisible by a prime p, hence k is also divisible by p.

John Doe
  • 11