Understandng euclids theorem 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?
 A: 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.
A: "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.
A: If $q$ is not prime, then it is composite, since $q$ is not $1$.
A: 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).
A: 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$$
