# UVa 10407

## Summary

An interesting problem in Number Theory.

## Explanation

Let the list of positive integers be ${\displaystyle x_{1},x_{2},...,x_{n},n\geq 2}$. We can rewrite the list as ${\displaystyle x_{1},x_{1}+d_{1},x_{2}+d_{2},...,x_{n-1}+d_{n-1},n\geq 2}$, where ${\displaystyle d_{i}}$ is the difference between ${\displaystyle x_{i+1}}$ and ${\displaystyle x_{i}}$. Let m be a positive integer such that ${\displaystyle 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 ${\displaystyle d_{i}}$ i=1..n-1. Otherwise, suppose that m > ${\displaystyle d_{i}}$ for some i. Let ${\displaystyle x_{i}\equiv r}$ mod m, i.e. ${\displaystyle x_{i}}$ = km + r, r<m. Then ${\displaystyle x_{i+1}=x_{i}+d_{i}=km+r+d_{i}}$. if ${\displaystyle r+d_{i}, then ${\displaystyle x_{i+1}\equiv r+d_{i}}$ mod m. if ${\displaystyle r+d_{i}\geq m}$, then ${\displaystyle x_{i+1}\equiv r+d_{i}-m}$ mod m. Either way, ${\displaystyle x_{i+1}\not \equiv x_{i}}$ mod m.

Another important fact about m is that m has to divide all ${\displaystyle d_{i}}$'s, i=2..n. Because ${\displaystyle x_{i+1}=x_{i}+d_{i}\equiv x_{i}}$ mod m if and only if ${\displaystyle 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 ${\displaystyle d_{i}}$'s, i=2..n.

## Gotchas

• There may be duplicate integers in the input.

## Notes

• In the proof, I am assuming that the integers are positive. But in the problem there may be some negative integers. But it seems that does not hurt the validity of the algorithm. Could anybody prove or disprove it?

## Input

701 1059 1417 2312 0
701 1059 1059 1417 2312 0
14 23 17 32 122 0
14 -22 17 -31 -124 0
0

179
179
3
3