# Path through multiplication table mod p

Suppose I have a multiplication table mod $p$, with the $0$ row and column excluded. Suppose I wish to circle a different number from $1$ through $p-1$ in each column so that no two numbers are circled in any given row, no two numbers are circled in any given column, and no given number is circled twice in the table.

How can I prove that my wish is futile, i.e. this is not possible?

Let us assume $p$ is a prime, so each row and column has all the numbers $1$ through $p-1$. There are $(p-1)^2$ cells. Each one you pick excludes $3(p-2)$ other cells. Each excluded cell gets counted at most twice, so you have at least $\frac 32(p-2)(p-1)$ excluded cells. You then need $p-1+\frac 32(p-2)(p-1)=\frac 32p^2-\frac 72p+2$ cells total, which is too many when $p \ge 3$. It works fine for $p=2$
The argument still needs work when $p$ is composite. It is allowed to pick a cell with $0$?
• It gives more flexibility, reducing the number of excluded cells. It doesn't work for $p=4,6$, but for $p=8$ we have $(7,1),(6,2),(1,3),(4,4),(5,5),(3,6),(2,7)$ where the numbers are (row, column) in the table. – Ross Millikan Sep 11 '13 at 19:59