# multiplication table for mod n, n prime

How do I prove that multiplication table for mod n, where n is a prime gives rise to a latin square if the row and column of 0 is omitted? I need to prove for a fixed i, i * k is distinct when k runs from 1 to n.

How do I use the fact that n doesn't have any factors other than 1 and itself?

## 2 Answers

You need the fact that if $m$ and $n$ are relatively prime integers, then there exist integers $x$ and $y$ so that $mx+ny=1$. This is usually called Bezout's theorem, I think. This will tell you that the nonzero elements of the integers mod $n$ form a group under multiplication. Why?

• I still can't get to it. can you give me one more hint? – user81055 Jun 16 '13 at 0:51
• So lets say $n$ is prime, and $1\leq m < n$, then $m$ is relatively prime to $n$ because $n$ is prime. Let $x$ and $y$ be as above. Then $mx+ny=1$, so $mx=1$ mod $n$. So every nonzero element of the integers mod $n$ has a multiplicative inverse. Does this help you understand why the nonzero integers mod $n$ form a group under multiplication? – Dylan Yott Jun 16 '13 at 1:04
• You only really need that if $n|ab$ then $n|a$ or $n|b$. (But your result is used to prove that.) – Thomas Andrews Jun 16 '13 at 1:54
• That tells us that $\mathbb Z / n\mathbb Z$ is an integral domain, and we know that every finite integral domain is a field. Is this roughly what you mean? – Dylan Yott Jun 16 '13 at 2:08

You want to show that for an $1\leq i\lt n$ (which corresponds to the row $i$ of the table) and all $1\leq k\neq m\lt n$ we have $i\cdot k\neq i\cdot m \pmod n$, right? This follows from the fact that for $1\leq k\neq m\lt n$ we have
$$i\cdot k= i\cdot m \pmod n\iff i\cdot(k-m)=0\pmod n\iff n\mid i\cdot (k-m).$$ Note here that we exclude $i,k,m=n$ since $n=0\pmod n$. Now (since we assuming $n$ to be prime) show that $$i\cdot k= i\cdot m \pmod n\iff k=m.$$ Therefore each row contains the $n-1$ numbers $1,2,\ldots,n-1$. Similarly you can show the same for each column.
It follows that the table is a Latin square.