During the contest I simply guessed that lcm worked and I couldn't come up with a counter test case so I went with it