This is part of the $\phi(mn) = \phi(m)\cdot \phi(n)$ theorem.
For some integer $a$ relatively prime to $m\cdot n$ how do I know the following:
- $a\mod m$ is relatively prime to $m$
- $a \mod n$ is relatively prime to $n$
This is part of the $\phi(mn) = \phi(m)\cdot \phi(n)$ theorem.
For some integer $a$ relatively prime to $m\cdot n$ how do I know the following:
$a\bmod m=a+km$ for some $k\in\mathbb Z$. If $d$ divides both $a\bmod m$ and $m$, say $a+km=d b$ and $m=d c$, then $a=db-km=d(b-kc)$, i.e. $d$ is also a common divisor of $a$ and $m$.
Do it in stages: prove that if $a$ is prime to $mn$ then it's prime to $m$, and prove that if $a$ is prime to $m$ then $a$ reduced modulo $m$ is relatively prime to $m$.
$a$ is relatively prime to $b$ if and only if $(a \bmod b)$ is relatively prime to $b$.
Moreover, $d|a,b \iff d|(a-kb),b$ for any $k\in\mathbb Z$. Try to prove this one.