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

Proving remainders?

  • Thread starter halo31
  • Start date
  • #1
51
0

Homework Statement


I have to prove "If a is congruent a (mod b) then a and b have the same remainders when divided by n.
I'm in a intro to proof class and we havent gone into much detail about this topic. In fact this is the first proof dealing with remainders I have to prove. Not sure if i did it right though?


Homework Equations





The Attempt at a Solution



Here is my proof:
Assume n|(a-b) implies ns=a-b where sεZ. Let a=nk+r1 where 0≤n<n. This means that ns=nk+r1-b then nk-ns+r1=b where n(k-s)+r1. Since k-sεZ then a and b both share the same remainder.
 
Last edited:

Answers and Replies

  • #2
33,492
5,182

Homework Statement


I have to prove "If a is congruent a (mod b) then a and b have the same remainders.
What is the exact problem statement? Your statement seems to be missing some important parts. What you have doesn't make any sense.

I'm in a intro to proof class and we havent gone into much detail about this topic. In fact this is the first proof dealing with remainders I have to prove. Not sure if i did it right though?


Homework Equations





The Attempt at a Solution



Here is my proof:
Assume n|(a-b) implies ns=a-b where sεZ. Let a=nk+r1 where 0≤n<n.
How can n < n?
This means that ns=nk+r1-b then nk-ns+r1=b where n(k-s)+r1. Since k-sεZ then a and b both share the same remainder.
 
  • #3
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,302
998

Homework Statement


I have to prove "If a is congruent a (mod b) then a and b have the same remainders.
I'm in a intro to proof class and we haven't gone into much detail about this topic. In fact this is the first proof dealing with remainders I have to prove. Not sure if i did it right though?

Homework Equations



The Attempt at a Solution



Here is my proof:
Assume n|(a-b) implies ns=a-b where sεZ. Let a=nk+r1 where 0≤n<n. This means that ns=nk+r1-b then nk-ns+r1=b where n(k-s)+r1. Since k-sεZ then a and b both share the same remainder.
First of all, the statement of your problem,
"If a is congruent a (mod b) then a and b have the same remainders"​
Doesn't make sense.

After looking at your proof, I suspect that the problem reads something like:
If a ≡ b (mod n), then a and b have the same remainders upon division by n .​

Your proof the following error, probably a typo.

Let a=nk+r1 where 0≤n<n. should be: Let a=nk+r1 where 0 ≤ r1 < n.

Are you starting your proof by Assuming n|(a-b) ? You should instead say that n|(a-b) is what it means for a ≡ b (mod n) .

My other question to you is, what allows you to state, "Let a=nk+r1 ..." ? You should probably mention what allows you to state that.
 
  • #4
51
0
Assume n≡a (mod b) which means n|(a-b). n|(a-b) implies ns=a-b where sεZ. Since a is divided by n then a=nk+r1 where 0≤r1<n where r1 represents the remainder. This means that ns=nk+r1-b = nk-ns+r1=b where n(k-s)+r1=b. Since k-sεZ then a and b both share the same remainder.
 

Related Threads on Proving remainders?

Replies
0
Views
2K
  • Last Post
Replies
17
Views
2K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
0
Views
2K
Top