# How to solve such congruences? [duplicate]

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,

-

## marked as duplicate by Gerry Myerson, Jyrki Lahtonen♦, Marc van Leeuwen, J. M., t.b.Jul 10 '12 at 16:11

This question was marked as an exact duplicate of an existing question.

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

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

-

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

-