Math problem; need help

[Farmer]

Yeah, so this was on the second assignment in calc 151. This is supposed to be prereq, so dont make fun of me:

Prove the following using Induction:

If a and b are natural numbers, show that there exists two integers, q and r, such that a = bq + r, and that 0 is less than or equal to r is less than b.

 

[coomar]

your not allowed to use contradiction?

 

[Farmer]

Not for this problem.

EDIT: But, if you can solve it via contradiction, please demonstrate.

EDIT: C'mon, I know you guys have taken Calc 1?

 

[fatty4ksu]

What section is it based off of?

 

[TuxDave]

r = a mod b
q = a (the opposite of modulus) b

QED. 😛

 

[Calin]

1 = 1*1 + 0
Let's assume we have a number a, which can be written as a = nr1*b + nr2
Now, for (a+1) we have (a+1) = either nr1*b + (nr2 + 1), either as (a+1) = (nr1 + 1)*b + (nr2 - nr1 + 1)
And a = nr1 * (b+1) + nr2 - nr1, or a = (nr1-1)*(b+1) + nr2 - b - 1
and check for every case that the relation of equality is ok

 

[akubi]

this problem is called the division "algorithm" in number theory and the proof can be found in most introductory number theory texts.

the most common way to prove this is by contradiction & WOP (well ordering principle, which infact is the basis of "proof by induction")

ok here's the basic overview on how it goes...

consider the set of integers a-b*n for all integer n. now consider a subset of this set which contains just the nonnegative integers (you can prove that this subset is nonempty with the given conditions)

because this subset is a nonempty set of nonnegative integers, you can apply the well-ordering principle, which simply states that there exists a smallest element in this set. (it's very obvious by common sense, but yes you can prove that rigorously as well).

ok let me just assign a name to this smallest element... say "r". anyway, for now, we only know that r is nonnegative and that r=a-b*q for some q.

suppose r is greater than or equal to b... then r-b is >= 0... meaning (a-b*q)-b>=0... refactor and that implies a-b*(q+1)>=0.
now, a-b*(q+1)>=0 and being of the form a-b*n means it should be in the subset of nonnegatives mentioned above. however, r=a-b*q > a-b*(q+1) so the assumption that r is the smallest of the set is false. by contradiction, 0<=r<b.

all that's left is to prove that r and q are unique. this is easy, you just say b*q+r = b*s+t (supposing s and t is some other pair that satisfies the condition). refactor to get b(q-s)=(t-r). at this point recall that r and s are both less than b from the condition above and nonnegative, so the difference between the two can't be more than b... but looking at the left side b(q-s), unless b(q-s)=0 that can't happen (remember q and s are integers so the difference betw them can't be fractional). sooooo q-s = 0, thus q=s, and r=t, therefore s and t consist of the same #s.

 

[Farmer]

Calin:

Huh, thats something similar to what I got, I guess.

By induction,

For b = 1;

a = bq+r
a = (1)q+0
a=q

True for b = 1

Inducing a,
Assume a = k, k = bq + r, 0 is less than or equal to r is less than b, is true for some a E N
Need to Show: a+1 = k+1 = bq + r for some b, q, r following the above parameters
(a + 1) = bq + (r + 1), where (r+1) is, say, r'
Satisfies original equation iff (2 Cases):
Case 1: If 0 is less than or equal to r+1 (r') is less than b, QED
Case 2: r+1 = b
a = qb + b
a = (q+1)b + 0, where (q+1) = q' (I guess, just to clarify) and r' = 0 QED

akubi:

Interesting. There was actually a problem assigned today that requires WOP and contradiction as proof.

Again, thanks to all who contributed proofs.

 

[TechHead87]

Originally posted by: Calin
1 = 1*1 + 0
Let's assume we have a number a, which can be written as a = nr1*b + nr2
Now, for (a+1) we have (a+1) = either nr1*b + (nr2 + 1), either as (a+1) = (nr1 + 1)*b + (nr2 - nr1 + 1)
And a = nr1 * (b+1) + nr2 - nr1, or a = (nr1-1)*(b+1) + nr2 - b - 1
and check for every case that the relation of equality is ok

Now I REALLY dont wanna go back to college!!

 

[ssvegeta1010]

Originally posted by: TechHead87

Originally posted by: Calin
1 = 1*1 + 0
Let's assume we have a number a, which can be written as a = nr1*b + nr2
Now, for (a+1) we have (a+1) = either nr1*b + (nr2 + 1), either as (a+1) = (nr1 + 1)*b + (nr2 - nr1 + 1)
And a = nr1 * (b+1) + nr2 - nr1, or a = (nr1-1)*(b+1) + nr2 - b - 1
and check for every case that the relation of equality is ok

Now I REALLY dont wanna go back to college!!

Now I really dont want to take Pre-Calc. (Still a year away though...)

 

[sao123]

Try my new proof method... its called proof by conduction.

Here hold this white wire.
Now hold this balck wire.
ZAP!

proof works every time.

 

[VigilanteCS]

Vegeta, Precalc is easy. You don't do anything like that.

 

[DerelictDev]

And Calc is easy enough as well and you dont do any of that either.

 

[Megamixman]

god damn, starting September is AP Calc.