# Finding the greatest common factor that matches some constraints

Is there a set of $n$ sets that has all of the following:

1) Inside each set, there are $n$ different numbers, and the multiplication of any two numbers in the set will produce some multiples of $x$.

2) However, when a number in one set is multiplied with another number in a different set, they no longer form a number that is multiples of $x$.

also does such set exists for all $n$ bigger than 2?

if so, what is a way to find out such set?

-

Curiously, 3x3 families can be constructed using Latin squares of order 3. For example:

1 2 3
2 3 1
3 1 2


and we change the notation to

1 -> 011
2 -> 101
3 -> 110


So the above Latin squares gives

(011 101 110)  (101 110 011)  (110 011 101)    (1)


We pair these up with:

(111 111 000)  (111 000 111)  (000 111 111)    (2)
(110 110 110)  (101 101 101)  (011 011 011)    (3)


Now pick 9 distinct primes $p_1,p_2,\ldots,p_9$ (any primes will do, so we're getting an infinite family of families). The i-th bit of the k-th number in (1), (2) and (3) determines the power of the prime $p_i$ using in the k-th number in our family.

We define:

\begin{align} a_1 &:= (p_1)^0,(p_2)^1,(p_3)^1,(p_4)^1,(p_5)^0,(p_6)^1,(p_7)^1,(p_8)^1,(p_9)^0 \\ a_2 &:= (p_1)^1,(p_2)^0,(p_3)^1,(p_4)^1,(p_5)^1,(p_6)^0,(p_7)^0,(p_8)^1,(p_9)^1 \\ a_3 &:= (p_1)^1,(p_2)^1,(p_3)^0,(p_4)^0,(p_5)^1,(p_6)^1,(p_7)^1,(p_8)^0,(p_9)^1 \\ b_1 &:= (p_1)^1,(p_2)^1,(p_3)^1,(p_4)^1,(p_5)^1,(p_6)^1,(p_7)^0,(p_8)^0,(p_9)^0 \\ b_2 &:= (p_1)^1,(p_2)^1,(p_3)^1,(p_4)^0,(p_5)^0,(p_6)^0,(p_7)^1,(p_8)^1,(p_9)^1 \\ b_3 &:= (p_1)^0,(p_2)^0,(p_3)^0,(p_4)^1,(p_5)^1,(p_6)^1,(p_7)^1,(p_8)^1,(p_9)^1 \\ c_1 &:= (p_1)^1,(p_2)^1,(p_3)^0,(p_4)^1,(p_5)^1,(p_6)^0,(p_7)^1,(p_8)^1,(p_9)^0 \\ c_2 &:= (p_1)^1,(p_2)^0,(p_3)^1,(p_4)^1,(p_5)^0,(p_6)^1,(p_7)^1,(p_8)^0,(p_9)^1 \\ c_3 &:= (p_1)^0,(p_2)^1,(p_3)^1,(p_4)^0,(p_5)^1,(p_6)^1,(p_7)^0,(p_8)^1,(p_9)^1 \\ \end{align} and the family is $$\{\{a_1,a_2,a_3\},\{b_1,b_2,b_3\},\{c_1,c_2,c_3\}\}$$ and $$x=\prod_{i=1}^9 p_i.$$

The smallest family that can be constructed by this Latin square construction is thus $$\{\{440895, 43890, 43758\},\{30030, 29070, 969969\},\{149226, 46410, 122265\}\}$$ where $$x=223092870.$$

The Latin square property ensures that there will be two coinciding zeroes in the "cross products" (which, when this occurs, implies a $(p_i)^0$ factor).

This construction will generalise to mutually orthogonal Latin squares (assuming the first column is identical in each Latin square). There will need to exist a family of $n-2$ mutually orthogonal Latin squares, which exist at least for infinitely many values of $n$.

(This also works for $n=2$, but a set of $n-2$ mutually orthogonal Latin squares is rather trivial. [ronno's earlier construction is an example of this case.])

Here's an example with $n=4$ constructed using a pair of orthogonal Latin squares of order $4$: \begin{align} \{ & \{7420738134810, 42597478693770, 705561031353570, 155186468939000213\},\\ & \{124952201298210, 263144725077234, 670103807644810, 1570864671608505\},\\ & \{230326723800030, 567883989007790, 762890549117235, 346859224918206\},\\ & \{317506244845530, 524202713204170, 629207214681045, 330502088912226\}\} \end{align} where $$x=32589158477190044730.$$

-

$\{\{6,35\},\{10,21\}\}$ with $x= 210$ seems to work.

-