Hello all,

I'd like you to check my work. I have this nagging feeling that I am missing something, or worst yet, that my proof has some error I can't see.

Problem:

(b) For which pairs $\displaystyle m,n$ is $\displaystyle \beta : \mathbb{Z}_m \to \mathbb{Z}_n$ by $\displaystyle \beta ([a]_m) = [a]_n$ well defined?

Solution:

We claim that this is true for pairs $\displaystyle m,n$ iff $\displaystyle n \mid m$. Thus we need to show $\displaystyle (a \equiv b~(\mbox{mod }m) \implies a \equiv b~(\mbox{mod }n)) \Longleftrightarrow n \mid m$.

Proof:

($\displaystyle \Leftarrow$): Assume $\displaystyle n \mid m$. Then $\displaystyle m = tn$ for some $\displaystyle t \in \mathbb{Z}$. So, $\displaystyle a \equiv b~(\mbox{mod }m) \Longleftrightarrow b - a = mk \implies b - a = n(tk) \Longleftrightarrow a \equiv b~(\mbox{mod }n)$ for some $\displaystyle k \in \mathbb{Z}$.

($\displaystyle \Rightarrow$): For the converse, we use the contrapositive. Assume $\displaystyle n \nmid m$. Then by the Division Algorithm, $\displaystyle n = qm + r$, $\displaystyle 0 < r < m$, for unique $\displaystyle q,r \in \mathbb{Z}$. So $\displaystyle m = \frac {n - r}q$ (which is an integer by hypothesis). Thus, $\displaystyle a \equiv b~(\mbox {mod }m) \Longleftrightarrow b - a = mk$, for some $\displaystyle k \in \mathbb{Z}$, which implies $\displaystyle b - a = \left( \frac {n - r}q \right)k = \left( \frac nq \right)k - \left( \frac rq \right)k \ne nl$ for any $\displaystyle l \in \mathbb{Z}$. Thus, $\displaystyle n \nmid (b - a)$, which means $\displaystyle a \not \equiv b~(\mbox{mod }n)$.

QED

I don't like the second part of the proof too much, the part where i said not equal to nl mostly. Plus, this is just an observation of mine that I saw and proved, how do I know these are the only m and n for which this works?

Thanks all