Question

HELP !! Division Algorithm applications
http://prntscr.com/3xh7kg

Answer 1

since \(b\) is positive, \(|a|b \ge |a|\)

so \(a - (-|a|-2)b = a + |a|b + 2b \ge a + |a| +2b \ge 2b\)

Answer 2

that means the set \(S = \{a-xb | \text{ x is an integer; }a-xb\ge 2b\}\) is nonempty

Answer 3

say the smallest integer in the set is \(\large r\)
thus \(\large r = a - qb \ge 2b\)

Answer 4

we need to prove that \( r < 3b\) - but isn't that just wrong as we can make \(r\) to take any value by choosing an appropriate value for \(q\) ?

Answer 5

@ikram002p need your help

Answer 6

Perhaps this will help:
https://proofwiki.org/wiki/Division_Algorithm#Uniqueness

Answer 7

yes hero this is exactly the proof im looking for... i can modify it for 2b<=r<3b thank you xD

Answer 8

hehe lolz i like that prove xD
sry i was not online at that time :-\

Answer 9

still u wanna prove the uniqueness or you have something else ?

Answer 10

@ganeshie8

Answer 11

yes i would like to work it again - more practice xD

Answer 12

lets do the bounds also for completeness sake...

Answer 13

well ok lol i like to start proof like this:-
for
\(a=qb+r\) \(0\le r <b\)
show :-
1- Existence
2-Uniqueness
then

\(0\le r <b\) + 2b

\(2b\le r <3b\)

Answer 14

its enough to show for \( 0\le r <b\)
Existence of p,q and Uniqueness of them
ok ?

Answer 15

Alright, so we're going to prove \(0 \le r \lt b\) first is it ?

Answer 16

yeah , ic .. u started good with W-OP

Answer 17

but mm make it for a-xb>=0

Answer 18

Before we starte - the question that troubled me last night was this :
how can we say r < b or r<3b, when r can take on any integer value

Answer 19

well remember mod :-
a=qp+r

a mod p= r mod p
a mod q= r mod q

Answer 20

i had thought i figured it out yesterday, but i have lost it again o.o

Answer 21

yes

Answer 22

so in mod we make sure that r take the least value right ? because it's the remainder

Answer 23

yeah that part is clear.
in the proof, they say r cannot be greater than b, how do they say that ?

Answer 24

but anderstanding the remainder and D.A will help you to understand the mod xD
so ill show it to you

Answer 25

well , r is bounded in you Qn
it gives
0<=r<b right ?
simply if you make long division
like this :- you will keep doing it untill you gor r <p

Answer 26

and if youreached r=b , then u devide again to get r=0

Answer 27

yes true, if you have r > b, you can always subtract b from it and make r < b

Answer 28

thats right ^_^

Answer 29

how does this fit with the highlighted line in the proof

Answer 30

the proof assumed r =a-qb as the smallest nonegative

assume r >b
then r-b < a-qb

Answer 31

since r >b we make sure that r-b is possitive
so
r=a-qb
r-b=a-(q+1) b < 1- qb

Answer 32

typo
r-b=a-(q+1) b < a- qb

Answer 33

Assume \(r\) is the smallest element in \(S\),
since \(r \in S\), \(r\) must be of form \(r = a-qb\)

Answer 34

what next ?

Answer 35

what proof you wanna follow xD

Answer 36

your's

Answer 37

then first we define S
\(S = \{a-xb | \text{ x is an integer; }a-xb\ge 0\}\)

Answer 38

okay

Answer 39

By WOP, this set with non-negative integers must contain a smallest integer, say \(r\)

Answer 40

ovc its nonempty sit , be carfull before using WOD , is it clear to you that \(0\le\) r ?
from the definition of S ?

Answer 41

that what u set up in the first line

Answer 42

so after having r ( from WOP)
r=a-qb \(0\le r\) ok till nw ?

Answer 43

oh okay i have skipped a line :
\(a - (-|a|)b = a + |a|b \ge a + |a| \ge 0 \)

so the set has atleast one element - so its nonempty

Answer 44

yeah :D

Answer 45

yes, all peace till now :)

Answer 46

good :D
now assume r >b

Answer 47

wait no we have r<b is the qn right , then lets assume r>=b

Answer 48

k following

Answer 49

yes assume r>= b, then r-b is non negative

Answer 50

r= a-qb from WOP assumption right ?

Answer 51

r= a-qb is the smallest element in S from WOP *

Answer 52

r= a-qb sub b from both side
r-b=a-qb-b

Answer 53

then
r-b = a-(q+1)b

Answer 54

\(r = a-qb\)
\(\implies r-b = a-qb-b = a-(q+1)b \in S\)

Answer 55

but
since
-(q+1) < -q
-(q+1)b< -qb
a-(q+1)b< a-qb
r-b <r wich is a contradiction to WOP

Answer 56

lol yeah :D

Answer 57

makes perfect sense xD

Answer 58

yeah hehe

Answer 59

now for Uniqueness ?

Answer 60

so that concludes the bounds part :
we can always bound the value of \(r\) within \(0\le r \lt b\) in the division \(\dfrac{a}{b}\)

Answer 61

that proved that there exist r , q s.t
r=a-qb or a=qb+r \(0\le r < b\)

Answer 62

now we need to show there is only r, q

Answer 63

yes

Answer 64

so lets assume r,q not unique
then there exist at least 2 of r and 2 of q xD
lets say
\((r_0,q_0) , (r_1,q_1)\)

Answer 65

then
\(a=q_0b+r_0\)
\(a=q_1b+r_1\)

Answer 66

okay

\(r_0 - r_1 = b(q_1-q_0)\)

Answer 67

\( r_0 - r_1 =b (q_1 -q_0)\)
\(-b\le r_0-r_1 <b\)

Answer 68

so
\(|r_0-r_1| <b\)
thus
\(b|q_0-q_1| <b\)
which yeild
\(0\le |q_0-q_1| <1\)

Answer 69

which is impossible, nice :) i think i luv DA more now xD thank you !!

Answer 70

haha np , will that is not impossible :P

Answer 71

that leave you with one case wich is
\( |q_0-q_1| =0\)

Answer 72

thats impossible since \(|q_0 - q_1|\) cannot be a fraction right ?

Answer 73

ahh okay

Answer 74

wait but it can be 0

Answer 75

otherwise ur right since its integer

Answer 76

which yields \(q_0 = q_1\) got you :)

Answer 77

:D

Answer 78

a=qb+r
let q=t+2
then
a=(t+2)b+r
a=tb+(2b+r)

we know this new remainder is between 2b and 3b since r is between 0 and b

i don't know if this helps
i was doing lots of examples with given numbers for a and b and seen r was between 2b and 3b for whenever I chose the q=t+2

Answer 79

Ohh yes, thats working perfectly :

a = qb+r

a = qb+r + 2b-2b
= b(q-2) + `r+2b`

Answer 80

since 0<=r<b,
2b<=r+2b<3b

xD