1
$\begingroup$

Possible Duplicate:
HCF/LCM problem

Given some positive integers $a_i, a_{i+1},\dots,a_n$ we need to find as large as possible number $X$ such that $a_i \pmod x = a_{i+1} \pmod x = \dots = a_n \pmod x$

I figured out that $X$ will not be greater than smallest number of out numbers. More, if we have two numbers $a$ and $b$, $a

I'm sure I'm missing some facts here. Any help appreciated.

Cheers,

  • 0
    I'm pretty sure someone asked just this question about a week ago.2012-07-10
  • 0
    Can't find it, so I'll just post the hint I recall here, someone can post it as community wiki if the duplicate is not found: look at the gcd of $a_i-a_j$ over all $i,j$.2012-07-10
  • 2
    This is a duplicate of this [recent question.](http://math.stackexchange.com/q/166330/242) Your answer is there.2012-07-10
  • 0
    *"I figured out that $X$ will not be greater than smallest number of out numbers."* <- Is this an extra condition on $X$, or is it your own attempt at a conclusion? In other words, would you accept $X=3$, when $a_1=2$, $a_2=5$ and $a_3=8$? If yes, then your question is more or less fully answered in the link that Bill gave. Otherwise look at André's answer.2012-07-10
  • 0
    @Jyrki Huh? As my hint shows, the solutions are the divisors of said gcd. Obviously if one seeks solutions in some interval then one simply restricts to divisors in that interval. What more do you think needs to be said?2012-07-10
  • 0
    @Bill: My point was that the congruences alone don't force $x$ to be smaller than all the $a_i$:s. I was uncertain as to whether the actual question ends after line two, and the next paragraph is about Chris describing his own thinking so far (the recommended practice here). Or whether alternatively the problem description still goes on, and the second paragraph gives another constraint for $x$ to satisfy.2012-07-10
  • 0
    @Jyrki Yes, of course. But I have no clue why you think Andre's answer does something that mine does not. To me, any needed restriction of the divisors to any sought interval - if desired - is so trivial that it needn't be mentioned in a hint. Is that the reason behind your bifurcated reference, or is there something more to it? I'm guessing the latter, since I don't think you'd do that for the former trivial reason. I'm curious what I might be overlooking (if anything).2012-07-10
  • 0
    @Bill: I read your first comment (the one with the reference to the earlier question) as implying that you prefer the discussion to take place there. Given that I expected this question to get closed a lot sooner. I forgot that as a moderator you cannot cast the first close vote, because it would also be the last. I wasn't trying to give a preference to André's answer over yours. And your answer to the other question has my +1. It is also barely possible that I had last updated my browser before your answer appeared here. I don't remember for sure. Sorry about the fuss.2012-07-10
  • 0
    @Jryki Ah, I see. I just wanted to be sure I wasn't overlooking some important but subtle point you were making. Apologies for the bother.2012-07-10

2 Answers 2

0

The question has been largely answered in the previous post referred to in Bill Dubuque's comment.

To adapt that answer to your particular situation, suppose that $a_1\lt a_2\lt \cdots \lt a_n$. Let $d$ be the gcd of the numbers $a_i-a_1$. Then $x$ must be a divisor of $d$. To meet the size condition, we pick the largest divisor of $d$ which is $\le a_1$.

Even when $n=2$, this may be computationally difficult. For example, let $M$ be a hard to factor product of two huge primes, and let $a_1=M-1$, $a_2=2M-1$.

0

Hint $\ \ \ \begin{eqnarray}\rm mod\ m\!:\ a_1\equiv a_2\equiv \ldots\equiv a_n &\iff&\rm m\:|\:a_1-a_2,\ \ldots,\ a_{n-1}-a_n \\ &\iff&\rm m\:|\:gcd(a_1\!-\!a_2,\ldots,a_{n-1}\!-\!a_n)\end{eqnarray}$

Remark $\ $ This is a special constant case $\rm\,m_i = m\,$ of the Chinese Remainder solvability criterion

$$\rm there\ exists\ \ x \equiv a_i\ \, (mod\ m_i) \iff a_i \equiv a_j\,\ (mod\ gcd(m_i,m_j))\ \ for\ all\ i,j $$