The answer is $n = p+1$. First, let us $0$-index the grid, so that labels are from $0$ to $n-1$. For the construction, we set $a_{ij} = i+j$ for all $i, j < p$. Moreover, we set $a_{pi} = a_{ip} = 1$ for $i < p$ and $a_{pp} = 0$. It may be verified that this grid works. For the bound, we consider quadruples $(i, j, k, r)$ with $0 \leq i < j < n, 0 \leq k < n, $ and $r \in \mathbb{F}_p^*$ so that the following are satisfied: $a_{ik}, a_{jk} \not \equiv 0 \pmod p$ $a_{ik} \equiv ra_{jk} \pmod p$ Let us first count this by $(i, j, r)$. If there are two permissible values of $k$ that work, say $k_1, k_2$ the rectangle formed by rows $i, j$ and columns $k_1, k_2$ would give a contradiction. Thus the count of such quadruples is at most ${n \choose 2}(p-1)$ on the one hand. We next count the quadruples by $(i, j, k)$. Each such triple spits out an $r$, so long as the first condition is ensured. First, column $k$ contains at most one element divisible by $p$, since if there were two such elements we could select any rectangle they were a part of to get a contradiction. As a result, for each column, we can get at least ${n-1 \choose 2}$ triples $(i, j, k)$ leading to at least $n {n-1 \choose 2}$ quadruples overall. Thus we have \[{n \choose 2} (p-1) \geq n {n-1 \choose 2}\]which yields $n \leq p+1$, solving the problem.