# if a composite number is divisible by a prime number , the prime number must be present in the prime factrisation of that composite number?

I think this should be true since prime factorisation it self means stating all the primes which divide the composite number . Please correct me if I am wrong .

• Well, what is a prime factorization anyway? And do you know if numbers have to have prime factorizations? Can a number ever have two different prime factorizations. What does it mean to say a prime divides a number and what does it mean for a prime to be present in a prime factorization? Is it even meaningful to imagine a prime number dividing an not being in the factorization? If so what is a factorization? – fleablood Jan 17 at 6:46

Here is a proof without the unicity part of the fundamental theorem of arithmetic (the existence is supposed known because of the statement).

Let $$a$$ an integer and $$a=\prod_{i=1}^n p_i^{\alpha_i}$$ a prime factorization of $$a$$.

Suppose $$p$$ is prime and $$p|a$$ where $$p \ne p_i$$ for all $$i \in \{1,\dots,n\}$$. Then $$p$$ divises $$p_1\left(p_1^{\alpha_1-1}\prod_{i=1}^n p_i^{\alpha_i}\right)$$. Since $$p$$ and $$p_1$$ are different primes, by Euclid's lemma, $$p$$ also divises $$p_1^{\alpha_1-1}\prod_{i=1}^n p_i^{\alpha_i}$$. Repeat this until there is no more $$p_1$$ (we substract a power of $$p_1$$ every time) and do the same for $$p_2$$. Applying the same reasoning again and again will yields that $$p$$ divises $$1$$, which is not possible for a prime number. Hence a contradiction and $$p$$ is in the prime factorization of $$a$$.

Note : I just realized that proof is just a slightly modified version of the one of unicity part in fundamental theorem of arithmetic.

You are correct. One way to see this is to let the composite number be $$c$$ and the prime number be $$p$$. Then $$p \mid c$$ means that there exists an integer $$k$$ such that $$c = pk$$. Now, since $$c$$ is composite, then $$k$$ can't be $$1$$, with it actually being $$\gt 1$$, so it must be a prime or a composite number. By the Fundamental theorem of arithmetic, $$k$$ has a unique, up to order, prime factorization, e.g.,

$$k = \prod_{i=1}^{j}p_i^{r_i} \tag{1}\label{eq1A}$$

Thus, $$c$$ would be

$$c = p\left(\prod_{i=1}^{j}p_i^{r_i}\right) \tag{2}\label{eq2A}$$

This is a prime factorization of $$c$$, but as $$c$$ itself has a unique (up to order) prime factorization, this shows that $$p$$ must be in any prime factorization of $$c$$.

• Good one. I had a much more boring way of doing it with this theorem. – nicomezi Jan 17 at 6:52