343 views

Which of the following(s) ALWAYS hold given that $a \equiv b(\bmod n)$ is true for some integers $a, b$ and $n.$
More than one option can be true.

1. $a \bmod n=b \bmod n$
2. $n \mid(a-b)$
3. $n \mid a$
4. $n \mid b$

### 1 comment

This a good Lecture to understand this concept. Link

A whole playlist to understand Modular Arithmetic. Link

## 2 Answers

Answer : A, B

$Given$ $:$ $a\equiv b\pmod{n}$

$According$ $to$ $the$ $definition$ $,$ $this$ $basically$ $means$ $a$ $mod$ $n$ $=$ $b$ $mod$ $n$ . $So$ $Option$ $A$ $is$ $correct$ .

$Now$ $,$ $let$ $a$ $mod$ $n$ $=$ $b$ $mod$ $n$ $=$ $r$ $which$ $is$ $the$ $remainder$ $when$ $a$ $or$ $b$ $is$ $divided$ $by$ $n$

$So$ $’a’$ $can$ $be$ $written$ $as$ :   $a$ $=$ $n*q_1$ $+$ $r$ $where$ $q_1$ → $Quotient$ $when$ $a$  $is$ $divided$ $by$ $n$ $and$ $r$ → $Remainder$

$And$  $’b’$ $can$ $be$ $written$ $as$ : $b$ $=$ $n*q_2$ $+$ $r$ $where$ $q_2$ → $Quotient$ $when$ $b$  $is$ $divided$ $by$ $n$ $and$ $r$ → $Remainder$

$Now$ , $a$ $-$ $b$ $=$ ($n*q_1$ $+$ $r$) $-$ ($n*q_2$ $+$ $r$)

$a$ $-$ $b$ $=$ $n$($q_1$ $-$ $q_2$) $which$ $is$ $clearly$ $divisible$ $by$ $n$

$Hence$ $,$ $n$ | ($a$ $-$ $b$) $is$ $True$

$Options$ $C$ $and$ $D$ $are$ $asking$ $us$ $that$ $if$ $n$ $always$ $divides$ $’a’$ $and$ $’b’$  $given$ $a\equiv b\pmod{n}$

$So$ $one$ $idea$ $here$ $could$ $be$ $to$ $think$ $of$ $an$ $counter$ $example$ $where$ $this$ $is$ $not$ $true$

$Lets$ $Take$ $27\equiv 47\pmod{10}$ $,$ $here$ $10$ $|$$27$ $is$ $false$ $as$ $you$ $can$ $see$ $and$ $also$ $47$ $|$ $10$ $is$ $also$ $false$.

$Hence$ $,$ $Options$ $C$ $and$ $D$ $are$ $false$

a ≡ b(mod n)  [a congruent to b mod n]  (given)

Now we can say that,

a/n = r  &  b/n = r means they both have same remainder r.

So, it is also valid that a mod n = b mod n as both have same remainder.

Also they can have different quotient and same remainder.

So, we can write that a = nk1 + r (where k1 is quotient)  and b = nk2 + r (where k2 is quotient).

a – b = n(k1 – k2)  =>  a – b = nk  [a – b is multiple of n] So, n | (a – b) it is also valid.

Hence, A & B are correct.

by
Answer:

4 votes
4 answers
1
2 votes
2 answers
2
310 views
9 votes
7 answers
3
1,427 views
8 votes
1 answer
4