If we make a table such that each column contains numbers modulo $m$ and each row containing numbers modulo $n$. Let us denote the element $a_{ij}=x$ and $a_{i'j'}=y$ Where $0\leq i,i' This is essentially how I translate a program i wrote to generate those tables and it works fine. (loop over every number, then decide its indices). I am now trying to show that no two numbers in the table are same (which is so if $m,n$ are coprime) Start by supposing that $x=y$ then,
$$i\equiv i' \quad(mod \;m)$$
$$j\equiv j' \quad(mod \;n)$$ But because $0\leq i,i' However, there has to be a mistake here as I never took into account $m$ and $n$ to be coprime.
Where is the mistake in this reasoning?
2 Answers
The problem when $m$ and $n$ are not coprime is that some positions in the table cannot be filled; for instance, if $m=6$ and $n=10$, $a_{01}$ is undefined. Your argument correctly shows that the entries that can be defined must all be distinct.
-
0But the problem is, for $m=6$ and $n=10$ we have $\;a_{00}=0\mbox{ and }30$. So for an entry, the above "proof" of mine can also be reversed to show that if $i=i'$ and $j=j'$ then $x=y$, which is clearly not true as we can have two different numbers in a position. – 2011-07-16
-
0@kuch nani: You are confusing the issue of whether, *given one specific way of filling in the table*, two entries can be the same, vs. *whether there is more than one way of filling in the table*. It is true that there is more than one way of filling in the table; but Brian's point is that, given two entries in different locations, they cannot be equal. – 2011-07-16
-
0@Kuch: Why do you think that it reverses? $x=y$ implies that $i\equiv i'\pmod m$ and $j\equiv j'\pmod n$, but the reverse implication is false. – 2011-07-16
It's an immediate consequence of uniqueness of solutions in CRT (Chinese Remainder Theorem). The proof is quite easy. $\:$ If $\rm\:gcd(m,n)\ =\ 1\:$ then $\rm\ x\ mod\ mn\ \to\ (x\ mod\ m,\ x\ mod\ n)\ $ is $1$ to $1\:.\ $ For if $\rm\ x,\:y\ $ map to the same value then $\rm\: x = y\ (mod\ m)\: $ so $\rm\ m\ |\ x-y\:,\:$ i.e. $\rm\:m\:$ divides $\rm\:x-y\:.\:$ Similarly $\rm\:n\ |\ x-y\:.\:$ Hence $\rm\: lcm(m,n)\ |\ x-y\:.\:$ But $\rm\:gcd(m,n) = 1\ \iff\ lcm(m,n) = mn\:.\:$ Thus $\rm\ mn = lcm(m,n)\ |\ x-y\:,\:$ hence $\rm\ x = y\ (mod\ mn)\:.\:$ Therefore, indeed, the map is $1$ to $1$.
Conversely, if $\rm\ lcm(m,n) < mn\ $ then $\rm\:x\:$ and $\rm\ x + lcm(m,n)\ $ are not congruent $\rm\:(mod\ mn)\:.\:$ However, both map to the same value $\rm\ (x\ mod\ m,\ x\ mod\ n)\:,\ $ since both $\rm\: m\:$ and $\rm\:n\ |\ lcm(m,n)\:.\ $ This explains the example you gave in your comment, where $\rm\:m,n = 6,10\:$ so $\rm\:lcm(m,n) = 30\:,\:$ hence $\rm\: x= 0\:$ and $\rm\:x+30 = 30\:$ both map to $\rm\:(0,0)\:$ but $\rm\: 30\not\equiv 0\ (mod\ 60)\:.$
The existence of solutions is also easy. Clearly $\rm\:|\mathbb Z\ mod\ mn| = mn = |\mathbb Z\ mod\ m \times \mathbb Z\ mod\ n|\: $ so the above map being $1$ to $1$ on these equal cardinality finite sets implies the map is also onto, i.e. every pair $\rm\:(i\ mod\ m,\:j\ mod\ n)\:$ is the image of some $\rm\: x\ mod\ mn\:.\:$ Summing up: if $\rm\:gcd(m,n) = 1$ then there exists a unique solution $\rm\ x\ mod\ mn\ $ to the congruences $\rm\ x\equiv i\ (mod\ m),\ x\equiv j\ (mod\ n)\:.\ $ For a simple constructive proof see here.