# Given a set of numbers $x_1, x_2, \ldots, x_k$, what is the largest number $h$ such that $x_i \bmod{h} = 0$ for all $i$?

I am solving a system of differential equations with respect to length, let's say 0 to $x_{max} = 10$ meters.

Now, I want to choose an integration step such that my step will land on each of the numbers specified in a list. For example, let's say I am integrating from 0 to 10 meters, and the numbers in my list are:

[1 2 3 3.5 5 7.1 10]

In this case, I can see what the answer is: I would need to set the step size to 0.1, since 0.1 will land on ("divide evenly into") all the other numbers, and also 7.1.

I just don't know what you would call this type of operation, or solve it for a more complicated or larger case, with a longer list and stranger numbers. I am just a chemical engineer, and this seems very much like a computer science/number theory question.

I think the way I expressed the problem in the title is correct, but how to solve it, I don't know how.

• In general, the number you're looking for is the $\gcd$ of $x_i$. But when you depart from the natural numbers, it's hard to say. – Ian Coley Oct 8 '13 at 18:38
• I think I have made some headway. The GCD of a set of numbers can be found recursively, e.g. gcd(A,B,C) = gcd(A,gcd(B,C)). However, GCD does not extend simply to fractions. However, I have observed the correct result is obtained by multiply by a sufficiently large number to make the set elements all integers. Then recursively find their gcd. Then divide the result by the large number originally multiplied by. However, this does not extend easily when we encounter a non-stop fraction e.g. 4/7, since you can't multiply that by anything to get an integer. – clustro Oct 8 '13 at 18:44

You have to find the greatest common divisor $\text{GCD}$ of $x_i$-s. $\text{GCD}$ is usually defined on natural numbers $\mathbb{N} = \{1,2,3,4, ...\}$. Those numbers do not have any decimals, but $\text{GCD}$ can be "generalised":

$1.$ Let be $m$ maximal number of decimals in your list.

$2.$ Multiply your numbers by $10^m$.

$3.$ Compute $d = \text{GCD}(10^m\cdot x_1,10^m\cdot x_2, ... , 10^m\cdot x_n)$

$4.$ Compute the biggest step $s = \frac{d}{10^m}$.

As mentioned in a comment above, this method doesn't work for fractions with infinitely many decimals, but I believe you do not have such numbers in your list.

• Wow cool great minds think alike. :D. Yup, that's what seemed to work above! – clustro Oct 8 '13 at 18:47
• Though does anyone know what matlab function returns the maximum number of decimals in a number? darned if I know :/ – clustro Oct 8 '13 at 18:48
• PS: if you have many numbers (with many decimals), maybe it is not worth to compute $\text{GCD}$ of them. You should test how much time does it take ... – Antoine Oct 8 '13 at 19:02