We can see that $s \leq m+n-\gcd(m,n)$ because we have the following construction for $m+n-\gcd(m,n)$: Let $\gcd(m,n)=d$. Consider the $d*d$ block: $k+1,k+2,.......,k+d-1,k+d$ $k+2,k+3,..........,k+d,k+1$ $k+3,k+4,...,k+d,k+1,k+2$ $.....................................$ $.....................................$ $k+d,k+1,...,k+d-2,k+d-1$ for a non-negative integer $k$. We will use $k^{*}$ as an abbreviation to represent this block. Then the following $m*n$ array given by: $0^{*},d^{*},2d^{*},.....(m-d)^{*}$ $d^{*},2d^{*},...,(m-d)^{*},m^{*}$ $...............................................$ $n-d^{*},n^{*},.......(m+n-2d)^{*}$ satisfies the property of the question for $m+n-\gcd(m,n)$. Now we will show that the smallest possible $s$ when $m,n$ are fixed is indeed $m+n-\gcd(m,n)$. Consider a working $(m*n)$ grid for the triple $(m,n,s)$ and assume WLOG that $m \geq n$ since the order of $m,n$ doesn't matter. Now let $a_1$ denote the number of columns (having $n$ numbers) having smallest number as $1$, similarly define $a_2,a_3,....a_m$ with $a_i$ as the number of columns having smallest number as $i$. Now we can assume that there exists at least one $1$ in the grid since otherwise we can just subtract all numbers by $1$ to get a smaller $s$. Thus each column has smallest element at most $m$ and thus the largest number of the grid is at most $m+n-1$. So for each row, the smallest number it contains should be at most $n$ since otherwise we will obtain that the grid has a number at least equal to $n+1+(m-1)=m+n>m+n-1$, a contradiction. Thus for any positive integer $i$ with $n \leq i \leq m$, we can see that each row contains exactly one occurence of $i$. So there are exactly $n$ occurences of $i$. Now we can see that for any $n \leq i \leq m$, ths number of times $i$ occurs can be written as $a_i+a_{i-1}+...+a_{i-n+1}$. Thus $n=a_i+a_{i-1}+...+a_{i-n+1}$. So if $i+1 \leq m$ we can see that $a_{i+1}+a_i+...+a_{i-n+2}$ is also equal to $n$. So for $n \leq i \leq m-1$, we have $a_{i-n+1}=a_{i+1}$. We can write this as: For a positive integer $i$, if both $i$ and $i+n$ are less than $m$, then $a_i=a_{i+n}$, so the sequence $a_k$ repeats after every $n$ terms. Now consider the following reduction process: Remove the $n$ columns having smallest number $\leq n$. For the remaining $(m-n)*n$ grid, subtract $n$ from each number. We claim that this process induces a working table for $(m-n,n,s-n)$ from the original table for $(m,n,s)$. Consider the $n$ columns which have smallest number $\leq n$ (there are exactly $n$ such columns since we proved $a_1+a_2+...a_n=n$ earlier). We can see that all the other numbers of the table are larger than or equal to $n+1$. Let $b_i$ denote the $n$ numbers formed by the intersection of the $i^{th}$ row and the $n$ columns considered. Now note that there are $a_1$ occurences of $1$, $a_1+a_2$ occurences of $2$, $a_1+a_2+a_3$ occurences of $3$,... so on upto $a_1+a_2+...a_n=n$ occurences of $n$. Now we can see that because no row has two occurences of the same number, the number of rows among the $b_i$ having smallest number $1$ must be $a_1$, the number of rows having smallest number $2$ must be $a_2$ (because as noted below, a row $b_i$ having smallest number $j$ must have all numbers between $j$ and $n$ so the rows having $1$ must have all numbers from $2$ to $n$ also), so on and so forth for all $i \leq n$ by induction (and noting again that any occurence of a number $\leq n$ must be among the $n$ columns we are considering). Also, since $m \geq n$ and the rows of the $m*n$ table formed $m$ consecutive number, any row $b_i$ having smallest number $j$ must have all numbers from $j$ to $n$ (because again as we noted any occurence of a number $\leq n$ must be among these $n$ columns). Let the number of "free spaces" of a row $b_i$ be defined as the number of elements larger than or equal to $n+1$ occuring in the row $b_i$. Now, we can see that a row $b_i$ having $j$ as its smallest number has $j-1$ free spaces due to the fact that all numbers from $j$ to $n$ are in that row $b_i$. Thus, we can combine our observations to see that among the $n$ rows $b_i$, for every $0 \leq j \leq n-1$, there are exactly $a_{j+1}$ rows having $j$ free spaces. But we can also see that for any $1 \leq i \leq n-1$, the number of occurrences of $n+i$ among the $n$ columns we are considering is $a_{i+1}+a_{i+2}+...+a_{n}$. Since each occurence is in a different row, we see that there are exactly $a_{i+1}+a_{i+2}+...+a_n$ rows having an occurrence of $n+i$. Now first of all, we see that $a_2+a_3+...+a_n$ rows have at least one free space and these are also the number of rows having an occurrence of $n+1$. Since any number larger than or equal to $n+1$ can only occur in the free spaces by definition, each row having at least one free space has an occurrence of $n+1$. This "fills" the rows with exactly one free space. Using similar reasoning, we can see that any row having at least two free spaces has an occurrence of $n+2$, the details work out exactly like above with $a_2+a_3+...+a_n$ replaced with $a_3+a_4+...+a_n$ and $n+1$ replaced with $n+2$. We can induct using this way and show that a row $b_i$ has an occurrence of $n+j$ if and only if it has at least $j$ free spaces. This proves a key observation after combining our results: Any row $b_i$ contains $n$ consecutive numbers and these are from $j$ to $n+j-1$ where $j$ is the smallest element of $b_i$. Since a full row in the $m*n$ table has $m$ consecutive numbers and the elements not among the $n$ columns considered are all greater than or equal to $n+1$, the full row which $b_i$ is part of has numbers from $j$ to $m+j-1$ and after removing the $n$ columns, it will have the remaining numbers from $n+j$ to $m+j-1$, which are $m-n$ consecutive numbers, and it will still be a set of $m-n$ consecutive numbers after subtracting each number by $n$. Thus, after the reduction process we obtain a working table for the triple $(m-n,n,s-n)$. So if we have a working table for $(m,n,s)$ with $m \geq n$, we have a working table for $(m-n,n,s-n)$. Note that $m+n-s$ remains invariant and the order of $m,n$ doesn't matter. So we can apply Euclidean algorithm to produce a working table for $(d,d,s+2d-m-n)$ where $d$ is the gcd of $m,n$. But it is clear that the smallest $s$ for $d,d$ has to be $d$ since each row has $d$ consecutive positive elements, so the largest element of each row is at least $d$. Thus we have $s+2d-m-n \geq d$ or $s \geq m+n-d$ or $s \geq m+n-\gcd(m,n)$. But we already provided a construction for $s=m+n-\gcd(m,n)$ in the beginning of our solution. Thus the answer is $s=m+n-\gcd(m,n)$. Proved

We 2 lemmas from the problem. Lemma 1- The smallest entry is at least $1$ and thus the largest entry in each row is at least $n. $ In each column is at least $m. $ Lemma 2- Adding a constant to each element of a valid array gives another valid array. From $\text {lemma 1} $ The minimum value of $s$ is $\max(m,n). $ From $\text {lemma 2}$ The smallest number in a valid array with each element $\le s $ will be $1. $ If $m=n$ then $s=m=n $ Filling the $$\begin {aligned} \text{row 1} =1,2,3,\hdots,n\\ \text {row 2}= 2,3,\hdots,n\\ \hdots\text {row n}=n,1,2,\hdots,(n-1) \end {aligned} $$We can prove if $m=kn$ or $(n=km), k $ is a positive integer. Then $s=kn\,(\text {or}\, km). $ It suffices to prove that for $m=kn. $ From the valid $n\times n$ array. The maximum entry is $n. $ From a second valid array by adding $n$ to each element, this second array has a minimum element $n+1$ and a maximum element $2n.$ Repeating this process recursively to produce $k $ valid arrays with the $i^{\text {th}}$ array having a minimum entry $(i-1)*n+1$ and a maximum entry $i*n. $ Notice that every row and every column of these arrays have the exact same set of entries. Stacking these $k $ valid arrays on top of each other gives us a $kn\times n$ array where each column contains all the integers between $1$ to $nk. $ Thus each column follows the conditions. By the construction all the rows follows the conditions. Thus, $nk\times n$ array is valid and the maximum entry is $nk, $ which is also the minimum possible maximal entry. Hence, $s=kn $ if $m=kn, $ and $s=km $ if $n=km. $ When $n\nmid m $ If m does not divide n. WLOG assume $m>n.$ If $m=\setminus=kn$ for integer $k.$ Then $s$ is at most $m+n-1.$ We may have the first column be $\{1,2,\hdots,m\}$ and the first row be $\{1,2,\hdots,n\} $ this will be true forall arrays even if $n$ divides $m.$ We can fill the rest validly by taking the second row to be $\{2,3,\hdots,n+1\}. $ Hence the last row is $\{m,m+1,\hdots, m+n-1\}. $ Proving the conjecture will lead to $s=m+n-\gcd(m-n) $ Clearly $s\ge\mathrm {max}(m,n).$ Let $A $ be the matrix with $a_{ij}=k. $ Where $1\le k\le\mathrm {max}(m,n) $ and $k==i+j(\mod\mathrm {max}(m,n)). $ On a row or a column, the values are just the residues of consecutive equivalence classes modulo $\mathrm {max}(m,n) $ and therefore they are distinct. Since we have achieved $s=\mathrm {max}(m,n),$ it will be minimal.

Here's a funny proof for $n$ prime: Shifting so that the smallest element is $1$ and permuting, we can make the final entry in the $k^{\text{th}}$ row be $k$ and the first entry in the $k^{\text{th}}$ column from the right be $k$. Letting $\varepsilon=e^{\frac{2\pi i}{n}}$ and letting an entry with the integer $k$ have the value of $\varepsilon^k$, it follows that the sum of the values of the entries is $0$ by summing through rows. Letting the smallest entries in column $\ell$ be $p_{\ell}$, summing through columns gives $(\varepsilon^{p_1}+\varepsilon^{p_2}+\dots +\varepsilon^{p_n})(1+\varepsilon+\varepsilon^2+\dots+\varepsilon^{m-1})=0\implies (\varepsilon^{p_1}+\varepsilon^{p_2}+\dots +\varepsilon^{p_n})(\varepsilon^m-1)=0$. If $n\mid m$, we trivially have $s\ge n$, giving $s=n=m+n-\gcd(m,n)$ through a simple construction. Otherwise, we have $\varepsilon^{p_1}+\varepsilon^{p_2}+\dots +\varepsilon^{p_n}=0$. Note that $p_i\in [1,n]$ for each $i$. Grouping terms, we may write $\varepsilon^{p_1}+\varepsilon^{p_2}+\dots +\varepsilon^{p_n}=a_1\varepsilon+a_2\varepsilon^2+\dots+a_n\varepsilon^n=0$ for positive integers $a_1,a_2,\dots, a_n$ with $a_1+a_2+\dots+a_n=n$; it now follows from the preliminary lemma in chapter 7 of PftB that $a_1=a_2=\dots=a_n=1$, implying that $\{p_1,p_2,\dots,p_n\}$ is a permutation of $\{1,2,\dots, n\}$. In particular, the largest element in the array is $n+(m-1)=m+n-\gcd(m,n)$. All in all, this gives $s=m+n-\gcd(m,n)$ for $n$ prime.

@above: This proof is easily generalizable to solve this problem and in fact it's the only solution we know for a very long time.

Here are two solutions (omitting the construction) I found; I think both are quite nice. The first solution was the one I submitted; as MarkBcc168 mentions, it was the only known solution for a while (which is surprising since people seem to have found many approaches).

Definitely my most favourite problem from the test. We claim that the minimum value of $s$ is $m+n- \gcd(m,n)$. The construction is pretty easy: Divide the grid into squares of size $\gcd(m,n)$ and fill each individually. Now we move on to the hard part. Consider an $m \times n$ grid filled in the required way. Let $s$ denote the largest number in the grid. WLOG $n \leq m$ and let $d=\gcd(m,n)$. We have to prove that $s \geq m+n-d$. WLOG assume that the smallest number in the grid is $1$, otherwise we can make $s$ smaller. $s \geq m$ trivially holds, so the case $n|m$ is done. Else let $m=qn+r$ where $r<n$. For any integer $i$, let $a_i$ (resp. $b_i$) denote the number of columns (resp. rows) in the grid whose smallest number is $i$. An easy double counting of the number of occurences of $i$ gives us $$a_i + a_{i-1} +\cdots +a_{i-n+1} = b_i+b_{i-1}+ \cdots +b_{i-m+1}$$Subtracting the relation for $i-1$ from the above gives $$a_i-a_{i-n}=b_i-b_{i-m}$$for all integers $i$. If $b_j>0$ for some $j \geq n$ then we have $s \geq m+n-1 \geq m+n-d$ and we are done. So assume the contrary. If $1 \leq i \leq n$ then $b_{i-m}=a_{i-n}=0$ so $a_i=b_i$. If $n < i \leq m$ then $b_i=b_{i-m}=0$ so $a_i=a_{i-n}$. So that means $a_i$ is (in the interval $[1,m]$ ) periodic with period $n$. Let $k$ be the largest positive integer $\leq r$ such that $a_{qn+k} >0$. Such a $k$ clearly exists because $a_{qn+1}=a_1>0$. Let $k'$ be the largest positive integer such that $b_{k'}>0$; clearly $k'<n$. Hence we get $$qn+k+n-1=s=k'+m-1$$which implies $k'=k+n-r$. Double counting occurences of $s$ gives us $$a_{k+n-r}=b_{k+n-r}=a_{qn+k}=a_{n+k}$$Now if $k<l \leq r$ then $$a_{l+n-r}=b_{l+n-r}=0=a_{qn+l}=a_{n+l}$$Also double counting the occurences of $s-1, s-2 \dots$ and easy induction starting with $l=0$ gives us $$a_{k+n-r-l}=b_{k+n-r-l}=a_{qn+k-l}=a_{n+k-l}$$for all integers $0 \leq l \leq k+n-r-1$. Both the above relations together imply that $a_{i+r}=a_i$ for all $1 \leq i \leq n$. So $a_i$ is (in the interval $[1,n+r]$ ) periodic with period $r$. Define a function $f: \mathbb{N} \rightarrow \mathbb{Z}$ by $f(i)=a_i$ for $1 \leq i \leq n$ and $f(i)=f(i-n)$ when $i>n$. The result in the above paragraph implies that $f$ is also periodic with period $r$ $\implies$ By Bezout's Lemma, $f$ must be periodic with period $ \gcd(n,r)=d$ $\implies$ $f(r-d+1)=f(1)$. But in that interval, values of $f$ and $a_i$ match $\implies$ $a_{r-d+1}=a_1>0$ $\implies$ $k \geq r-d+1$. Therefore $$s = qn+k+n-1 \geq m+n-d$$and we are done.

The minimum is $s=m+n-\gcd(m,n)$. We first prove we can do it with this $s$, then show it is the minimum. Part 1: Construction First, we show the construction for when $m=n$. In this case, simply let row 1 be $(1,2,\ldots,m)$, and then let row $i$ be this but cyclically shifted to the right $i-1$ times. This clearly gives each row a permutation of $(1,\ldots,m)$, since the columns are cyclic shifts of each other too. For example, for $m=n=3$, \[ \begin{tabular}{cccc} 1&2&3 \\ 2&3&1 \\ 3&1&2 \end{tabular} \]Next, we show the construction for $(m,n)=(g,bg)$ for some positive integer $b$. In this case, just repeat the $g\times g$ grid $b$ times rightwards, and each time, add $g$ to each sub-grid. This works since each column clearly does not change from initially being some consecutive permutation, and each row is a concatenation of $(1,2,\ldots,g)$, $(g+1,\ldots,2g)$, and so on till $((b-1)g+1,\ldots,bg)$, each in some order. For example, $(m,n)=(3,9)$ would be \[ \begin{tabular}{ccc|ccc|ccc} 1&2&3 & 4&5&6 & 7&8&9 \\ 2&3&1 & 5&6&4 & 8&9&7 \\ 3&1&2 & 6&4&5 & 9&7&8 \end{tabular} \]Next, we show the construction for $(m,n)=(ga,gb)$ for some positive integer $g$. In this case, repeat a $g\times gb$ board $a$ times downwards, and each time, add $g$ to every element of $g\times gb$. The rows and columns still work, since all we do is add a constant to their corresponding rows/columns earlier. For example, for $(m,n)=(6,9)$, \[ \begin{tabular}{ccc|ccc|ccc} 1&2&3 & 4&5&6 & 7&8&9 \\ 2&3&1 & 5&6&4 & 8&9&7 \\ 3&1&2 & 6&4&5 & 9&7&8 \\ \hline 4&5&6 & 7&8&9 & 10&11&12\\ 5&6&4 & 8&9&7 & 11&12&10 \\ 6&4&5 & 9&7&8 & 12&10&11 \end{tabular} \]Now let us find the maximum number used in this construction. Each $g\times g$ subgrid uses $g$ numbers each. And the top left subgrid has a maximum number $g$. If we take a path from the top left square to the bottom right square, first along the top row, then along the rightmost column, then each time the maximum number increases by exactly $g$. Since this path has $a+b-1$ steps, the maximum number by the end is $g(a+b-1)=ga+gb-g = m+n-g$. Since we want to minimize this quantity, it is optimal to take $g$ to be $\gcd(m,n)$, and then do the construction using $g=\gcd(m,n)$. Therefore, the maximum number used is $m+n-\gcd(m,n)$, as claimed. Part 2: Proving the Bound Suppose we have some $m\times n$ working grid. Let the entries be $a_{ij}$, for $1\le i \le m$, and $1\le j \le n$. Define the polynomials \begin{align*} P_i(X) &= X^{a_{i1}} + X^{a_{i2}} + \cdots + X^{a_{in}} \\ Q_j(X) &= X^{a_{1j}} + X^{a_{2j}} + \cdots + X^{a_{mj}}. \end{align*}Since $(a_{i1},\ldots,a_{in})$ is $(k,k+1,\ldots,k+n-1)$ for some $k$, hence $1+X+\cdots+X^{n-1}=\tfrac{X^n-1}{X-1}$ divides $P_i(X)$. Similarly, $\tfrac{X^m-1}{X-1}$ divides $Q_j(X)$. Note that $\sum_{i=1}^m P_i(X) = \sum_{j=1}^n Q_j(X)$; call this sum $S(X)$. We want to show that $\deg S(X) \ge m+n-\gcd(m,n)$, since $S(X)$ is the sum of all $X^{a_{ij}}$ over all $i,j$. We know \[ L(X):=\text{lcm}\left(\frac{X^n-1}{X-1}, \frac{X^m-1}{X-1}\right) \mid S(X). \] Claim: $\deg \text{lcm}(X^n-1,X^m-1) = m+n-\gcd(m,n)$. Proof: We use the cyclotomic factorization theorem. It is well known that \[ X^n-1 = \prod_{d\mid n} \Phi_d(X)\]where $\Phi_d(X)$ is the $d$'th cyclotomic polynomial. Also, all cyclotomic polynomials are well-known to be irreducible and pairwise relatively prime. Therefore, \[ \text{lcm}(X^n-1,X^m-1) = \prod_{d\mid n \text{ or }d\mid m} \Phi_d(X). \]Since $\deg \Phi_d(X) = \phi(d)$, we have \begin{align*} \deg \text{lcm}(X^n-1,X^m-1) &= \sum_{d\mid n \text{ or } d\mid m} \phi(d). \end{align*}If we let $f(n)=\sum_{d\mid n} \phi(d)$, then the RHS above is $f(n)+f(m)-f(\gcd(m,n))$ by PIE. But it is well-known that $f(n)=n$, which proves the lemma. $\square$ Now, $\deg L(X) = m+n-\gcd(m,n)-1$, since we divided by $X-1$. But since $L(X)$ has a constant term (if it didn't, then dividing out by $X$ keeps it divisible), it means there is a coefficient in front of $X^0$. However, this is not possible for $S(X)$, since all the numbers in the grid are positive. Therefore, $\deg S(X) \ge m+n-\gcd(m,n)$. The end.

An alternate proof for the lower bound:

This is edited a bit even though it was mentioned and things like that. Credits to Imayormaynotknowcalculus or post 5.

CantonMathGuy wrote: Here are two solutions (omitting the construction) I found; I think both are quite nice. The first solution was the one I submitted; as MarkBcc168 mentions, it was the only known solution for a while (which is surprising since people seem to have found many approaches).

The best sol which is short and involves generating functions

We claim that $s=m+n-\gcd(m,n)$. To achieve this, we must demonstrate two constructions. First, we demonstrate an easily generalizable construction for an $n\times n$ array achieving $s=n$. $\begin{pmatrix} 1&2&3&4\\ 2&3&4&1\\ 3&4&1&2\\ 4&1&2&3 \end{pmatrix}$ Then, we demonstrate an easily generalizable construction for a $m\times n$ array achieving $s=m+n-1$. $\begin{pmatrix} 1&2&3&4&5\\ 2&3&4&5&6\\ 3&4&5&6&7 \end{pmatrix}.$ By substituting a $\gcd(m,n)\times\gcd(m,n)$ block into each number of the $m/\gcd(m)\times n/\gcd(n)$ array, we can achieve $s=m+n-\gcd(m,n)$. Now, we show $s\ge m+n-\gcd(m,n)$. Consider some array with maximal entry $s$. Let each element $t$ correspond to the monomial $x^t$. Then the sum of all monomials is divisible by both $x+x^2+\cdots+x^m$ and $x+x^2+\cdots+x^n$. Since the gcd of these two polynomials is $x+x^2+\cdots+x^{\gcd(m,n)}$ (say, by the Euclidean algorithm on $x^m-1$ and $x^n-1$), this sum of monomials clearly has degree at least $m+n-\gcd(m,n)$. Thus $s\ge m+n-\gcd(m,n)$ as desired.

Worth noting that the problem also appears in the following reference, although the proof there is quite different: R. Kamalian, Interval Colorings of Complete Bipartite Graphs and Trees, Preprint of the Computing Centre of the Academy of Sciences of Armenia, Yerevan, 1989; English translation at arXiv:1308.254

The answer is $m+n-\gcd(m, n)$, with the construction explained in the last paragraph. Realize that the generating function $f(x)$ for the numbers in the grid is: divisible by $x$ because all numbers are positive, divisible by $x^m-1$ because of the rows condition, and divisible by $x^n-1$ because of the columns condition. I contend that the degree of $\operatorname{lcm}(x^m-1, x^n-1)$ is exactly $m+n-\gcd(m, n)$; this is clear upon noting the well-known fact that $\gcd(x^m-1, x^n-1) = x^{\gcd(m, n)}-1$. Thus \[ x \cdot \operatorname{lcm}\left(\frac{x^m-1}{x-1}, \frac{x^n-1}{x-1}\right) \]has degree $m+n-\gcd(m, n)$ as well, returning the desired lower bound. For the bound, split the grid into several $\gcd(m, n) \times \gcd(m, n)$ sized blocks, each of which contain $1, 2, \dots, \gcd(m, n)$ on the top row and cyclic shifts by 1 step for each subsequent row. Let $t$ denote the taxicab distance from block $C$ to the top-left block $B$. Then add $\gcd(m, n) \cdot t$ to each of the numbers in $C$. Verifying that this construction works is not difficult.

Lemma. Let $G$ be a weighted bipartite graph with bipartition $A \sqcup B$, where all weights are positive. Let $a = |A|$ and $b = |B|$. If all vertices in $A$ have equal weighted degree and all vertices in $B$ have equal weighted degree, then the number of edges in $G$ is at least $a+b-\gcd(a,b)$. Proof- Let $G$ be a weighted bipartite graph with bipartition $A \sqcup B,$ where all weights are positive. Let $a = |A|$ and $b = |B|$. Let $d_A$ be the weighted degree of each vertex in $A$ and $d_B$ be the weighted degree of each vertex in $B$. Consider the action of the cyclic group $C_a$ on the vertices of $A$ by rotation, and the action of the cyclic group $C_b$ on the vertices of $B$ by rotation. Since all vertices in $A$ have equal weighted degree, the action of $C_a$ on the vertices of $A$ preserves the weighted degrees. Similarly, the action of $C_b$ on the vertices of $B$ preserves the weighted degrees. By the Orbit-Stabilizer Theorem, the number of edges incident to each vertex in $A$ is equal to the number of orbits of the action of the stabilizer of a vertex in $A$ on the vertices of $B$. Similarly, the number of edges incident to each vertex in $B$ is equal to the number of orbits of the action of the stabilizer of a vertex in $B$ on the vertices of $A$. Since the actions of $C_a$ and $C_b$ are transitive, the stabilizer of a vertex in $A$ is a subgroup of $C_a$ of order $d_A$, and the stabilizer of a vertex in $B$ is a subgroup of $C_b$ of order $d_B$ $\text{ Sylow Theorems},$ number of orbits of the action of a subgroup of order $d_A$ on a set of size $b$ is at least $b-\gcd(b,d_A)$. Similarly, the number of orbits of the action of a subgroup of order $d_B$ on a set of size $a$ is at least $a-\gcd(a,d_B)$ Therefore $,$ the number of edges incident to each vertex in $A$ is at least $b-\gcd(b,d_A)$, and the number of edges incident to each vertex in $B$ is at least $a-\gcd(a,d_B)$ Since $,$ the sum of the weighted degrees on both sides must be equal, we have $ad_A =\frac{ b}{d_B}$. Therefore, $d_A = \frac{b}{d_B},$ and $d_B = \frac{a}{d_A}.$ Substituting these expressions into the bounds number of edges incident to each vertex in $A$ is at least $b-\gcd\left(b,\frac{b}{d_B}\right) = b-\frac{\gcd(b,a)}{d_B}$ and number of edges incident to each vertex in $B$ is at least $a-\gcd(a,\frac{a}{d_A}) = a-\frac{\gcd(a,b)}{d_A}$ Summing these bounds over all vertices $\implies$ total number of edges is at least $ab-\gcd(a,b)(\frac{a}{d_A}+\frac{b}{d_B})$ Since $\frac{a}{d_A} =\frac{ b}{d_B},$ we have $\frac{a}{d_A}+\frac{b}{d_B} =\frac{ (a+b)}{d_A} =\frac{ (a+b)}{d_B}.$ Therefore, the total number of edges is at least $ab-\frac{\gcd(a,b)(a+b)}{d_A }= ab-\frac{\gcd(a,b)(a+b)}{d_B}$. Simplifying this expression $,$ total number of edges is at least $a+b-\gcd(a,b)\,\blacksquare$ Footnoote Key insight is to use the actions of the cyclic groups $C_a$ and $C_b$ to relate the weighted degrees to the number of orbits of the stabilizers. $\text{Sylow's 3rd theorem states}$ Consider $G$ be a finite group and $P$ is a Sylow $p$-subgroup of $G,$ then the number of Sylow $p$-subgroups of $G$ is congruent to $1$ modulo $p$. $\text{ Sylow's 3rd Theorem}$ to bound the number of orbits of the action of a subgroup of order $d_A$ on a set of size $b$. Let $G$ be the symmetric group on $b$ elements, and let $P$ be a Sylow $p$-subgroup of $G$, where $p$ is a prime number dividing $d_A$ $(\bullet)$ By Sylow's Third Theorem, the number of Sylow $p$-subgroups of $G$ is congruent to $1$ modulo $p$. Since $P$ is a Sylow $p$-subgroup of $G$, it has order $p^k$ for some integer $k$. The number of orbits of the action of $P$ on a set of size $b$ is equal to the number of cosets of $P$ in $G$, which is equal to $\frac{|G|}{|P| }=\frac{ b}{p^k}$. Since the number of Sylow $p$-subgroups of $G$ is congruent to $1$ modulo $p$, the number of orbits of the action of $P$ on a set of size $b$ is at least $b-\gcd(b,p^k) = b-\gcd(b,d_A)$ This bound is applied in the proof of the lemma to explain that the number of edges incident to each vertex in $A$ is at least $b-\gcd(b,d_A)$ Similarly, the number of orbits of the action of a subgroup of order $d_B$ on a set of size $a$ is at least $a-\gcd(a,d_B)$ Let $G$ be the group of permutations of the vertices in $B$, and let $H$ be the stabilizer of a vertex $v$ in $B$. Then $H$ is a subgroup of $G$ that fixes $v$. The Orbit-Stabilizer Theorem states that the size of the orbit of $v$ under the action of $G$ is equal to the index of $H$ in $G$, denoted by $|G:H|$ $$|\mathrm{Orb}(v)| = |G:H| = \frac{|G|}{|H|}$$ Consider $d_A$ be the weighted degree of each vertex in $A$, and let $d_B$ be the weighted degree of each vertex in $B$. We want to show that the number of edges incident to each vertex in $A$ is at least $b-\gcd(b,d_A)$. Consider the action of the group $G$ on the vertices in $B$. Let $v$ be a vertex in $B$, and let $H$ be its stabilizer in $G$. Then $H$ is a subgroup of $G$ that fixes $v$. Size of the orbit of $v$ under the action of $G$ is equal to the index of $H$ in $G$. Since $H$ fixes $v$, the orbit of $v$ is precisely the set of vertices in $B$ that are adjacent to $v$. Therefore, the number of edges incident to $v$ is equal to the size of the orbit of $v$, which is equal to the index of $H$ in $G$. Since $H$ is a subgroup of $G$ of order $d_B$, we have: $$|\mathrm{Orb}(v)| = |G:H| = \frac{|G|}{|H|} = \frac{b}{d_B}$$Since this is true for every vertex $v$ in $B$, the total number of edges incident to all vertices in $B$ is at least $b(\frac{d_B}{d_B}) = b$. Consider the action of the group $G$ on the vertices in $A$. Let $u$ be a vertex in $A$, and let $K$ be its stabilizer in $G$. Then $K$ is a subgroup of $G$ that fixes $u$. By the Orbit-Stabilizer Theorem, the size of the orbit of $u$ under the action of $G$ is equal to the index of $K$ in $G$. Since $K$ fixes $u$, the orbit of $u$ is precisely the set of vertices in $A$ that are adjacent to $u$. Therefore, the number of edges incident to $u$ is equal to the size of the orbit of $u$, which is equal to the index of $K$ in $G$. Since $K$ is a subgroup of $G$ of order $d_A,$ $$|\mathrm{Orb}(u)| = |G:K| = \frac{|G|}{|K|} = \frac{a}{d_A}$$ Since this is true for every vertex $u$ in $A$, the total number of edges incident to all vertices in $A$ is at least $a(\frac{d_A}{d_A}) = a$. Total number of edges is at least $a+b\implies\, |E| \ge a+b \ge b-\gcd(b,d_A) + a-\gcd(a,d_B)$

The answer is $m+n - \gcd(m,n)$ attained by breaking the grid into $\gcd (m,n) \times \gcd(m,n)$ Latin squares. An example for $(6,9)$ is shown below: [asy][asy] unitsize(0.6cm); int fillgrid(int startx, int endx, int starty, int endy, pen fillcolor, pen edgecolor) { fill((startx,starty)--(startx,endy)--(endx,endy)--(endx,starty)--cycle, fillcolor); for(int i = startx+1; i < endx; ++i) { draw((i,starty)--(i,endy), edgecolor); } for(int i = starty+1; i < endy; ++i) { draw((startx,i)--(endx,i), edgecolor); } return 0; } int[][] grid = {{6,4,5,9,7,8,12,10,11}, {5,6,4,8,9,7,11,12,10}, {4,5,6,7,6,9,10,11,12}, {3,1,2,6,4,5,9,7,8}, {2,3,1,5,6,4,8,9,7}, {1,2,3,4,5,6,7,8,9}}; int height = grid.length; int width = grid[0].length; fillgrid(0,3,0,3, paleblue,lightblue); fillgrid(3,6,0,3, palegreen, green); fillgrid(6,9,0,3, paleyellow, lightolive); fillgrid(0,3,3,6, palegreen, green); fillgrid(3,6,3,6, paleyellow, lightolive); fillgrid(6,9,3,6, palered, lightred); int diff; for(int x = 0; x < width; ++x) { for(int y = 0; y < height; ++y) { label((string)grid[height-y-1][x], (x+0.5,y+0.5), fontsize(8)); } } draw((0,0)--(width,0)--(width,height)--(0, height)--cycle, linewidth(2)); [/asy][/asy] Now we prove the bound. If there is not a $1$ in the grid, decrease every number by the same amount until there is. Now that there is a $1$ in the grid, the largest number in its column is $m$ – therefore, the smallest number in each row is at most $m$. Similarly, the smallest number in each column is at most $n$. Let $a_k$ denote the number of rows whose smallest element is $k$, for $1 \leq k \leq m$. Let $b_k$ denote the number of columns whose smallest element is $k$, for $1 \leq k \leq n$. Let $g_k$ denote the number of instances of $k$ in the grid. We have the following equations: \begin{align*} b_1 &= g_1 = a_1 \\ b_2 + b_1 &= g_2 = a_2 + a_1 \\ \vdots ~ ~ ~ & ~ ~ ~ \vdots \vdots \vdots \qquad ~ ~ \vdots \\ b_m + \dots + b_1 &= g_m = a_m + \dots + a_1 \\ b_{m+1} + \dots + b_2 &= g_{m+1} = a_m + \dots + a_1 \\ \vdots ~ ~ ~ & ~ ~ ~ \vdots \vdots \vdots \qquad ~ ~ \vdots \\ b_n + \dots + b_{n-m+1} &= g_n = a_m + \dots + a_1 \\ b_n + \dots + b_{n-m+2} &= g_{n+1} = a_m + \dots + a_2 \\ \vdots ~ ~ ~ & ~ ~ ~ \vdots \vdots \vdots \qquad ~ ~ \vdots \\ b_n &= g_{m+n-1} = a_m. \end{align*}Subtracting adjacent pairs of equations gives us $b_1 = a_1$, $b_2 = a_2$, and so on. In particular, define $c_k = a_k$ for $1 \leq k \leq m$ and $c_k = b_{k-m}$ for $m+1 \leq k \leq m+n$ – take all other indices modulo $m+n$. Then, by subtracting adjacent pairs of equations above, we precisely get \[c_k = c_{k+m}\]for all integers $k$. This means that $c_1, c_2, \dots, c_{\gcd(m,n)}$ determine the whole sequence, and in particular, \[a_{m-\gcd(m,n)+1} = c_{m - \gcd(m,n) + 1} = c_1 = a_1 \geq 1,\]so some row has a smallest element of $m-\gcd(m,n)+1$. This same row contains $m+n - \gcd(m,n)$, as desired.