# What is the smallest $k$ such that two disjoint sets remain unequal when elements are considered modulo $k$?

Let $X$ be a finite set of positive integers. Define $X$ mod $k$ as multiset of positive integers obtained by mod operation on every element of $X$. For example, $\{3, 5, 8\} \bmod 3 = \{0, 2, 2\}$. Two multisets are equal iff they have the same elements with identical frequency.

Let $A$ and B be two subsets of $\{1, 2, 3, ..., n - 1, n\}$ such that $|A| = |B| = m$, $A \cap B = \emptyset$. What is the minimum $k$ (as a function of $n$ and $m$) such that the multisets $A \bmod k \neq B \bmod k$. Consider for example $A = \{2, 4, 11, 15\}$ and $B = \{6, 8, 13, 17\}$ for which $A \bmod i = B \bmod i$, for $i = 2, 3$ but $A \bmod 4 \neq B \bmod 4$.

-
I think $k$ is a function of $A$ $B$, but does not only depend on $m$ and $n$. For example (with $n = 4$ and $m = 2$) if $A = \{1,3\}$ and $B = \{2,4\}$ then $k = 2$. But if $A = \{1,2\}$ and $B = \{3,4\}$, then $k = 3$. –  Joel Cohen May 27 '12 at 14:58
@JoelCohen: I guess that just proves that $k \geq 3$; I believe what the OP wants is a bound that would work for every pair of sets. OP, could you confirm that? –  Najib Idrissi May 27 '12 at 16:05
@N.I For $n\gt m=2$, the value then is $k=n$: if $1\lt k\lt n-1$, then $A=\{1,2\}$, $B=\{1,k+2\}$ are equal modulo $k$. And $A=\{1,2\}$ $B=\{2,n\}$ have $A\bmod n-1 = B\bmod n-1$. –  Arturo Magidin May 27 '12 at 17:50
@N.I.: Yes, I am looking for a bound that works for every disjoint pair with the same number of elements. –  K MathCS May 28 '12 at 0:42
@ArturoMagidin: Please note that the sets should be disjoint. Your examples do not satisfy the criterion. –  K MathCS May 28 '12 at 0:45

From the comments, I understand OP is interested in the case where each set has just one element, and we want the smallest $k$ such that for all $p,q$, $p$ and $q$ are incongruent modulo $k$. But that's easy: if $1\le p\lt q\le n$, then $p$ and $q$ are not congruent modulo $n$, and if $k\lt n$, then we can take $p=1$, $q=k+1$, getting $p$ and $q$ congruent modulo $k$. So in the $m=1$ case, the smallest $k$ is $n$. So perhaps the question has not been stated to reflect exactly what OP wants.
EDIT: I gather from the comment that OP has clarified (in a darker mood, I might say, shifted the goalposts again) and wants the maximum over all pairs $p,q$ (with $1\le p\lt q\le n$) of the minimum $k$ such that $p$ and $q$ are incongruent modulo $k$. The conjecture that $k=O(\log n)$ is correct. If $p$ and $q$ are congruent modulo $r$ for $r=1,2,3,\dots,s$ then they are congruent modulo the least common multiple $M$ of the numbers $1,2,3,\dots,s$, which means they differ by at least $M$, which means $n\ge M$. Now it is known that $M$ is asymptotically $e^s$ (see any text on analytic number theory), so $\log M=s+o(1)$. This gives what you want (for the case $m=1$).
For $p = 1$, $q = x$, if $x$ is even, $k = 2$. In the worst case, $k = O(log~ x)$. This is perhaps true in general too i.e. given two positive integers $p$ and $q$, where $1 \leq p \leq q \leq n$ there always exist a $k = O(log~ n)$ such that $p \not\equiv q ~mod~ k$. I do not have a proof. –  K MathCS May 28 '12 at 15:35
GerryMyerson: My apologies for the confusion. Thank you for giving proof for $m = 1$ case. Now for $m > 1$, does $k$ still remains $O(log~n)$. In this case, I am unable to conjecture any bound on $k$. –  K MathCS May 29 '12 at 2:27
Good question. For $m=1$, $n=2521$, we need $k=11$ to distinguish between 1 and 2521. But for $m=2$ and the much smaller $n=143$ we still need $k=11$ to distinguish between $\{{1,143\}}$ and $\{{71,73\}}$. I'd recommend doing small examples and looking for patterns. –  Gerry Myerson May 29 '12 at 3:16