POW-1: An “elementary” divisibility problem

[Update: I have decided to pose at least one problem (or perhaps, two problems) a week from now and invite solutions to those problems from the readers. This should be exciting. I am sure all of you would want your names to be listed in the Problem-Solving Hall of Fame page! 8) ]

This post is about getting the readers of this blog to participate! And so, let me pose an elementary divisibility problem and invite solutions from the readers. “Elementary” doesn’t necessarily mean “easy”, by the way. It just means elementary methods can be used to solve the problem. I am particularly looking for elegant solutions, though all kinds of solutions are welcome. Readers with correct solutions will be given credit and their names will be included in the Problem-Solving Hall of Fame page on this blog! So, go ahead, write down your solutions.

Problem: Suppose and are two positive natural numbers such that is divisible by . Prove that .