Why are all non-prime numbers divisible by a prime number?

Question

In Euclid's infinite prime numbers proof, the logic is as follows:

Assume a set $S$ of all prime numbers in existence is finite (there are a finite amount of primes)

Then there must be a greatest prime $p$

$$n = (2 \cdot 3 \cdot 5\cdots p) + 1$$

$n > p$, and under the proof's assumption, $n$ cannot be prime.*

This is where the logic confuses me. Why is it that given that the if a number is not prime, then it is automatically divisible by a prime. I can't think of an example to contradict, but that's not proof that there exists no number that is not prime and non divisible by primes.

Answer 1

One can prove this for all integers greater than $1$ by induction: we know that $2$ is a prime. Now for ou inductive step assume that for all $i<n$, $i$ is either prime or divisible by a prime. Case 1: $n$ is prime; we're done. Case 2: $n$ is composite, so $ab = n$ for $a, b < n$. So each of those is divisible by a prime. We're done.

Essentially the same argument shows that all integers greater than $1$ can be written as a product of primes.

Answer 2

Lemma $\ $ The least factor $>1\,$ of $\ n>1\,$ is prime.

Proof $\ $$\,n>1$ has at least one factor $> 1,\,$ viz. $\,n.\,$ Let $\,p\,$ be its least factor $>1.\,$ Then $\,p\,$ is prime (else $\,p\,$ has a proper divisor $\,1 < d < p\,$ and $\,d\mid p\mid n\,\Rightarrow\,d\mid n,\,$ contra minimality of $\,p).$

Remark $\ $ More generally it proves prime the least element of any set $\,S\,$ of integers $> 1$ that is closed under divisors $> 1,\,$ i.e. $ $ if $\,S\,$ contains $\,n\,$ then $\,S\,$ contains every divisor $> 1$ of $\,n.\,$ Above the set $\,S\,$ is the set of factors $>1$ of $\,n.$

We can interpret the proof constructively as follows. Suppose we have an algorithm $\,n\mapsto f(n)\,$ that yields a proper factor of every nonprime $\,n > 1.\,$ Then iterating the algorithm must eventually terminate at a prime factor of $\,n,\,$ for otherwise it would yield an infinite strictly descending sequence of proper factors (see below), contra $\,\Bbb N\,$ is well-ordered

$$ n > f(n) > f(f(n)) > f(f(f(n))) >\, \cdots$$

Answer 3

You are in good company in your error. Some great mathematicians, including Dirichlet, have made the same mistake: falsely reporting that Euclid's proof was by contradiction.

Euclid's proof says that if you take any finite set of prime numbers (for example, $2$, $11$, and $19$) and multiply them and then add $1$, the resulting number is not divisible by any of the primes in the finite set you started with (thus $(2\cdot11\cdot19)+1$ is not divisible by $2$, $11$, or $19$ because its remainder on division by any of those numbers is $1$.

Therefore, the finite set you started with can be extended to a larger finite set: the prime factors of (in this example) $(2\cdot11\cdot19)+1$.)

The reason the number $(2\cdot11\cdot19)+1$ must be divisible by some prime is that if it is not divisible by any prime other than itself, then it is prime and it is of course divisible by itself.

PS: Some people commenting below are unhappy with my last paragraph above, so I'll add this: Let's do a proof by contradiction on this one: Consider the smallest number $N$ that is not divisible by any prime. It cannot be divisble by anything smaller than itself except $1$, since that not-necessarily-prime factor, being smaller than the smallest counterexample, would be divisible by some prime, and then $N$ would be divisible by that prime. So not being divisible by anything except itself and $1$, $N$ would be prime, and hence divisible by some prime, namely itself.

Answer 4

Assume your "non-prime number" is not divisible by a prime. Because of the unique factorization theorem, all numbers can be written as a product of primes. This means your "non-prime number" can be written as a product of primes. But it can't be written as a product of primes by definition, so it must be divisible by only itself - making your "non-prime number" a prime number.

Answer 5

The answer by @Don Larynx gives me an idea without further looking at the unique factorization theorem.

Why a non-prime is always divisible by a prime? When a number P is divisible by n1 then n1 is a factor of P. For example P = n1 x n2 x n3. So P is divisible by either n1, n2, n3 (the quotient is a positive whole number) and these 3 numbers are factors of P. Lets say we want to factor P, we can start with 2 factors, P = n1 x n2. If both n1 and n2 are primes then we have answered the question. If any of the factor is non-prime, then we can continue to break down that non-prime factor until eventually all the factors is a prime (divisible by itself and 1). For example:

1.) 200 = 10 x 20
2.) 200 = (5 x 2) x (5 x 4)
3.) 200 = (5 x 2) x (5 x (2 x 2))
200 = 5 x 2 x 5 x 2 x 2

1.) 200 = 100 x 2
2.) 200 = (25 x 4) x 2
3.) 200 = (5 x 5) x (2 x 2)) x 2
200 = 5 x 5 x 2 x 2 x 2

So we can say a prime can only be a product of itself and 1. A non-prime can eventually be reduced to a product of 2 or more prime numbers. Therefore a non-prime is always divisible by a prime.

Answer 6

Let $n$ be a composite (i.e., non-prime) integer.

According to the Fundamental Theorem of Arithmetic, $n$ has a unique prime factorization:

$$ n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{k}^{\alpha_{k}}$$

where the $p_{i}$ are distinct prime numbers and the $\alpha_{i}$ are positive integers.

Choose any of the $p_{i}$, say $p_{j}$.

Now, $p_{j} | p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{k}^{\alpha_{k}}$, and so,

$$p_{j}|n.$$

Therefore, $n$ is divisible by a prime number. (Actually $k$ of them in this case.)