Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Arturo Magidin Jul 7 '12 at 19:36

4 Answers 4

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.

share|improve this answer
    
When you say closed form - you mean the solution can only be found iteratively? –  user35334 Jul 7 '12 at 19:44
    
Closed form: en.wikipedia.org/wiki/Closed-form_expression. So yes, you need to calculate it iteratively. –  KCiebiera Jul 7 '12 at 19:47

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.

share|improve this answer

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)\}}$.

share|improve this answer

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).$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.