I think you're almost there. Let . This is non-empty (obviously) and so it has a smallest element .

You know by the division algorithm that for some . Evidently then we have that . Now, if then we'd have that and contradicting the minimality of .

Now that I read your post more carefully though, I think you may have misunderstood what you were to prove. You are given that is the smallest such integer...and from this you must prove that

P.S. If you know group theory this is clear since .