# Division Algorithm Proof Help

Member asked to not delete the template in future posts

## Homework Statement

Let a, b be natural numbers then there exists a unique pair (q,r) that are elements of the non-negative integers such that b=aq+r and 0 is less than or equal to r which is less than a

I have a question regarding the existence part of the proof, now if I assumed a is less than b, its clear that there exists a positive integer x such that xa is greater than b. Now, why must q be the least element such that (q+1)a is greater than b?

BvU
Homework Helper
Assume the opposite and show that in that case r > a

berkeman
Ray Vickson
Homework Helper
Dearly Missed

## Homework Statement

Let a, b be natural numbers then there exists a unique pair (q,r) that are elements of the non-negative integers such that b=aq+r and 0 is less than or equal to r which is less than a

I have a question regarding the existence part of the proof, now if I assumed a is less than b, its clear that there exists a positive integer x such that xa is greater than b. Now, why must q be the least element such that (q+1)a is greater than b?

If ##q## is the least element such that ##(q+1)a > b## then for all non-negative integers ##p \leq q## we have ##pa \leq b.## In particular, ##qa \leq b## but ##(q+1) a## is not ##\leq b##. That means that ##b-qa \in \{0,1,\ldots, a-1 \}.##