Hi

As you've seen, it's easy to check that divides when

Now, to prove that for any in we have to assume that for some integer divides and then prove that divides

We can write:

Hence

An integer is divided by iff it is divided by and and a prime divides a product iff it divides at least a factor.

If and divide or then they divide

If divides it also divides and then divides

If divides it also divides and then divides

Therefore

Of course, writing gives an immediate but non inductive proof.

Another proof by induction (maybe more comon, try to do it) consists in, when you assume that divides develop and you find something which is a sum of and an integer If you show that is divided by then divides , and you can end your proof.