The answer is all $n$ such that $n+1$ is prime. Note that if $n$ works, then $4 \mid n^2(n-1)$, hence $n$ is even or $\equiv 1 \pmod 4$. We examine the two cases: Case 1: $n$ is even. Call a pair $(i,j)$ good if $n \mid ij$ and bad otherwise. Noe that we may organize the $n^2$ entries of the board in pairs of $4$, as follows: $\lfloor \frac{ij}{n+1} \rfloor, \lfloor \frac{(n+1-i)j}{n+1} \rfloor, \lfloor \frac{i(n+1-j)}{n+1} \rfloor, \lfloor \frac{(n+1-i)(n+1-j)}{n+1} \rfloor$ (note that each pair $(i,j)$ is counted $4$ times) It can easily be checked that the sum of all numbers in each group is either $n+1$ (if $(i,j)$ is good) or $n-1$ (if $(i,j)$ is bad) -- just notice that the sum of every two numbers in the floors is an integer. Hence, the total sum of the entries is $\frac{(n+1)x+(n-1)y}{4}$, with $x$ being the number of good pairs and $y$ being that of the bad pairs. It is clear that $x+y=n^2$. According to the problem statement, $(n+1)x+(n-1)y=n^2(n-1)=(n-1)(x+y)$, and so $x=0$, i.e. all pairs $(i,j)$ are bad. If $n+1$ is not prime, let $n+1=ab$ with $a,b >1$, and so the pair $(a,b)$ is good, a contradiction. However, if $n+1$ is prime, then $n+1 \mid ij$ implies $n+1 \mid i$ or $n+1 \mid j$, both absurd since $1 \leq i,j \leq n$. Case 2: $n \equiv 1 \pmod 4$. We will use the very same idea, but a bit more carefully, since now there might be some internal overlap in the groups we formed before (precisely in the $i=(n+1)/2$ or $j=(n+1)/2$ case). Call a pair $(i,j)$ good if $i,j \neq (n+1)/2$ and $(n+1) \mid ij$ and bad if $i,j \neq (n+1)/2$ and $(n+1) \nmid ij$. It is clear that $x+y=(n-1)^2$, where $x$ and $y$ denote the number of good and bad pairs, respectively. By the same idea as above, the sum of all entries of the board that do not belong in the middle row or column is $\frac{(n+1)x+(n-1)y}{4}$. In order to deal with the remaining entries, we note that $\lfloor \frac{((n+1)/2)i}{n+1} \rfloor$ takes the values $0,1,1,2,2,\ldots,(n-1)/2,(n-1)/2$ when $i$ runs from $1$ to $n$, and so the sum of the entries that belong in the middle row or column is $2(1+1+2+2+\ldots+(n-1)/2+(n-1)/2)-(n-1)/4=(n^2-1)/2-(n-1)/4=(2n^2-n-1)/4$ Hence, $\frac{(n+1)x+(n-1)y}{4}+\frac{2n^2-n-1}{4}=\frac{n^3-n^2}{4}$, and so $(n+1)x+(n-1)y=n^3-3n^2+n+1$. Moreover, $x+y=(n-1)^2,$ and so $(n-1)^3=(n-1)x+(n-1)y\leq (n+1)x+(n-1)y=n^3-3n^2+n+1<n^3-3n^2+3n-1=(n-1)^3,$ a contradiction. Thus, all solutions are $n=p-1$ where $p$ is prime.

When you realise A2 is a better N2 and N2 is a better A2 ...

This problem use the same idea from Baltic Way 2001… It’s basically the same but with some change. https://artofproblemsolving.com/community/c6h378171p2089076

The answer is $n+1$ prime. Because \[ \sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} = \frac{1}{n+1} \left( 1+2+\dots+n \right)^2 = \frac{n^2(n+1)}{4} \]the equation is equivalent to \[ \sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1} \right\} = \frac{n^2}{2} \qquad (\clubsuit) \]where $\{ x \}$ is the fractional part of $x$. Now \[ \left\{ \frac{ij}{n+1} \right\} + \left\{ \frac{i(n+1-j)}{n+1} \right\} = \begin{cases} 1 & n+1 \nmid ij \\ 0 & \text{otherwise}. \end{cases} \]So by pairing up terms, we find $(\clubsuit)$ is true only when the $0$ case never occurs. Thus $n$ works exactly if $n+1$ is not the product of two smaller positive integers, i.e. is prime.

The answer is $n = p-1$ for all $p$ prime We do pairing. Notice that, \[ \left \lfloor \frac{i j}{n+1} \right \rfloor + \left \lfloor \frac{i (n + 1 - j)}{n+1} \right \rfloor \geq \frac{i j}{n+1} + \frac{i (n + 1 - j)}{n+1} - 1 = i - 1 \] Where equality occurs when $n + 1 \nmid i j$. Summing up all the entries: \[ \sum_{i = 1}^{n} \sum_{j = 1}^{n} \left \lfloor \frac{i j}{n+1} \right \rfloor \geq \sum_{i = 1}^{n} \left (\frac{n}{2} \cdot (i - 1) \right ) = \frac{n^2(n-1)}{4} \] So, we want $n + 1 \nmid i j \: \forall \: 1 \leq i,j \leq n$. This obviously happens if $n+1$ is prime. Otherwise, let $n+1 = ab $ and take $i = a$ and $j = b$.

Just like gghx, I feel like this problem (which is really number theory) and N2 (which is really algebra) should be interchanged in the Shortlist! Rewrite the condition as $\sum_{i=0}^{m-1}\sum_{j=0}^{m-1}\left\lfloor \frac{ij}{m} \right\rfloor = \frac{(m-1)^2(m-2)}{4}$ where $m = n + 1 \geq 2$. Since $\sum_{i=0}^{m-1}\sum_{j=0}^{m-1}ij = (\sum_{k=0}^{m-1}k)^2 = \frac{m^2(m-1)^2}{4}$, the condition is equivalent to $\sum_{i=1}^{m-1}\sum_{j=0}^{m-1} [ij \pmod m] = \frac{m(m-1)^2}{2}$. Now trying the first few $m$ suggest that only primes would work. Indeed, if $m$ is coprime with a fixed $i$, then for a fixed $i$, the numbers $ij \pmod m$, $j=0,1,\ldots,m-1$ are all distinct (if $ij_1 \equiv ij_2 \pmod m$, then $m \mid i(j_1-j_2)$, $i$ and $m$ are coprime and so $j_1\equiv j_2 \pmod m$) and since they are $m$ in number, they must be $0$, $1$, $\ldots$, $m-1$ in some order. So the contribution of such an $i$ is $1 + 2 + \cdots + m-1 = \frac{m(m-1)}{2}$. More generally, it follows that if gcd$(i,m) = d_i$, then replacing $i$ and $m$ with $i/d_i$ and $m/d_i$ in the above argument yields $\sum_{j=0}^{m-1} ij \pmod m = d_i\sum_{j=1}^{m} \frac{i}{d_i} j \pmod {\frac{m}{d_i}} = d_i^2\sum_{j=1}^{m/d_i} \frac{i}{d_i} j \pmod {\frac{m}{d_i}} = d_i^2 \frac{\frac{m}{d_i}(\frac{m}{d_i}-1)}{2} = \frac{m(m-d_i)}{2}$. Overall, $\sum_{i=1}^{m-1}\sum_{j=0}^{m-1}ij \pmod m = \sum_{i=1}^{m-1} \frac{m(m-\mbox{\scriptsize gcd}(i,m))}{2}$. Each summand is at most $\frac{m(m-1)}{2}$ and the number of summands is $m-1$, so the condition requires equality to hold. But this occurs if and only if gcd$(i,m) = 1$ for all $i=1,2,\ldots,m-1$ which is equivalent to $m$ being prime. Therefore all working $n$ are of the form $p-1$, where $p$ is any prime.

ISL 2021 A2. For every $n\in\mathbb Z_+$ consider the $n\times n$ table with entry $\left\lfloor\frac{ij}{n+1}\right\rfloor$ at the intersection of row $i$ and column $j$, for every $i=1, \dots, n$ and $j=1, \dots, n$. Determine all $n\in\mathbb Z_+$ for which the sum of the $n^2$ entries in the table is equal to $\frac14n^2(n-1)$. Solution. All such integers $n$ are those of the form $n=p-1$, where $p$ is a prime. Define \begin{align*}f(n)&=\sum_{i, j=1}^n\left\lfloor\frac{ij}{n+1}\right\rfloor,\\g(n)&=\frac14n^2(n-1),\\\overline f(n)&=\sum_{i, j=1}^n\frac{ij}{n+1}=\frac1{n+1}\sum_{i=1}^n\left(i\sum_{j=1}^nj\right)=\frac14n^2(n+1),\\ [a]_b&\text{ to be the integer such that a}\equiv [a]_b\pmod b\text{ and }0\le[a]_b<b,\\\tilde f(n)&=\sum_{i, j=1}^n\left\{\frac{ij}{n+1}\right\}=\sum_{i, j=1}^n\frac{[ij]_{n+1}}{n+1}.\end{align*}Observe that $\overline f(n)=f(n)+\tilde f(n)$, so \[f(n)=g(n)\iff\tilde f(n)=\overline f(n)-g(n)=\frac12n^2.\]Now it is well-known that $\{1, \dots, n\}=k\{1, \dots, n\}$ for any $\gcd(k, n+1)=1$. Hence \[\tilde f(p-1)=\frac1p\sum_{i, j=1}^{p-1}[ij]_p=\frac1p(p-1)\sum_{j=1}^{p-1}j=\frac12(p-1)^2.\]Therefore all integers of the form $n=p-1$ satisfy the problem condition. On the other hand, if $n$ is not of this form then choose a prime $p\mid n+1$ but $p<n+1$. Claim that \[\sum_{j=1}^n[kpj]_{n+1}<\frac{n(n+1)}2\]for all $k\in\mathbb Z_+$. In fact, all the residues $[kpj]_{n+1}$ are multiples of $p$, and they are $p, 2p, 3p, \dots, \left(\frac{n+1}p-1\right)p, 0, p, 2p, 3p, \dots, \left(\frac{n+1}p-1\right)p, 0, \dots$. Thus the sum is just \[p\sum_{r=1}^{\frac{n+1}p-1}rp=p^2\left(\frac{\left(\frac{n+1}p-1\right)\left(\frac{n+1}p\right)}2\right)=\frac12(n+1-p)(n+1)<\frac12n(n+1),\]as desired. Therefore \begin{align*}\tilde f(n)&=\frac1{n+1}\sum_{i, j=1}^n[ij]_{n+1}\\&=\frac1{n+1}\left(\sum_{\substack{1\le i, j\le n\\\gcd(i, n+1)\ne 1}}[ij]_{n+1}+\sum_{\substack{1\le i, j\le n\\\gcd(i, n+1)=1}}[ij]_{n+1}\right)\\&<\frac1{n+1}\left((n-\phi(n+1))\frac12n(n+1)+\sum_{\substack{1\le i, j\le n\\\gcd(i, n+1)=1}}[ij]_{n+1}\right)\\&=\frac1{n+1}\left((n-\phi(n+1))\frac12n(n+1)+\sum_{\substack{1\le i, j\le n\\\gcd(i, n+1)=1}}[j]_{n+1}\right)\\&=\frac1{n+1}\left((n-\phi(n+1))\frac12n(n+1)+\phi(n+1)\frac{n(n+1)}2\right)\\&=\frac1{n+1}\left(n\cdot\frac{n(n+1)}2\right)\\&=\frac12n^2.\end{align*}This suggests that all integers $n$ that are not of that form are not satisfying the problem condition, establishing the proof.

We have \begin{align*} 2\sum_{i=1}^n\sum_{j=1}^n\left\lfloor\frac{ij}{n+1}\right\rfloor&=\sum_{i=1}^n\sum_{j=1}^n\left(\left\lfloor\frac{ij}{n+1}\right\rfloor+\left\lfloor\frac{i(n+1-j)}{n+1}\right\rfloor\right)\\ &\geq\sum_{i=1}^n\sum_{j=1}^n\left(\left\lfloor\frac{i(n+1)}{n+1}\right\rfloor-1\right)\\ &=\sum_{i=1}^n\sum_{j=1}^n(i-1)\\ &=\sum_{i=1}^nn(i-1)\\ &=\frac{(n-1)n^2}2. \end{align*}Therefore, the equation is true if and only if equality holds in all of the equation. This happens if and only if $\frac{ij}{n+1}$ is a noninteger for all $n+1$, which happens if and only if $n+1$ is prime.

The answer is $n = p-1$, where $p$ is a prime. Let $n$ be a positive integer satisfying the inequality (there exists an $n$ since $n = 1$ can be easily seen to work). Note that $$\sum_{i=1}^{n}\sum_{j=1}^{n}\left \lfloor \frac{ij}{n+1}\right \rfloor = \sum_{i=1}^{n}\sum_{j=1}^{n}\left(\frac{ij}{n+1} - \left \{\frac{ij}{n+1}\right \}\right) = \frac{1}{n+1}\sum_{i=1}^{n}\sum_{j=1}^{n}ij - \sum_{i=1}^{n}\sum_{j=1}^{n}\left \{\frac{ij}{n+1}\right \} = \frac{1}{n+1}\cdot (1 + 2 + \cdots + n)^2 - \sum_{i=1}^{n}\sum_{j=1}^{n}\left \{\frac{ij}{n+1}\right \} = \frac{1}{n+1}\left(\frac{n(n+1)}{2}\right)^2 - \sum_{i=1}^{n}\sum_{j=1}^{n}\left \{\frac{ij}{n+1}\right \} = \frac{n^2(n+1)}{4} - \sum_{i=1}^{n}\sum_{j=1}^{n}\left \{\frac{ij}{n+1}\right \}.$$Thus, we have $$\sum_{i=1}^{n}\sum_{j=1}^{n}\left \{\frac{ij}{n+1}\right \} = \frac{n^2(n+1)}{4} - \frac{n^2(n-1)}{4} = \frac{n^2}{2}.$$Now, fix a $1\leq i\leq n$, and let $g := \gcd(i, n+1)$. Then, $\{i, 2i, \cdots, ni\}$ is a permutation of $\{g, 2g, \cdots, ng\}$ modulo $n+1$ (since $f(k) = \frac{i}{g}k$ is a bijection modulo $(n+1)/g$), so the sum for that particular $i$ is $$\left \{\frac{0}{n+1}\right \} + \left \{\frac{g}{n+1}\right \} + \left \{\frac{2g}{n+1}\right \} + \cdots + \left \{\frac{ng}{n+1}\right \}.$$Since $f(k) = gk$ repeats after every $\frac{n+1}{g}$ (modulo $n+1$), and there are $g$ such blocks of repetition, we have that this is equal to $$g\left(\left \{\frac{0}{n+1}\right \} + \left \{\frac{g}{n+1}\right \} + \cdots + \left \{ \frac{g\left(\frac{n+1}{g} - 1\right)}{n+1}\right \}\right) = \frac{g^2}{n+1}\left(0 + 1 + 2 + 3 + \cdots + \frac{n+1}{g}-1\right) = \frac{g^2}{n+1}\cdot \frac{\left(\frac{n+1}{g} - 1\right)\frac{n+1}{g}}{2} = \frac{n+1-g}{2} \leq \frac{n}{2},$$equality holding when $g = 1$. Thus, summing over all $1\leq i\leq n$, this is $\leq \frac{n}{2}\cdot n = \frac{n^2}{2}$, equality holding when all $\gcd(i, n+1) = 1$ for all $1\leq i\leq n$, i.e. $n+1$ is prime (if $n+1$ wasn't prime, take a prime divisor to get a non-$1$ gcd, and if $n+1$ is prime, than clearly everything less than $n+1$ is prime). However, the total sum is exactly $\frac{n^2}{2}$, so equality must indeed hold everywhere, ergo $n+1$ is prime, as desired.

This is easier even than A1 in my opinion, the grouping idea is too classical. Otherwise, nothing new here, but this is more like a sketch. Rewrite as $\sum \{ \frac{ij}{n+1}\} = \frac{n^2}{2}$ and group the terms $\{ \frac{ij}{n+1}\}+\{ \frac{i(n+1-j)}{n+1}\}$ and note that there sum is $1$ only if $n+1$ doesn't divide $ij$ and $0$ otherwise. Since zero can't appear, there are no numbers in $\{1,2,...,n\}$ divisible by $n+1$, hence it's prime.

The answer is all numbers that are one less than a prime. First, the statement can be reduced algebraically: \[\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor + \sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1} \right\}=\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1}= \frac{(\sum_{m=1}^n m)^2}{n+1}=\frac{(\frac{n(n+1)}{2})^2}{n+1}=\frac{n^2(n+1)}{4}\]If \[\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor=\frac{n^2(n-1)}{4}\]then it remains to find $n$ such that \[\sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1} \right\} = \frac{n^2(n+1)}{4} - \frac{n^2(n-1)}{4} = \frac{n^2}{4}\left((n+1)-(n-1)\right)=\frac{n^2}{2}.\]By pairing, the above is only false when $n+1 \mid ij$ for some pair(s) $(i, j)$. Since $i$ and $j$ range from $1$ to $n$, if $n+1$ were composite, it could be written as the product of two numbers less than it, which is covered in some pair $(i, j)$. Otherwise, $n+1$ would be prime, and no pair would be divisible by it as $n+1$ is greater than all $i$ and $j$. Therefore the answer is $n+1=p \Rightarrow \boxed{n=p-1}.$ Solved with a hint after the manipulation part, which was literally just "try finding the sol set".

Exactly same as v_Enhance's , Just posting for reference

Fix $i$. Since $\frac{ij}{n} + \frac{i(n+1-j)}{n} = i$ is an integer, \[ \left \{ \frac{ij}{n+1} \right \} + \left \{ \frac{i(n+1-j)}{n+1} \right \} = \begin{cases} 0 & \text{ if } n+1 \mid ij \\ 1 & \text{otherwise.} \end{cases} \] Adding from $j=1$ to $n$, we get \[ 2 \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} = \text{ number of indices } j \text{ such that } (n+1) \nmid ij \implies \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} \le \frac{n}{2}\] Adding over all $1 \le i \le n$, we get \[\sum_{i=1}^n \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} \le \frac{1}{2} \cdot n \cdot n = \frac{n^2}{2}\] Since \[\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} = \frac{n(n+1)}{2} \cdot \frac{n(n+1)}{2} \cdot \frac{1}{n+1} = \frac{n^2(n+1)}{4},\]we get \[\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor \ge \frac{n^2(n+1)}{4} - \frac{n^2}{2} = \frac{n^2(n-1)}{4}\] For equality, it must be the case that for all $1 \le i,j \le n$, we have $(n+1) \nmid ij$. Clearly, this is true if and only if $n+1$ is prime.

We will prove something stronger: $$\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor=\frac{n^2(n-1)}{4} + \sum_{\substack{d \mid n+1 \\ d<n+1}} \left(\frac{d-1}{2} \right) \varphi \left(\frac{n+1}{d} \right)$$From the above it is evident that $n$ satisfies the given equation iff $n+1$ is prime. To prove the identity, fix an $i<n+1$, and let $d=\gcd(i,n+1)$. Look at $$\sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor = \sum_{j=1}^n \frac{ij}{n+1} - \sum_{j=1}^n \frac{r(ij)}{n+1}= \frac{in}{2}-\frac{1}{n+1}\sum_{j=1}^n r(ij)$$where $r(\cdot)$ is the remainder upon division by $n+1$. Now, the numbers $i,2i, \dots ni, (n+1)i$ leave all possible remainders divisible by $d$: In fact the remainders are $d, 2d \dots n+1-d,0$ in some order, repeated $d$ times (because $\frac{n+1}{d} \cdot i \equiv 0 \pmod{n+1}$). Now the final remainder is $0$, so we can ignore it. The sum of all these remainders is then $d(d+2d+ \cdots (n+1-d))$, which simplifies to $\frac{(n+1)(n+1-d)}{2}$. Putting this in the above expression, we get $$\sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor = (i-1)\frac{n}{2} +\frac{d-1}{2}$$Note that we must have $d<n+1$, and the number of $i<n+1$ with $\gcd(i,n+1)=d$ is $\varphi \left(\frac{n+1}{d} \right)$. Therefore summing over all $i$ gives us the required answer.

The answer is $n$ such that $n+1$ prime, which we will prove works below and that they are the only solutions. Note that $$\sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1} \right\} = \sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1}-\lfloor \frac{ij}{n+1} \rfloor = \frac{n^2}{2}.$$Next, we get that $$n^2 = 2 \sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1} \right\} = \sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1} \right\} + \left\{ \frac{(n+1-i)j}{n+1} \right\}.$$Using the identity $$\left\{ \frac{ij}{n+1} \right\} + \left\{ \frac{i(n+1-j)}{n+1} \right\} = \begin{cases} 1 & n+1 \nmid ij \\ 0 & \text{otherwise}. \end{cases} \le 1$$, we have that equality must always hold, so $n+1 \nmid ij$ for all $i,j \in \{ 1,2, \dots, n \}$. This means that $n+1$ is prime and it proves that when $n+1$ is prime the equation holds so we are done.

Bad solution ... We claim the answer is all $n$ such that $n+1$ prime. Notice the RHS is equal to \begin{align*}\sum_{i=1}^n\sum_{j=1}^n\left(\frac{ij}{n+1}-\left\{\frac{ij}{n+1}\right\}\right)&=\sum_{i=1}^n\sum_{j=1}^n\frac{ij}{n+1}-\sum_{i=1}^n\sum_{j=1}^n\left\{\frac{ij}{n+1}\right\}\\&=\frac{(1+2+\dots+n)^2}{n+1}-\sum_{i=1}^n\sum_{j=1}^n\left\{\frac{ij}{n+1}\right\}\\&=\frac{n^2(n+1)}{4}-\sum_{i=1}^n\sum_{j=1}^n\left\{\frac{ij}{n+1}\right\}.\end{align*}If $n+1$ is prime, then $\{i,2i,\dots,ni\}\equiv\{1,2,\dots,n\}\pmod{n+1},$ so $$\sum_{i=1}^n\sum_{j=1}^n\left\{\frac{ij}{n+1}\right\}=\sum_{i=1}^n\frac{n(n+1)}{2(n+1)}=\sum_{i=1}^n\frac{n}{2}=\frac{n^2}{2}.$$Hence, $$\sum_{i=1}^n\sum_{j=1}^n\left\lfloor\frac{ij}{n+1}\right\rfloor=\frac{n^2(n+1)}{4}-\frac{n^2}{2}=\frac{n^2(n-1)}{4},$$as desired. Consider when $n+1$ is composite. If $\gcd(i,n+1)=1,$ then $$\sum_{j=1}^n\left\{\frac{ij}{n+1}\right\}=\frac{n}{2}$$as before. On the other hand, suppose $\gcd(i,n+1)=d>1,$ which must occur for at least one $i$ since $n+1$ is composite. Letting $m=(n+1)/d$ and $k=i/d,$ we will calculate the sum of the residues of $ij$ modulo $n+1$ for $j=1,2,\dots,n.$ From $j=\ell m+1$ to $j=(\ell+1)m,$ where $\ell=0,1,\dots,d-1,$ we know $ij\equiv dkj\equiv 0\pmod{d}$ for all $j$ and $$\{i(\ell m+1),i(\ell m+2),\dots,i(\ell+1)m\}\equiv \{0,i,2i,\dots,(m-1)i\}\equiv\{0,1,\dots,m-1\}\pmod{m}.$$Since $\gcd(m,d)=1,$ we conclude $$\{i(\ell m+1),i(\ell m+2),\dots,i(\ell+1)m\}\equiv \{0,d,2d,\dots,(m-1)d\}\pmod{n+1}.$$Notice all residues in the final set are less than $n+1.$ Therefore, $$\sum_{j=1}^n\left\{\frac{ij}{n+1}\right\}=\sum_{\ell=0}^{d-1}\sum_{t=1}^m\left\{\frac{i(\ell m+t)}{n+1}\right\}=\frac{1}{n+1}\sum_{\ell=0}^{d-1}(0+d+2d+\dots+(m-1)d)=\frac{1}{n+1}\frac{d^2(m-1)m}{2}<\frac{n(n+1)}{2(n+1)}.$$Hence, $$\sum_{i=1}^n\sum_{j=1}^n\left\{\frac{ij}{n+1}\right\}<\frac{n^2}{2}$$and the equation is false. $\square$

The given is equivalent to $\sum_{i=1}^{n} \sum_{j=1}^{n} \left\lfloor \frac{ij}{n+1} \right\rfloor (n+1) = \frac{n^2(n^2-1)}{4}$ $\sum_{i=1}^{n} \sum_{j=1}^{n} ij - \left\lfloor \frac{ij}{n+1} \right\rfloor (n+1) = \sum_{i=1}^{n} \sum_{j=1}^{n} ij - \frac{n^2(n^2-1)}{4} = \frac{n^2(n+1)^2}{4} - \frac{n^2(n^2-1)}{4} = \frac{n^2(n+1)}{2}$ But $ij - \left\lfloor \frac{ij}{n+1} \right\rfloor = ij \pmod{n+1},$ remainder of $ij$ dividing by $n.$ If $n+1$ is prime, then it's well known $\{a,2a,\ldots,na \} \pmod{n+1} = \{1,\ldots,n\},$ and thus the sum $\sum_{i=1}^{n} \sum_{j=1}^{n} ij \pmod{n+1} = n(1+\cdots+n) = \frac{n^2(n+1)}{2},$ so the identity holds. If $n+1$ is not prime, we show that for some multisets $\{i, 2i, \ldots, ni\} \pmod{n+1}$ the sum is strictly less than $\frac{n(n+1)}{2}.$ If $\gcd(i,n+1) = 1$ then $\{i,2i,\ldots,ni\} \pmod{n+1} = \{1,2,\ldots,n\}.$ On the other hand if $\gcd(i,n+1) = a > 1$ then $\{0,a,2a,\ldots,na\}$ is a permutation of the multiset $\{a,2a, \ldots (\frac{n+1}{a} - 1) a, 0, a, 2a, \ldots \}$ and the sum is then $a \cdot a \cdot (1+2+\cdots+(\frac{n+1}{a} - 1)) = a^2 \cdot \frac{1}{2} \cdot \left( \frac{n+1}{a} - 1 \right) \left( \frac{n+1}{a} \right) = \frac{(n+1-a)(n+1)}{2} < \frac{n(n+1)}{2}.$ Thus when $n+1$ is not prime, the sum $\sum_{i=1}^{n} \sum_{j=1}^{n} ij \pmod{n+1} < \frac{n^2 (n+1)}{2}.$ We conclude that the identity holds exactly for $n+1$ prime. $\blacksquare$

Let $f(i,j)=\left\lfloor \frac{ij}{n+1} \right\rfloor$ We have two cases: We compute \[f(i,j)+f(i,n+1-j)+f(n+1-i,j)+f(n+1-i,n+1-j)\]for every $(i,j)$. Note that the sum of the fractional parts of $\frac{ij}{n+1}$ will be $0$ when $n+1\mid ij$ or $2$ otherwise. Thus, the sum $f(i,j)+f(i,n+1-j)+f(n+1-i,j)+f(n+1-i,n+1-j)$ will be $n+1$ when $n+1\mid ij$ and $n-1$ otherwise. Thus in order to ensure that the total is $n^2(n-1)$ there must be no $n+1\mid ij$ which implies that $n+1$ is prime. We need $n^2(n-1)$ because we have counted everything four times.

The answer is $\boxed{n=p-1}$. Multiply by $n+1$ to give $\tfrac{n^2(n^2-1)}{4}$, noting that $(n+1)\lfloor\tfrac{ij}{n+1}\rfloor=ij-(ij\pmod{n+1})$. Specifically, $\textstyle\sum ij=\tfrac{n^2(n+1)^2}{4}$, so it is equivalent to have \[\sum_{i=1}^n\sum_{j=1}^n(ij\pmod{n+1})=\frac{n^2(n+1)}{2}.\]Given a fixed $i$ with $\gcd(i,n+1)=d$, \[\sum_{j=1}^n(ij\pmod{n+1})=\frac{n+1}{d}\sum_{k=1}^{(n+1)/d-1}dk\le\frac{n(n+1)}{2}\]with equality at $d=1$. Summing over $i=1,\dots,n$ forces $d=1$ for every $i$, meaning $n+1\in\mathbb{P}$. $\square$

The answer are all primes, decreased by $1.$ First we have $\sum_{i=1}^n \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} = \frac{1}{n+1}\left( \sum_{i=1}^n i \right) \left( \sum_{j=1}^n j \right) - \sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor =\frac{n^2(n+1)}{4}-\frac{n^2(n-1)}{4}=\frac{n^2}{2}.$ Next observe that $\left \{ \frac{ij}{n+1}\right \} + \left \{ \frac{i(n+1-j)}{n+1}\right \}=\left \{ \frac{ij}{n+1}\right \} + \left \{ \frac{-ij}{n+1}\right \},$ which equals to $0$ if $(n+1)\mid ij,$ and to $1$ otherwise. Therefore $\sum_{i=1}^n \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \}\leq \frac{n^2}{2},$ with equality occuring iff $n+1$ is prime.

wow this identity pretty useful $\sum^{n-1}_{k=1}\lfloor \frac{km}{n} \rfloor = \frac{(m-1)(n-1)+\gcd(m,n)-1 }{2}$ thus we have $\sum^n_{i=1}\frac{(i-1)(n)}{2}+\sum^n_{i=1}\frac{\gcd(i,n+1)}{2}-\frac{n}{2}=\frac{n^2(n-1)}{4}$ thus we just need to find such n so that $n \leq \sum^n_{i=1}\gcd(i,n+1) = n$ notice for all natural number $\gcd(a,b) \geq 1$ so each of em must be $\gcd(i,n+1) = 1$ so that the equality could hold if n+1 nonprime then if n+1 even thus $\gcd(2,n+1) = 2$ contradiction if n+1 odd $n+1 =m*p^k \gcd(m,p) = 1, $ notice there is some index where p exist since $1<p<m*p^k$ if n+1 prime then it just a complete residue system less than p it is evident each of em has gcd equal to 1 since if gcd(i,p) >1 i.e $\gcd(i,p) = p$ ,i multiple of p contradicting i less than p

Nice! A bit on the easy side of A2s imo The answer is $n+1$ prime; the key is to see $$\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} = \frac{1}{n+1} \left( 1+2+\dots+n \right)^2 = \frac{n^2(n+1)}{4}\implies\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor=\frac{n^2(n-1)}{4}\iff\sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1} \right\} = \frac{n^2}{2}.$$Indeed, $$\left\{ \frac{ij}{n+1} \right\} + \left\{ \frac{i(n+1-j)}{n+1} \right\} =\{ 1 \forall n+1 \nmid ij, 0\forall n+1\mid ij\}.$$By pairing, we deduce that we need $n+1\nmid ij$ always; in particular, we must have $n+1$ is prime. $\blacksquare$

We claim that this is true if and only if $n+1,$ is prime. Note, that $\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1}=\sum_{i=1}^n \frac{i(1+2+3+4+5+......+n)}{n+1}=\frac{(1+2+3+4+5+.....+n)^2}{n+1}=\frac{\frac{(n(n+1))^2}{4}}{n+1}=\frac{(n+1)\cdot n^2}{4}.$ Now, let $\left \{x\right\}=x-\lfloor x \rfloor$ note that $\sum_{i=1}^n \sum_{j=1}^n \left\{ \frac{ij}{n+1}\right\}=\frac{(n+1) \cdot n^2}{4}-\frac{(n-1)\cdot n^2}{4}=\frac{n^2}{2},$ next $\left\{\frac{ij}{n+1}\right\} + \left \{\frac{i(n+1-j)}{n+1}\right\},$ is $0$ if and only if $\frac{ij}{n+1}$ is an integer, but then contradicion so $n+1$ is prime.

The answer is when $n+1$ is prime. Multiply the equation by $n+1$ to get $$\sum ij-\sum (ij\pmod{n+1})=\frac{n^2(n+1)(n-1)}{4}.$$Of course, we have $$\sum ij = (\frac{n(n+1)}{2})^2,$$so this simply becomes $$\sum (ij\pmod{n+1})=\frac{n^2(n+1)}{2}.$$ Looking carefully at this statement, this is saying that the "average" residue in the multiplication table mod $n+1$ is $\frac{n+1}{2}$, aka the average of all distinct nonzero residues. If $n+1$ is prime this is clearly true as each row contains each nonzero residue exactly once. This "summing by row" method motivates the following claim: \begin{claim} Fix $i$. Then, we have $$\sum_{1\leq j\leq n}(ij\pmod{n+1})\leq n\times \frac{n+1}{2}$$with equality if and only if $i$ is relatively prime to $n+1$. \end{claim} \begin{proof} Every nonzero residue that is a multiple of $\gcd(i,n+1)$ shows up a $\gcd(i,n+1)$ times. Let this be $d$. Then, the total sum is $$d\times d(\frac{(\frac{n+1}{d}-1)(\frac{n+1}{d})}{2})=\frac{(n+1-d)(n+1)}{2}\leq \frac{n(n+1)}{2}$$with equality only when $d=1$. \end{proof} Summing this over all $i$, we get that all such $i$ need to be relatively prime to $n+1$. Hence, $n+1$ must be prime.

We note that \[ \frac{n^2(n-1)}{4} = \sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor = \sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} - \sum_{i=1}^n \sum_{j=1}^n\left \{ \frac{ij}{n+1} \right \} \]First, we have \[ \sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} = \sum_{i=1}^n \left ( \frac{i+2i+ \cdots +ni}{n+1} \right ) = \sum_{i=1}^n \frac{i}{n+1} \cdot \frac{n(n+1)}{2} = \sum_{i=1}^n \frac{in}{2} = \frac{n}{2} \cdot \frac{n(n+1)}{2} = \frac{n^2(n+1)}{4} \] Thus, \[ \frac{n^2(n-1)}{4} = \frac{n^2(n+1)}{4} - \sum_{i=1}^n \sum_{j=1}^n\left \{ \frac{ij}{n+1} \right \} \Longleftrightarrow \sum_{i=1}^n \sum_{j=1}^n\left \{ \frac{ij}{n+1} \right \} = \frac{n^2}{2} \] Claim: $\sum_{i=1}^n\left \{ \frac{ki}{n+1} \right \} \leq \frac{n}{2}$ with equality only at $\gcd(k,n+1)=1$. Assume $\gcd(k,n+1)=d$. We note that \[ \sum_{i=1}^n \left \{ \frac{ki}{n+1} \right \} = d \cdot \sum_{i=1}^{\frac{n+1}{d}} \frac{i}{(n+1)/d} = \frac{n-d+1}{2} \leq \frac{n}{2}\]with obvious only equality case at $d=1$ as desired. $\square$ Since \[ \frac{n^2}{2} = \sum_{i=1}^n \sum_{j=1}^n\left \{ \frac{ij}{n+1} \right \} \leq n \cdot \frac{n}{2}\]which implies that equality holds for each inequality above. Thus, if $k < n+1$ then $\gcd(k,n+1)=1$ which is equivalent to $n+1$ being prime.

The answer is $\boxed{n + 1 \text{ prime}}$. We cry. Split the double sum into integer and fractional parts so that we have, \begin{align*} \sum_{i = 1}^n \sum_{j = 1}^n \left\{ \frac{ij}{n+1} \right\} &= \sum_{i = 1}^n \sum_{j = 1}^n\left( \frac{ij}{n+1} \right) - \frac{n^2(n-1)}{4}\\ &= \sum_{i=1}^n \frac{n \cdot i}{2} - \frac{n^2(n-1)}{4}\\ &= \frac{n^2(n+1)}{4} - \frac{n^2(n - 1)}{4}\\ &= \frac{n^2}{2} \end{align*}Now interpret the fractional part thing as follows. We really just need, \begin{align*} \sum_{i=1}^n \sum_{j=1}^n (ij \bmod{n + 1}) &= \frac{n^2(n+1)}{2} \end{align*}Note that, \begin{align*} ij + i(n + 1 -j) \equiv 0 \pmod{n+1} \end{align*}For $n+1 \nmid ij$ we find that neither term is $0 \bmod n + 1$ and hence we have, \begin{align*} \left[ij \bmod{n+1}\right] + \left[i(n + 1 - j) \bmod{n+1}\right] = n + 1 \end{align*}for $n + 1 \nmid ij$. Otherwise if $n + 1 \mid ij$ clearly both terms are individually $0$ so they contribute $0$ to the sum. Thus let us define, \begin{align*} f(i, j) = \begin{cases} n+1 & n+1 \nmid ij \\ 0 & n + 1 \mid ij \end{cases} \end{align*}Now our double sum then evaluates to, \begin{align*} \sum_{i=1}^n \sum_{j=1}^n (ij \bmod{n + 1}) = \sum_{(i, j)} f(i, j) \end{align*}Note then that, \begin{align*} \sum_{(i, j)} f(i, j) \leq \frac{n^2(n + 1)}{2} \end{align*}with equality if and only if every $(i, j)$ contributes $n + 1$. This happens precisely when $n + 1 \mid ij$ never occurs. Thus we need the condition $n + 1$ prime as claimed.

We require that $n+1$ is a prime. We first rewrite the equation as \[ \sum_{i=1}^n \sum_{j=1}^n \left\{\frac{ij}{n+1}\right\} = \frac{n^2}{2}. \]Multiplying both sides by $n+1,$ if $f(k)$ is the remainder when $k$ is divided by $n+1,$ then we get \[ \sum_{i=1}^n \sum_{j=1}^n f(ij) = \frac{n^2(n+1)}{2}. \]For a fixed $i,$ consider the sequence $0,i,2i,\dots,ni.$ If we let $\gcd(n+1,i) = d,$ then this sequence is just $d$ copies of $0,d,2d,\dots,n+1-d,$ each of which has sum $d \cdot \frac{\frac{n+1}{d} \cdot \left(\frac{n+1}{d} - 1\right)}{2},$ which gives \[ \frac{(n+1)(n+1-d)}{2}. \]If we sum up over all $i,$ this becomes \[ \frac{n+1}{2} \cdot \sum_{i=1}^n (n+1-\gcd(n+1,i)). \]Spliting the sum gives \[ \frac{n+1}{2} \cdot (n(n+1) - \sum_{i=1}^n \gcd(n+1,i)). \]The sum on the right is at least equal to $n,$ so the entire sum is at most equal to \[ \frac{n+1}{2} \cdot (n(n+1) - n) = \frac{n^2(n+1)}{2}. \]Equality is achieved if and only if all of the gcd's are equal to $1,$ which happens if and only if $n+1$ is prime. Therefore, since all our steps are reversible, $n+1$ being prime is necessary and sufficient.

We claim the answer is all $n$ such that $n+1$ is prime. To start, rewrite the equation as: \[\sum_{i,j=1}^{n}{\frac{ij}{n+1}}-\sum_{i,j=1}^{n}{\left\lfloor\frac{ij}{n+1}\right\rfloor}=\frac{n^2(n-1)}{4}\]\[\frac{n^2(n+1)}{4}-\sum_{i,j=1}^{n}{\left\lfloor\frac{ij}{n+1}\right\rfloor}=\frac{n^2(n-1)}{4}\]\[\sum_{i,j=1}^{n}{\left\lfloor\frac{ij}{n+1}\right\rfloor}=\frac{n^2}{2}.\] Lemma: For constants $a,k$, if $\gcd (a,k)=1$, then $ab\pmod{k}$ contains all residues modulo $k$ for $b\in \{0,1,\dots,k-1\}$. Let $d_i=\gcd (n+1,i)$. We make the following claim: Claim: \[\sum_{i,j=1}^{n}{\left\lfloor\frac{ij}{n+1}\right\rfloor}=\frac{1}{n+1}\cdot\sum_{i=1}^{n}{\frac{(n+1)(n+1-d_i)}{2}}\]Proof: For now, disregard the denominator of $n+1$. This means we are looking at $ij \pmod{n+1}$. Fix $i$. To find the sum of the residues, such that $j\in S=\{0,1,\dots,n\}$, we factor out $d_i$. This results in the sum being: \[d_i\cdot \sum_{j\in S}{\frac{i}{d_i}\cdot j\pmod{\frac{n+1}{d_i}}}.\]Using our previous lemma, this is: \[d_i^2\cdot \frac{\left(\frac{n+1}{d_i}-1\right)\left(\frac{n+1}{d_i}\right)}{2}\]\[\frac{(n+1)(n+1-d_i)}{2}\text{ }\square\] Summing over all $i$, we get the sum being: \[\frac{1}{n+1}\sum_{i\in S}{\frac{(n+1)(n+1-d_i)}{2}}\leq \frac{1}{n+1}\sum_{i\in S}{\frac{(n+1)(n)}{2}}\leq \frac{n^2}{2},\]with equality occuring iff $d_i=1\text{ }\forall i\in S$, implying that $n+1$ must be prime, as desired $\blacksquare$

Quite easy actually

Remark: Proving the identity was actually a problem, that appeared as a P6 in the German Federal Round just a few years ago.

Just pairing lol Note that $$\sum_{i=1}^n \sum_{j=1}^n \frac{ij}{n+1} = \frac{1}{n+1} \cdot \left( \frac{n(n+1)}{2} \right)^2 = \frac{n^2(n+1)}{4}.$$Therefore, we just need to have $$\sum_{i=1}^n \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} = \frac{n^2}{2}.$$But this becomes $$n^2 = 2\sum_{i=1}^n \sum_{j=1}^n \left \{ \frac{ij}{n+1} \right \} = \sum_{i=1}^n \sum_{j=1}^n \left(\left \{ \frac{ij}{n+1} \right \} + \left\{ \frac{(n+1-i)j}{n+1} \right \} \right) = \sum_{i=1}^n \sum_{j=1}^n \left( \left \{ \frac{ij}{n+1} \right \} + \left\{ \frac{-ij}{n+1} \right \} \right).$$There are $n^2$ of these terms in total, and note that if $\frac{ij}{n+1}$ was an integer, then clearly $$\left \{ \frac{ij}{n+1} \right \} + \left\{ \frac{-ij}{n+1} \right \}$$becomes $0.$ Otherwise, it becomes $1.$ Hence, for $1 \leq i, j \leq n,$ $$\frac{ij}{n+1}$$cannot be an integer. Clearly, if $n+1$ is prime this works, but if $n+1=mn$ for $m, n \geq 2$ then we can just let $(i, j) = (m, n),$ so $n+1$ cannot be composite. Hence, only $n$ such that $n+1$ is prime works.