, 2021

Answer: All integers $n$ for which $n+1$ is a prime.

First, observe that every pair $x, y$ of real numbers for which the sum $x+y$ is integer satisfies
$$\lfloor x\rfloor+\lfloor y\rfloor \geqslant x+y-1 \tag{1}$$
The inequality is strict if $x$ and $y$ are integers, and it holds with equality otherwise.
We estimate the sum $S$ as follows.
$$\begin{aligned} 2 S=\sum_{1 \leqslant i, j \leqslant n}\left(\left\lfloor\frac{ij}{n+1}\right\rfloor+\left\lfloor\frac{ij}{n+1}\right\rfloor\right)= & \sum_{1 \leqslant i, j \leqslant n}\left(\left\lfloor\frac{ij}{n+1}\right\rfloor+\left\lfloor\frac{(n+1-i)j}{n+1}\right\rfloor\right) \\ & \geqslant \sum_{1 \leqslant i, j \leqslant n}(j-1)=\frac{(n-1)n^{2}}{2} . \end{aligned}$$
The inequality in the last line follows from (1) by setting $x=ij/(n+1)$ and $y=(n+1-i)j/(n+1)$, so that $x+y=j$ is integral.
Now $S=\frac{1}{4} n^{2}(n-1)$ if and only if the inequality in the last line holds with equality, which means that none of the values $ij/(n+1)$ with $1 \leqslant i, j \leqslant n$ may be integral.
Hence, if $n+1$ is composite with factorisation $n+1=ab$ for $2 \leqslant a, b \leqslant n$, one gets a strict inequality for $i=a$ and $j=b$. If $n+1$ is a prime, then $ij/(n+1)$ is never integral and $S=\frac{1}{4} n^{2}(n-1)$.

To simplify the calculation with indices, extend the table by adding a phantom column of index 0 with zero entries (which will not change the sum of the table). Fix a row $i$ with $1 \leqslant i \leqslant n$, and let $d:=\operatorname{gcd}(i, n+1)$ and $k:=(n+1) / d$. For columns $j=0, \ldots, n$, define the remainder $r_{j}:=ij \bmod (n+1)$. We first prove the following

Claim. For every integer $g$ with $1 \leqslant g \leqslant d$, the remainders $r_{j}$ with indices $j$ in the range
$$(g-1)k \leqslant j \leqslant gk-1 \tag{2}$$
form a permutation of the $k$ numbers $0 \cdot d, 1 \cdot d, 2 \cdot d, \ldots, (k-1) \cdot d$.

Proof. If $r_{j'}=r_{j}$ holds for two indices $j'$ and $j$ in (2), then $i(j'-j) \equiv 0 \bmod (n+1)$, so that $j'-j$ is a multiple of $k$; since $|j'-j| \leqslant k-1$, this implies $j'=j$. Hence, the $k$ remainders are pairwise distinct. Moreover, each remainder $r_{j}=ij \bmod (n+1)$ is a multiple of $d=\operatorname{gcd}(i, n+1)$. This proves the claim.

We then have
$$\sum_{j=0}^{n} r_{j}=\sum_{g=1}^{d} \sum_{\ell=0}^{(n+1)/d-1} \ell d=d^{2} \cdot \frac{1}{2}\left(\frac{n+1}{d}-1\right) \frac{n+1}{d}=\frac{(n+1-d)(n+1)}{2} . \tag{3}$$
By using (3), compute the sum $S_{i}$ of row $i$ as follows:
$$\begin{align*} S_{i}=\sum_{j=0}^{n}\left\lfloor\frac{ij}{n+1}\right\rfloor & =\sum_{j=0}^{n} \frac{ij-r_{j}}{n+1}=\frac{i}{n+1} \sum_{j=0}^{n} j-\frac{1}{n+1} \sum_{j=0}^{n} r_{j} \\ & =\frac{i}{n+1} \cdot \frac{n(n+1)}{2}-\frac{1}{n+1} \cdot \frac{(n+1-d)(n+1)}{2}=\frac{(in-n-1+d)}{2} \tag{4} \end{align*}$$
Equation (4) yields the following lower bound on the row sum $S_{i}$, which holds with equality if and only if $d=\operatorname{gcd}(i, n+1)=1$ :
$$S_{i} \geqslant \frac{(in-n-1+1)}{2}=\frac{n(i-1)}{2} . \tag{5}$$
By summing up the bounds (5) for the rows $i=1, \ldots, n$, we get the following lower bound for the sum of all entries in the table
$$\sum_{i=1}^{n} S_{i} \geqslant \sum_{i=1}^{n} \frac{n}{2}(i-1)=\frac{n^{2}(n-1)}{4} . \tag{6}$$
In (6) we have equality if and only if equality holds in (5) for each $i=1, \ldots, n$, which happens if and only if $\operatorname{gcd}(i, n+1)=1$ for each $i=1, \ldots, n$, which is equivalent to the fact that $n+1$ is a prime. Thus the sum of the table entries is $\frac{1}{4} n^{2}(n-1)$ if and only if $n+1$ is a prime.