# $nx - my = 0$, find smallest positive integer values of $nx$ and $my$ where this is true

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.

-
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

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.

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

-

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

-

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

-