Properties of Euler's $\phi()$ function

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

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

-
How does $a \mod m = a + km$? I thought $a \mod m = r$ where the division algorithm says: $a = mk + r$. I guess we could subtract $mk$ to the other side and get: $r = a -mk$ and then the sign does not really matter? – CodeKingPlusPlus Sep 30 '12 at 15:07
I really like your proof if you could explain the $a \mod m = a +km$ – CodeKingPlusPlus Sep 30 '12 at 15:11
If you define $a\bmod m$ as the number $r$ where $a=mk+r$ with $k\in\mathbb Z$, $0\le r<m$, then you have $a\bmod m=r=a-mk$, hence my $k$ is your $-k$, but of course that doesn't matter. – Hagen von Eitzen Sep 30 '12 at 16:20

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.

-