Recall that in class, we proved the division algorithm, which states that if n a

Question

Recall that in class, we proved the division algorithm, which states that if n and d are integers and d > 0, then there exists a unique pair of integers (q,r) satisfying the following properties: • n = qd + r. • 0 r < d. The integers q and r are called the “quotient” and “remainder,” respectively, when n is divided by d. Use the division algorithm to prove the following proposition. Proposition: Let n, m, and d be integers and suppose d > 0. Then nm is divisible by d if and only if n and m have the same remainders when divided by d. (Hint: In order to prove the statement nm is divisible by d n and m have the same remainders when divided by d, it may be helpful to review the “uniqueness” part of the proof of the division algorithm.)

Explanation / Answer

Let n= dq+r and m= ds+t. where, 0<=r<d and 0<=t<d

Where r and t are the remainder s when n and m are divided by d respectively.

To show, s=t

Now, n-m = d(q-s) + (r-t)

Now d divides n-m if and only if, d divides r-t ( since d(q-s) is already divisible by d)

Hence, d divides r-t

But, from the inequality relation of d with r and t, we get that d divides r-t if and only if r-t=0

i.e. r=t

i.e. m and n have same remainders

Conversely if they have remainder then, m=dq+r and n=ds+r

Then, m-n = dq-ds = d(q-s)

Hence d divides m-n

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.