Question

Let m be a positive integer. Show that a mod m = b mod m if a ≡ b (mod m).

Answer 1

use the definition

Answer 2

according to the defintion, a = b(mod m) then m divides a - b

Answer 3

\(\large a\equiv b \pmod n\)

means


\(\large n|(a-b)\)

Answer 4

\(a\equiv b \pmod m \implies a = ms + b\) for some \(s\)

Answer 5

Next consider \(a \pmod m\)
By division algorithm there exists some \(r, t\) such that \(a = mt + r\) where \(0 \le r\lt m\)

Answer 6

fine with above two steps right ?

Answer 7

eliminate \(a\) from both equations you get :

\(a-a = ms+b - (mt+r)\)

Answer 8

simplifying a bit you get :
\(b = m(t-s) + r\) where \(0\le r\lt m\) again

Answer 9

So we have :

\(\large a = mt + r\)
\(b = m(t-s) + r\)

where \(0\le r\lt m\)

Answer 10

t and r for some integer?

Answer 11

that precicely means
\(a\pmod m = r\)
\(b\pmod m = r\)

right ?

Answer 12

yes

Answer 13

yeah so if I use 0 then a (mod m) = b (mod m)?

Answer 14

they both equal to r
so they are equal to each other too

Answer 15

lol thats it?

Answer 16

thats it, you don't look convinced hmm

Answer 17

just a little confusing. Discrete math isnt my favorite math subject :(

Answer 18

and my teacher isnt being very helpful. Im taking it online.. i know it is a bad idea!

Answer 19

All these congruence proofs just require you to check with the definition of congruence relation at each step. And luckily there is only one definition to check - check my first reply from top

Answer 20

for example,
if u have some equation like : \(a = mt + r\)
you can express it using congruence definition as \(a\equiv r \pmod m\)

Answer 21

I cant copy and paste for some reason. its your 3rd post. where did you find that defintion?

Answer 22

\(a\equiv b \pmod m \implies a = ms + b\) for some \(s\)

this one ?

Answer 23

yes

Answer 24

thats same as the definition you gave me, let me break it into steps :)

Answer 25

\(a\equiv b \pmod m \implies m | (a-b)\)

fine ?

Answer 26

sure..

Answer 27

that means there will be some integer factor \(s\) such that : \((a-b) = ms\)

still fine ?

Answer 28

yeah I guess its fine lol

Answer 29

kick that \(b\) to other side, you get :
\(a = ms + b\)

Answer 30

ah I see.. ok thanks!

Answer 31

after doing few congruence proofs, it becomes easy to see why below is same as the definition. you can use below directly and skip that intermediate division step : \[a \equiv b\pmod m \implies a = mq + b\]

Answer 32

is that other method?

Answer 33

its same, i have just skipped the intermediate step

Answer 34

whats the intermediate step?

Answer 35

\[a \equiv b\pmod m \color{Red}{\implies m|(a-b) \implies (a-b) = mq} \implies a = mq + b\]

Answer 36

Oh i see

Answer 37

you dont need to show those intermediate steps in red always
you can directly jump from first step to last once u get hang of congruences

Answer 38

Yeah thanks