1
$\begingroup$

My first question on math stackexchange.

I have two numbers, $n$ and $m$. Their values will vary but I always know what they are and they're always positive integers (and multiples of 2, but that doesn't make much difference).

I want to find the smallest number both $n$ and $m$ will perfectly divide into.

E.g.$\begin{align*}n&=32\\m&=144\end{align*}$

Smallest number they will both divide into is $288$.

I can see how to work this out iteratively ($n*m$, then keep dividing by 2 until you find the first number they both won't divide into, the previous value is the desired value) but I can't see how to calculate it directly (and I need to).

For those who ae wondering what this is for, it's do with memory allocation on an ARM platform. I want to be cache line aligned and also exclusive reservation granuale aligned. There, that helped ;-)

So if the cache line width is 32 bytes and the ERG is 144 bytes, I want to allocate with alignment on 288 bytes.

What it amounts to is this; $nx - my = 0$

Except that defines many values and I want the smallest value of $nx$ and $my$ where this is true. $\begin{align*} nx &= my\\ \frac{nx}{ my} &= 1\\ \left(\frac{n}{m}\right)\left(\frac{x}{y}\right) &= 1 \end{align*}$ I know $n$ and $m$, so $\frac{n}{m} = c$ $\frac{x}{y}=c$

And I see that somewhere I need to find more information because what I have can't solve the question. I can't see how to quantify my wish for the smallest values into the equation.

  • 2
    You are looking for the "least common multiple". The least common multiple is equal to $mn/d$, where $d$ is the greatest common divisor. The greatest common divisor can be computed using the Euclidean Algorithm.2012-07-07

4 Answers 4

1

The problem you are describing is called least common multiple. I don't think there exists closed form of LCM, since it would give us closed solution of greatest common divisor.

  • 0
    Closed form: http://en.wikipedia.org/wiki/Closed-form_expression. So yes, you need to calculate it iteratively.2012-07-07
1

First, find the greatest common divisor of $m$ and $n$. This can be done using the Euclidean algorithm, which is fast and computationally efficient.

Once you know the greatest common divisor $d$ of $m$ and $n$, we can write $m=dm'$, $n=dn'$, and the least common multiple of $m$ and $n$ is $dm'n'$. So $x=m'$, $y=n'$ and we have $xn-ym=0$. This is the smallest values that works.

0

Call $(p_i)_{i\geqslant1}$ the prime integers and consider two integers $n$ and $m$ whose decompositions into products of prime factors are $n=\prod\limits_{i\geqslant1}p_i^{c_i(n)}$ and $m=\prod\limits_{i\geqslant1}p_i^{c_i(m)}$. Then the greatest common divisor of $n$ and $m$ is $\gcd(n,m)=\prod\limits_{i\geqslant1}p_i^{\min\{c_i(n),c_i(m)\}}$ and the lowest common multiple of $n$ and $m$ (which coincides with your smallest $nx=my$) is $\text{lcm}(n,m)=\prod\limits_{i\geqslant1}p_i^{\max\{c_i(n),c_i(m)\}}$.

0

Hint $\rm\ n\,x = m\ y\iff x/y = m/n\ $ so least $\rm\, x,y\, $ arise from $\rm\,m/n\,$ in least terms $\rm = (m/d)/(n/d)\,$ where $\rm\,d = gcd(m,n).\, $ So the least solution is $\rm\, n\,x = n m/d,\,$ i.e. $\rm\,lcm(n,m) = nm/gcd(n,m).$