1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I still can't get to it. can you give me one more hint? $\endgroup$ – user81055 Jun 16 '13 at 0:51
  • $\begingroup$ 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? $\endgroup$ – Dylan Yott Jun 16 '13 at 1:04
  • $\begingroup$ You only really need that if $n|ab$ then $n|a$ or $n|b$. (But your result is used to prove that.) $\endgroup$ – Thomas Andrews Jun 16 '13 at 1:54
  • $\begingroup$ 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? $\endgroup$ – Dylan Yott Jun 16 '13 at 2:08
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.