0
$\begingroup$

Let m and n be relatively prime integers, and suppose that N is an integer for which m ∣ N and n ∣ N. Prove that mn ∣ N.

What I tried to do was use the mod function to divide the two numbers but I got stuck at the idea of "relatively prime integers". How would I deal with prime integers using the mod functions. Or would I use something like the Chinese remainder theorem?

Any help would be highly appreciated!

$\endgroup$
1
  • $\begingroup$ Think about the prime factorization of $m$ and $n$ and what being relatively prime means. $\endgroup$
    – ultrainstinct
    Commented Oct 21, 2017 at 20:08

1 Answer 1

Reset to default
2
$\begingroup$

Rename: $m\to a$, $n\to b$ and $N\to n$

Proof: Since $a|n$ we can write $n=ak$. Now since $b|ak$ we have, by Euclid lemma $b|k$, so $k=bl$. Thus $n=abl$ and so $ab|n$.

Vice versa. Say $ab|n$ and since $a|ab$ we have by transitivity $a|n$ and the same holds for $b$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .