Proving m mod d = n mod d with Quotient Remainder Theorem

In summary, the Quotient Remainder Theorem states that for any integer n and positive integer d, there exists unique integers q and r such that n=dq + r and 0≤r<d and n mod d = r. Using this theorem, it can be proven that if m, n, and d are integers and d divides (m-n), then m mod d = n mod d. This is shown by expressing m and n in terms of d and using the fact that d divides (m-n) to show that (m-n) mod d = (r-s), where r and s are the remainders of m and n when divided by d. Therefore, m and n will have the same remainder when
  • #1
cmajor47
57
0

Homework Statement


Prove that is m, n, and d are integers and d divides (m-n) then m mod d = n mod d.


Homework Equations


Quotient Remainder Theorem: Given any integer n and positive integer d, there exists unique integers q and r such that n=dq + r and 0[tex]\leq[/tex]r<d and n mod d = r.


The Attempt at a Solution


Proof: Let m, n, d [tex]\in[/tex] Z st d divides (m-n)
[tex]\exists[/tex] k [tex]\in[/tex] Z st m=dk + r
[tex]\exists[/tex] j [tex]\in[/tex] Z st n=dj + s
m-n=(dk + r)-(dj + s)
=dk+r-dj+s
=d(k-j)+(r-s)

Am I going along with the proof correctly? I don't know where to go from this point and would really appreciate some help.
 
Physics news on Phys.org
  • #2
I'm not sure this is the easiest proof, but it looks correct.

You have now shown that
if m = r mod d, n = s mod d, then (m - n) mod d = (r - s)
But you also know that d | (m - n) which you haven't used yet. So what does that tell you about (m - n) mod d?
 

1. What is the Quotient Remainder Theorem?

The Quotient Remainder Theorem is a mathematical theorem that states that when dividing two integers, the result can be expressed as a quotient and a remainder. It is also known as the Division Algorithm.

2. How does the Quotient Remainder Theorem relate to modular arithmetic?

The Quotient Remainder Theorem is often used to prove equations in modular arithmetic, specifically when proving that m mod d = n mod d. This is because the remainder in the division algorithm is equivalent to the value in modular arithmetic.

3. What is the process for proving m mod d = n mod d using the Quotient Remainder Theorem?

To prove m mod d = n mod d using the Quotient Remainder Theorem, you must first divide both m and n by d using the division algorithm. The remainder in both cases should be equal, showing that m mod d = n mod d.

4. Can the Quotient Remainder Theorem be used for all values of m, n, and d?

Yes, the Quotient Remainder Theorem can be used for all values of m, n, and d. However, it is important to note that m and n must be integers, and d must be a positive integer.

5. Are there any common mistakes when using the Quotient Remainder Theorem to prove m mod d = n mod d?

One common mistake when using the Quotient Remainder Theorem to prove m mod d = n mod d is not following the correct steps in the division algorithm. It is important to divide both m and n by d and to consider the remainder in both cases, not just one. Another mistake is using the incorrect value for d, as it must be a positive integer.

Similar threads

Can anyone please review/verify this proof of greatest common divisor?
    • Calculus and Beyond Homework Help
Replies
2
Views
958
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
511
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
574
Chinese Remainder theorem for 2 congruences
    • Calculus and Beyond Homework Help
Replies
2
Views
1K
Prove ##(a+b)\cdot c=a\cdot c+b\cdot c## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
520
Prove ## a/d\equiv b/d \mod n/d ##.
    • Precalculus Mathematics Homework Help
Replies
2
Views
694
Relation of m mod d and n mod d Proven
    • Calculus and Beyond Homework Help
Replies
1
Views
688
U(n) as an External Direct Product
    • Calculus and Beyond Homework Help
Replies
11
Views
1K
Prove ##a + b = b + a## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
811
Chinese remainder theorem (CRT) question, flat shapes
    • Calculus and Beyond Homework Help
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top