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' and 0\leq j,j'. $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
    @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.