1
$\begingroup$

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 .

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – fleablood Jan 17 at 6:46
1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.