1
$\begingroup$

Given a set of numbers, say $x=\{1,2,3\}$, how can I find the maximum $m$ such that $x_i\bmod m =x_j\bmod m$, where $i$ and $j$ are some indexes of the set $x$. So for $x=\{1,2,3\}$, the answer should be $1$ and for $x=\{5,2,8\}$, the answer should be $3$. I know that this won't work when say we have a set of $\{1,1,1\}$, but I am interested to knowing when it will work and how we can find the maximum $m$. Also, I am interested to know if there are any other cases where this doesn't follow.

One of the thoughts I had was to do this: $\left(\frac{x_i}{x_j}\right)\bmod b\equiv 1$, but I'm not sure if this leads anywhere.

$\endgroup$
3
  • $\begingroup$ @peterwhy No, $i$ could equal $j$ $\endgroup$
    – user335937
    Commented Apr 30, 2016 at 18:32
  • $\begingroup$ I would like some clarification. Which of the following is this question about: $$\exists i,\exists j, x_i\bmod m = x_j\bmod m\\ \forall i,\exists j, x_i\bmod m = x_j\bmod m\\ \forall i,\forall j, x_i\bmod m = x_j\bmod m\\ $$ $\endgroup$
    – peterwhy
    Commented Apr 30, 2016 at 18:36
  • $\begingroup$ @peterwhy The question is about for all i and j that are valid, we need to find a maximum $m$ such that $x_i\bmod m = x_j\bmod m$. Does that answer your question? $\endgroup$
    – user335937
    Commented Apr 30, 2016 at 18:38

3 Answers 3

1
$\begingroup$

Assuming all the $x_i \in \Bbb{Z}^+$:

Simply take $m = \sup x - \inf x$.

It is easy to prove that there are some $i,j$ such that $x_i \equiv x_ \pmod m$, namely, take $i: \sup x = x_i$ and $j: \inf x = x_j$.

It is easy to show for $k > m$ and $i \neq j$ that $x_i \neq x_j \pmod k$: because if $x_i \equiv x_j \pmod k$ and $x_j > x_i$ then $x_j - x_i \leq m$ and $$ x_i -x_i \equiv x_j-x_i \pmod k \\ x_j-x_i \equiv 0 \pmod k \\ x_j - x_i = nk (n>0) \\ nk \leq m $$ but $m<k$ so that is impossible.

the other answers proposed are answering a different question: THey assume you meant that for all pairs $i,j$ we have $x_i \equiv x_j \pmod m$ but your question states some pair $i,j$/

$\endgroup$
2
  • $\begingroup$ how do you find $\sup x - \inf x$? This is a new concept for me $\endgroup$
    – user335937
    Commented Apr 30, 2016 at 18:54
  • $\begingroup$ What I get that sup is the maximum of the set and inf is the minimum, but for (5,2,8), 8-2=6 not 3 $\endgroup$
    – user335937
    Commented Apr 30, 2016 at 19:01
1
$\begingroup$

I would use an algorithm like the following:

m=1
While all set elements are different from 0:
if gcd($x_1,x_2,x_3$) > m then m = gcd($x_1,x_2,x_3$)
$x_1=x_1-1, x_2=x_2-1, x_3=x_3-1$

If any of the set elements is 0 then compute the gcd of the non-zero elemets, if it is greater than m then update m otherwise m is your asnwer

$\endgroup$
0
$\begingroup$

Pick any element in the set, say $x_1$. Compute the set of differences: $$y = \{n-x_1\mid n\in x\setminus \{x_1\}\}$$ Then the common divisor of all these numbers satisfy the condition, and the largest one is the GCD.


For example, if $x = \{5,2,8\}$, take $x_1 = 5$, $$y = \{2-5, 8-5\} = \{-3, 3\}$$ And the GCD is $3$.

$\endgroup$
2
  • $\begingroup$ Could you show me an example of how 5,2,8 gives 3? $\endgroup$
    – user335937
    Commented Apr 30, 2016 at 18:43
  • $\begingroup$ @user335937 edited. $\endgroup$
    – peterwhy
    Commented Apr 30, 2016 at 18:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .