My solution during the contest: Suppose the claim is not true. Label the elements of $A,B$ by $a_1,a_2,\cdots,a_{|A|},b_1,b_2,\cdots,b_{|B|}$. Any element of has at least one representation $x=a_ib_j$. It is enough to consider the case that each reprensentation is unique. If $a_ib_j\in S$ and $a_ib_k,a_lb_j\in S$ for $k\neq j,l\neq i$, we are done since $a_ib_j\mid a_ib_k\cdot a_lb_j$. For any $a_ib_j\in S$ there is no $a_ib_k\in S$ with $k\neq j$ or no $a_lb_j\in S$ with $l\neq k$. Colour each element of $S$ red if there is no $a_ib_k\in S$ with $k\neq j$. Colour the rest green. Since $|S|=|A|+|B|-1>(|A|-1)+(|B|-1)$, there are at least $|A|$ red or at least $b$ green elements. W.l.o.g the are at least $|A|$ red elements. This is only possible if the is for each $1\leq i\leq |A|$ exactly $j$ for which $a_ib_j$ is an element of $S$ and each element of $S$ is red. This implies $|A|+|B|-1=|S|=|A|$ contradicting $|B|\geq2$.

It should be combinatorics instead of number theory.

This problem was proposed by Burii.

Let $A = \{a_1, a_2, \ldots, a_n \}$ and $B = \{b_1, b_2, \ldots, b_m \}$. Notice that if $S$ contains three elements of the form $(a_i \cdot x)$, $(y \cdot b_j)$ and $(a_i \cdot b_j)$, then $ a_ib_j \mid (a_i \cdot x) \cdot (y \cdot b_j) $ and problem would be done. Let's prove $S$ always contains $3$ such elements. Elements of $S$ are always in the form $a_i \cdot b_j$, thus $S$ can be represented by the edges of a bipartite graph, where $a_ib_j$ is represented by the edge $a_i - b_j$. If this graph contains chain of $3$ edges say $a_i - b_j$, $b_j - a_k$ and $a_k - b_e$, the problem is solved since $b_j a_k \mid a_kb_e \cdot a_ib_j $. Assume graph does not contain such chain. This graph must not contain any cycles, because cycle would have to be of length at least $4$ and in it would be chain of length $3$, which is impossible. Then this graph consists of multiple trees. The number of trees can be calculated by the well- known formula ((number of vertices) -(number of edges )). But this graph has $n+m$ vertices and $n+m-1$ edges, so in fact this graph is connected tree. A tree of more than $4$ vertices must have a chain of 3 edges, otherwise it is a star type tree, but degree of each edge is limited by $\max(n,m)$, so our graph cannot be star. . This ends proof.