Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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)

reading from left-to-right and top-to-bottom.

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.$$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.