# UVa 10407

## Summary

An interesting problem in Number Theory.

## Explanation

Let the list of positive integers be $x_{1},x_{2},...,x_{n},n\geq 2$ . We can rewrite the list as $x_{1},x_{1}+d_{1},x_{2}+d_{2},...,x_{n-1}+d_{n-1},n\geq 2$ , where $d_{i}$ is the difference between $x_{i+1}$ and $x_{i}$ . Let m be a positive integer such that $x_{1}\equiv x_{2}\equiv ...\equiv x_{n}$ mod m.

Then the first useful fact is that m can not be bigger than any $d_{i}$ i=1..n-1. Otherwise, suppose that m > $d_{i}$ for some i. Let $x_{i}\equiv r$ mod m, i.e. $x_{i}$ = km + r, r<m. Then $x_{i+1}=x_{i}+d_{i}=km+r+d_{i}$ . if $r+d_{i} , then $x_{i+1}\equiv r+d_{i}$ mod m. if $r+d_{i}\geq m$ , then $x_{i+1}\equiv r+d_{i}-m$ mod m. Either way, $x_{i+1}\not \equiv x_{i}$ mod m.

Another important fact about m is that m has to divide all $d_{i}$ 's, i=2..n. Because $x_{i+1}=x_{i}+d_{i}\equiv x_{i}$ mod m if and only if $d_{i}\equiv 0$ mod m. Combining the two facts, we know that the solution of the problem is the greatest common divisor of the $d_{i}$ 's, i=2..n.

## Gotchas

• There may be duplicate integers in the input.