multiply fraction with what number to get a whole number?

Question

I'm solving some programming puzzle and it has come down to this:

I've a fraction, say 12/13, and I need to multiply it with a smallest possible natural number (say x) to get a whole number. How do I solve for x?

I intuitively feel I need to use LCM to solve this but haven't been able to pin down on a method.

Answer 1

If the fraction is allready reduce ($\implies gcd(num;den)=1$) the smallest $x$ is denominator.

Or to reduce the fraction you have to divide both num and den by $gcd(num;den)$ so the new denominator is $den/gcd(num;den)$.

So the smallest $x$ is $den/gcd(num;den)$.

Answer 2

Hint $\,\ c \dfrac{a}b\in\Bbb Z\iff b\mid ac\iff b\mid ac,bc\iff b\mid(ac,bc)= (a,b)c\iff b/(a,b)\mid c$