Calculating a Least Common Multiple with shifts

85 Views Asked by At

I'm writing a program where one part of it has to calculate a LCM with "shifted" values.

The idea behind it is quite hard to describe for me, so I'll give you an imaginative representation of it:

Imagine we have got two sets of bricks: one of 20cm height white bricks and another with 30cm height black bricks. We are building two "towers" out of each set until we got two towers of the same height. The question is: how tall will be each of towers?

Of course the answer is: $lcm(20,30) = 60$

Now the twist

Imagine one of those towers doesn't sit on the ground level, but it is positioned on a foundation that raises it by 5cm up. Now, because the towers are not of the same height, we start adding bricks again until they will be again of the same height.

The (real) question is: how much bricks we need NOW?

1

There are 1 best solutions below

5
On

If one tower is shifted by $5$ cm, then the towers will never be of the same height,

no matter how many bricks you add.

The towers will be of height $5+20n$ and $30m$ (or $20n$ and $5+30m$),

where $n$ and $m$ are whole numbers,

and these will never be equal, because $10$ divides $30m$ (or $20n$) but not $5+20n$ (or $5+30m$).