• Support PF! Buy your school textbooks, materials and every day products Here!

Division Algorithm Proof Help

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

Answers and Replies

  • #2
BvU
Science Advisor
Homework Helper
2019 Award
13,039
3,016
Assume the opposite and show that in that case r > a
 
  • #3
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

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 \}.##
 

Related Threads on Division Algorithm Proof Help

  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
13
Views
967
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
1
Views
2K
Replies
4
Views
2K
Replies
1
Views
2K
Top