1

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<b$ 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,

Community
  • 1
Krzysztof Lewko
  • 2,312
  • I'm pretty sure someone asked just this question about a week ago. – tomasz Jul 10 '12 at 12:49
  • 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$. – tomasz Jul 10 '12 at 12:52
  • 2
    This is a duplicate of this recent question. Your answer is there. – Bill Dubuque Jul 10 '12 at 13:06
  • "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. – Jyrki Lahtonen Jul 10 '12 at 14:23
  • @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? – Bill Dubuque Jul 10 '12 at 15:37
  • @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. – Jyrki Lahtonen Jul 10 '12 at 16:52
  • @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). – Bill Dubuque Jul 10 '12 at 17:05
  • @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. – Jyrki Lahtonen Jul 10 '12 at 17:19
  • @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. – Bill Dubuque Jul 10 '12 at 17:37

2 Answers2

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$.

Community
  • 1
André Nicolas
  • 507,029
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 $$

Bill Dubuque
  • 272,048