0
$\begingroup$

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:

  1. $a\mod m$ is relatively prime to $m$
  2. $a \mod n$ is relatively prime to $n$

3 Answers 3

1

$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$.

  • 0
    If you define $a\bmod m$ as the number $r$ where $a=mk+r$ with $k\in\mathbb Z$, 0\le r, then you have $a\bmod m=r=a-mk$, hence my $k$ is your $-k$, but of course that doesn't matter.2012-09-30
0

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$.

0

$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.