Let $x,y$ be coprime integers. If $z$ is a multiple of $x$ and $y$ then $z$ is a multiple of $xy$.

Question

Let $x,y$ be coprime integers. I want to prove that if $z \in \mathbb Z$ is a multiple of $x$ and $y$ then $z$ is a multiple of $xy$.

I know that $\exists r,s,m_1, m_2 \in \mathbb Z$ s.t. $$z=m_1x=m_2y$$ $$xr+ys = 1$$. But this is as far as I've gotten. I'm not sure how to proceed from here.

Answer 1

Multiply the second equality you wrote by $z$ to get $xrz+ysz=z$. We also know that $z=m_1x=m_2y$. So that way we get $xr(m_2y)+ys(m_1x)=z$. Hence $z=xy(rm_2+sm_1)$.

Answer 2

Use the unique decomposition of integers into prime powers. If $x=\prod_i p_i^{a_i}$ and $y=\prod_j q_j^{b_j}$ and $x,y$ are coprime, the collections of primes $(p_i)$ and $(q_j)$ are disjoint. If $z$ is a multiple of both $x$ and $y$, then $z$ is a multiple of $xy=\prod_i p_i^{a_i}\prod_j q_j^{b_j}$

Answer 3

If $x$ has a prime factorization $p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}$ and $y$ has a prime factorization $p_{m+1}^{e_{m+1}} p_{m+2}^{e_{m+2}} \cdots p_n^{e_n}$, then none of the $p_i$ can be the same because $\gcd(x, y) = 1$. So what can you say about the factorization of $xy$, or of any multiple of both $x$ and $y$?