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$.
 A: 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$). 
