0
$\begingroup$

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'$$x\equiv i \quad(mod \;m)$$ $$x\equiv j \quad(mod \;n)$$ $$y\equiv i' \quad(mod \;m)$$ $$y\equiv j' \quad(mod \;n)$$

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' and $0\leq j,j', we have $i=i'$ and $j=j'$. Hence no two numbers in this table are the same.

However, there has to be a mistake here as I never took into account $m$ and $n$ to be coprime.

2 Answers 2

2

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.

  • 0
    But 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
1

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.