Proving remainders?

  • Thread starter halo31
  • Start date
  • #1
halo31
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
36,339
8,297

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,603
1,190

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
halo31
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.
 

Suggested for: Proving remainders?

  • Last Post
Replies
18
Views
438
  • Last Post
Replies
4
Views
455
Replies
8
Views
167
Replies
2
Views
232
  • Last Post
Replies
1
Views
141
Replies
20
Views
591
Replies
6
Views
417
Replies
27
Views
1K
Replies
25
Views
1K
Top