What you did is correct save for a typo.

Okay you know that is a common multiple of and . We have (1) by the definition of the remainder.

Now remember the definition of Least Common Multiple. (2) In other words, it is thesmallest positiveinteger such that it is a multiple of both and .

So in our case, if then is positive integer which is a common multiple of and , and in fact smaller (1) than the smallest positive integer satisfying this (2)! This is acontradiction!

Thus it must be -only case remaining- which is indeed a common multiple of and