Proving that $p_1p_2\mid n$ iff $p_1\mid n$ and $ p_2\mid n.$

Question

Let $p_1$, $p_2$ be distinct primes. Using the Fundamental Theorem of Arithmetic prove that a natural number $n$ is divisible by $p_1p_2$ if and only if $n$ is divisible by $p_1$ and $n$ is divisible by $p_2$.

Thus in symbolic terms I have to prove that

$n = (p_{1}p_{2})x_{1} \iff n = p_{1}x_{2} \wedge n = p_{2}x_{3}$ where $x_{1-3} \in \mathbb{N}$

I understand this in terms of a double implication,

$n =(p_{1}p_{2})x_{1} \Rightarrow n = p_{1}x_{2} \wedge n = p_{2}x_{3}$

and

$n =(p_{1}p_{2})x_{1} \Leftarrow n = p_{1}x_{2} \wedge n = p_{2}x_{3}$

If I prove both, I will have proved the statement.

The first implication is easy to prove, it doesn't even require me to use the FTA at all. I assume it holds and then decompose it in those two sub expressions using algebraic manipulation.

But I'm guessing for the second one I will need to the FTA somehow... and I haven't really gotten far. I could use a contrapositive, maybe.

How can I approach this? I know it is really simple, I feel awkward for asking this question but an insight would be useful.

Is there another more direct method?

Answer 1

$\Rightarrow$ part:
If $p_1 p_2 \mid n$ then $n = m p_1 p_2 = (m p_1) p_2 = (m p_2)p_1$. It is obvious then $p_1 \mid n$ and $p_2 \mid n$

$\Leftarrow$ part:
If $p_1 \mid n$ then $n = n_1p_1$. Now if $p_2 \mid n$ then $p_2 \mid n_1p_1$. But $p_2 \nmid p_1$ since $p_1$ and $p_2$ are different prime numbers, then $p_2 \mid n_1$ must hold, which means $n_1 = n_2 p_2$. Therefore $n = n_2 p_1 p_2$ or $p_1 p_2 \mid n$

Answer 2

Suppose $n$ is divisible by $p_1 p_2$ (i.e.,$p_1 p_2 | n)$ , then write $n=k(p_1^{\alpha}p_2^{\beta})$ for some integer $k$. Let $k(p_2^{\beta}) = q$, so write

$$n=(p_1^{\alpha})(k(p_2^{\beta}))=(p_1^{\alpha})q=(p_1)(p_1^{\alpha-1})q$$

and $(p_1^{\alpha-1})q$ is a positive integer ($\alpha > 0$ by hypothesis), so we conclude that $p_1$ divides $n$.

Now let $k(p_1^{\alpha}) = r$, and write

$$n=(kp_1^{\alpha})(p_2^{\beta})=(p_2^{\beta})r=(p_2)(p_2^{\beta-1})r$$

and $(p_2^{\beta-1})r$ is a positive integer ($\beta > 0$ by hypothesis), so we conclude that $p_2$ divides $n$ as well.

So $p_1$ divides $n$ and $p_2$ divides $n$.

Now assume $n$ is divisible by $p_1$ and $n$ is divisible by $p_2$ (i.e., $p_1 | n$ and $p_2 | n$), so there exist positive integers $s$ and $t$ such that $n=sp_1$ and $n=tp_2$. Now write the prime factorization of both $s$ and $t$:

$$s=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_r^{a_r}$$ and $$t=p_1^{b_1}p_2^{b_2}p_3^{b_3}...p_q^{b_q}$$

(note we aren't using the same factorization as we did from the first argument; I'm just running out of letters to use ;)

so write: $$n=(p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_r^{a_r})p_1$$ $$n=p_1^{a_1+1}p_2^{a_2}p_3^{a_3}...p_r^{a_r}$$ call the above line $(1)$ and $$n=(p_1^{b_1}p_2^{b_2}p_3^{b_3}...p_q^{b_q})p_2$$ $$n=(p_1^{b_1+1}p_2^{b_2}p_3^{b_3}...p_q^{b_q})$$ call the above line $(2)$

making note of the fact that, by hypothesis, $a_1, a_2, b_1, b_2$ are all greater than zero.

Rewrite $(1)$:

$$n=(p_1p_2)(p_1^{a_1}p_2^{a_2-1}p_3^{a_3}...p_r^{a_r})$$

rewrite $(2)$:

$$n=(p_1p_2)(p_1^{b_1}p_2^{b_2-1}p_3^{b_3}...p_q^{b_q})$$

and since $(p_1^{a_1}p_2^{a_2-1}p_3^{a_3}...p_r^{a_r})$ and $(p_1^{b_1}p_2^{b_2-1}p_3^{b_3}...p_q^{b_q})$ are integers, we conclude that $p_1p_2$ divides $n$.

Answer 3

Obviously, if $p_1p_2\mid n$, then $p_1\mid n$ and $p_2\mid n$. So assume that $p_1\mid n$ and $p_2\mid n$.

If $p_1$ and $p_2$ are distinct primes, then, using Bezout's Identity, there are $x,y\in\mathbb{Z}$ so that $$ xp_1+yp_2=1\tag{1} $$ Equation $(1)$ implies that $$ \begin{align} n &=nxp_1+nyp_2\\ &=\left(\frac{n}{p_2}x+\frac{n}{p_1}y\right)p_1p_2\tag{2} \end{align} $$ which is a multiple of $p_1p_2$ since $\frac{n}{p_1},\frac{n}{p_2}\in\mathbb{Z}$.

---

The preceding argument actually shows that if $\gcd(p_1,p_2)=1$, then $$ p_1p_2\mid n\iff p_1\mid n\text{ and }p_2\mid n\tag{3} $$