UVA 10407 - Simple division

http://uva.onlinejudge.org/external/104/10407.html

Given a list of \(n\) numbers \(2 \leq n \leq 1000\).  You need to return the largest integer which when divided into each of the input integers leaves the same remainder.

Let's call our list of numbers \(x\), the following expression explain the given situation:

$$\\ x_{1} = q_{1}d + r \\ x_{2} = q_{2}d + r \\ ... \\ x_{j} = q_{j}d + r$$

As we can see from the previous expressions all the numbers on the list when we divided them by \(d\) leaves the same remainder \(r\). We are interesting in the largest \(d\) that has that property. To understand this problem it may be useful first to prove the following theorem if \(a \equiv b (mod \,\, d)\) then \(d | (a - b)\):

$$\\ a = q_{1}d + r \\ b = q_{2}d + r \\ a = q_{1}d + (b-q_{2}d) \\ a - b = q_{1}d - q_{2}d \\ a - b = d(q_{1} - q_{2})$$

Because \(a - b\) can be expressed as the product of \(d\) by some integer without any remainder, we conclude that \(d | (a - b)\). Enough math for the day :) let's focus in the task. Knowing this we take an arbitrary integer from our set of numbers and subtract this amount to all the numbers in our list. To obtain our result (\(d\)) we just calculate the greatest common divisor over the whole list.