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


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

  • $\begingroup$ hint: consider the prime factorization of $n$ $\endgroup$ – russoo Jan 21 '15 at 18:33

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

  • $\begingroup$ Why the downvote? This answer does use the fact that a prime is irreducible, but that is pretty simple to show (that an irreducible is prime can be proven using Bezout, but that is not needed here). Otherwise, the answer looks good. $\endgroup$ – robjohn Jan 22 '15 at 21:30

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

  • $\begingroup$ Bezout's Identity holds in any PID (e.g. any Euclidean domain), but I believe there are integral domains in which it fails. $\endgroup$ – robjohn Jan 22 '15 at 2:14
  • $\begingroup$ You are right. I was just thinking that if $(p,q)=1$ ( that is, a combination of them equals $1$), and $p \mid n$, $q \mid n$ then $pq \mid n$, just the standard result: $I\cap J = I\cdot J\ $ if $I + J=1$. $\endgroup$ – Orest Bucicovschi Jan 22 '15 at 5:17
  • $\begingroup$ I am trying to prove this only using the natural numbers, I will try an approach similar to yours... This proof is very well implemented though. $\endgroup$ – JOX Jan 22 '15 at 20:51
  • $\begingroup$ @DanielOrtizCosta: It would be nice to mention this in the question. Bezout is a pretty basic result for integers, but it does require $x,y\in\mathbb{Z}$. $\endgroup$ – robjohn Jan 22 '15 at 21:29

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


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


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)$:


rewrite $(2)$:


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

  • $\begingroup$ Thank you very much to the downvoter who decided not to comment on why my answer sucks. $\endgroup$ – Sultan of Swing Jan 22 '15 at 0:01
  • $\begingroup$ I'm no number theorist, but this looks okay. Have my upvote, and maybe someone will explain it to both of us. $\endgroup$ – Alfred Yerger Jan 22 '15 at 2:29
  • 1
    $\begingroup$ It concerns me when people do that because it doesn't contribute to the site at all; I'd like to hear feedback from people to see if I've done things correctly. I realize my answer might be a lot longer than the other answers, but if it is incorrect or flawed, I'd like to hear about it so I could edit it. I wouldn't want to leave an incorrect answer. $\endgroup$ – Sultan of Swing Jan 22 '15 at 10:44

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.