Let $n, m ∈ Z$ (integer set) , $(n, m) = 1$. Suppose that $d$ is a positive divisor of $mn$. Show that there exist positive integers $d_1$ and $d_2$ such that $d =$ $d_1$$d_2$ where $d_2$ divides $n$ and $d_2$ divides $m$.

Could someone explain how to approach this proof? I would greatly appreciate it!

My Attempt:

Since it is assumed that d is a positive divisor of $mn$ we get $d_1$ and $d_2$, but I don't understand how $d_2$ divides $n$ and $m$, this is where I get confused.

  • 1
    $\begingroup$ This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level. $\endgroup$ – user296602 Apr 28 '16 at 2:57
  • $\begingroup$ I added my honest attempt to it. $\endgroup$ – Earthbound27 Apr 28 '16 at 4:10
  • $\begingroup$ What do you mean by "we get $d_1$ and $d_2$"? $\endgroup$ – Mees de Vries Apr 28 '16 at 7:22

For every prime power $p^a$ that divides $d$, we have $p^a \mid mn$. If $p \mid m$, then $p \nmid n$, and vice versa, because $(m,n) = 1$; so all the $p$s must be in only one of $m$ and $n$. We get that $p^a$ divides either $m$ or $n$. Since we're doing this for every $p^a$ that divides $d$, we will eventually assign each factor to either $m$ or $n$, and we will get the $d_1$ and $d_2$ required.

  • $\begingroup$ This is not true. 6 divides both 2 and 3 (and (2,3) = 1), yet obviously 6 divides $2 \times 3$. $\endgroup$ – Mees de Vries Apr 28 '16 at 7:21
  • $\begingroup$ @MeesdeVries Sorry, fixed it. $\endgroup$ – shardulc Apr 28 '16 at 9:05
  • $\begingroup$ This is now the proof I also had in mind. I wonder if there's a more direct way, using the definition/properties of the greatest common divisor directly, rather than by using prime factorizations. $\endgroup$ – Mees de Vries Apr 28 '16 at 11:49

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.