We have the simple identity for . Hence,(a).

Let be the largest power of that divides . So , by(a).

From it follows that and so divides , where does not divide . Euclid's Lemma implies then that must divide .

By the way, the argument works for also.