0

before i will explain of my question , first of all let us introduce classical definition of division algorithm ,namely for given integer $a$ and integer $d$, here exist unique integers $q$ and $r$ such that

$0 \leq r <d$

so that $a=d*q+r$

from where

$q=\frac{a}{d}$

and $r$ is remainder when we are dividing $a$ by $d$

now question about one theorem : namely let $a$ and $b$ be integers and let $m$ be positive integers, then

$${a}\equiv b \pmod {m}. $$

if they have same remainder when divided by $m$

this $${a}\equiv b \pmod {m}. $$ means that

$a-b=k*m$

or $a=k*m+b$

compare to this equation

$a=d*q+r$

$b$ is remainder when $a$ is divided by $m$, on the other hand

$a-b=k*m$

from here $b=-k*m+a$

from this equation we know that when b is divided by $m$, quotient part is $-k$ and remainder is $a$, but that means that $a=b$ , as i know it is not necessary that $a$ must be equal to $b$ , if they are equal of course

$${a}\equiv b \pmod {m}. $$

as $a-b=0$ and $0$ mod $m$ is equal to zero, so where i am making mistake in my conclusion ?

dato datuashvili
  • 9,194

1 Answers1

0

Your confusion is due to the statement

'$b$ is remainder when $a$ is divided by $m$, ....'

which is not necessarily true. It is only true if it happens to be the case that $b$ < $m$, which is not required in general. What is true is that $a$ and $b$ will have the same remainder $r$ under the division algorithm (given $m$).

PMar
  • 1