Now you’re talking about something different. The proof of the division algorithm is built up from a bunch of other machinery. It relies on the fact that the ring of integers is a Euclidean domain.

Take a course in ring theory if you want to see how all of this machinery gets built up.