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