Let $a,b \in \mathbb{Z}, m \in \mathbb{N}, d= \gcd(a,m)$ If $d>1, a=a_1d, m=m_1d$ Why $\gcd(a_1,m_1)=1$?

Question

Let $a,b \in \mathbb{Z}, m \in \mathbb{N}, d= \gcd(a,m)$ If $a=a_1d, m=m_1d, d>1$ Why $\gcd(a_1,m_1)=1$ ?

Answer 1

Because if it was $d_1\neq 1$, you would have $a_1=d_1a_2, m_1=d_1m_2$, $a=a_1d=a_2d_1d, m=m_1d=d_1dm_2$ so $d_1d$ divides $a$ and $m$ contradiction.

Answer 2

An alternate definition of $\gcd$:

The $\gcd$ of $x$ and $y$ is a number $z$ such that:

1. $z \mid x$ and $z \mid y$; and:
2. For every $z'$ satisfying $z' \mid x$ and $z' \mid y$, we have $z' \mid z$. (Universal Property)

---

Let $a,b \in \Bbb Z$ and $m \in \Bbb N$ such that $m=\gcd(a,b)$.

Then, $m \mid a$ and $m \mid b$, i.e. there is $a'$ such that $a = a' m$ and $b'$ such that $b = b' m$.

Now, I claim that $\gcd(a',b')=1$:

1. Obviously, $1 \mid a'$ and $1 \mid b'$.
2. If there is another $z'$ with $z' \mid a'$ and $z' \mid b'$, then there is $a''$ such that $a' = z' a''$ and $b''$ such that $b' = z' b''$, then $a = a'' z' m$ and $b = b'' z' m$, so $z'm \mid a$ and $z'm \mid b$. Therefore, by the universal property of $\gcd$ applied to $a$ and $b$, we have $z'm \mid m$, so $z' \mid 1$.