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 and if $a$ divides $b$ without remainder then we can replace those two numbers with just $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