Understandng euclids theorem

Question

Reading this Wikipedia article, it states "If q is not prime, then some prime factor p divides q"

Why does some prime factor divide q? Does mean that for any number there is some prime factor p that divides q?

Answer 1

"Why does some prime factor divide $q$?"

Because if it didn't, then $q$ would itself be prime.

(This of course assumes $q\ne1$. For Euclid, that was not a problem since Euclid didn't even consider $1$ to be a number. The question "Why is $1$ not considered prime?" gets answers here that seem to me too complicated. I'd rather answer it something like this: Suppose we are factoring a number: $$ \begin{array}{cccccccccccl} & & & & & & 60 \\ & & & & & \swarrow & & \searrow \\ & & & & 15 & & & & 4 \\ & & & \swarrow & \downarrow & & & & \downarrow & \searrow \\ & & 3 & & 5 & & & & 2 & & 2 & \text{Stop here.} \\ & \swarrow & \downarrow \\ 1 & & 3 & \leftarrow& \leftarrow& \leftarrow& \leftarrow& \leftarrow& \leftarrow& \leftarrow& \leftarrow & \text{Don't do this.} \end{array} $$ You can keep factoring out $1$s forever and it gives you no information about the factorization of the number. Therefore the number $1$ belongs in a different role from those of composite numbers, like $60$, which are the ones to be factored, and prime numbers like $2$, $3$, and $5$, which is where the process of factoring ends.

Answer 2

If $q$ is not prime, then it is composite, since $q$ is not $1$.

Answer 3

Yes. Every number can be represented as a product of primes, and so every number is divisible by some prime.

Proof: If the number is itself prime, we're done (it's divisible by itself). Otherwise, write it as a product $ab$. Now do the same for $a$ and $b$ - that is, if either is prime we're done, and if not, break each one into a product of smaller numbers. Since the numbers are getting smaller and smaller, at some point we'll have to hit a prime number, otherwise we'd keep going forever, which is impossible (you can't make a number smaller forever, you'll hit $1$ eventually).

Answer 4

Here's a method for proving thr statement. By definition, if q is not prime, then q has some divisors, other than 1 and q itself. Let d be a divisor of q.

We now have two cases:

1) if d is prime, then we've found a prime number that divides q, and we're done.
2) if d is not prime, then it has some divisors. Let d' a divisor of d, different of 1 and d itself. I assume you know that if d divides q, and d' divides d, then d' also divides q. So if our new d' is prime, then we're done. Otherwise, we apply the same reasoning for a divisor of d', different of 1 and d' itself, which of course, will divide q.

Eventually, we will obtain a prime dvisor.

I know this isn't a very rigorous proof, but it helps you get an ideea of why the statement is indeed correct.

Answer 5

Hint $\ $ The least factor $>1\,$ of $\ n>1\,$ must be prime.

By $\,n>1$ it 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 $\ $ We can interpret the proof constructively as follows. Suppose we have an algorithm $\,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 naturals (see below), contra $\,\Bbb N\,$ is well-ordered

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