# 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?

Related Calculus and Beyond Homework Help News on Phys.org
BvU
Homework Helper
2019 Award
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 \}.$