From Wikipedia:
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value
So the point of modular arithmetic is to do our normal arithmetic operations wrap around after reaching a certain value.
From what I read about modular arithmetic operations, they are just normal operations, same as how we use in normal arithmetic.
Consider modulo n:
modulo addition is defined (a+b)mod n
modulo subtraction is defined as (a-b) mod n
modulo multiplication is defined as (a*b) mod n
modulo division is defined as (a/b) mod n
After defining above arithmetic operations we just happened to have found out that this is true, (a+b)mod n =(a mod n + b mod n) mod n which is similar with multiplication and subtraction.
That doesn't mean that modular addition is (a mod n + b mod n) or does it? (correct me if I am wrong).
now consider modular division as it is defined as (a/b) mod n
ex: consider a=48,b=8,n=4 (here b is multiple of n)
Now from what i understand This is perfectly fine (48/8)mod 8=6 right ! but as it says in above so when we modular division is not valid (a/b) modulo n when b is multiple of n.
But can't we just say (a/b) modulo n != (a mod n)/( b mod n) and move on.
So everything boils down to following questions.
1.Does while doing modular arithmetic every number 'p' that is ever going to used in arithmetic operation should be in [0,n) so modular arithmetic is ((a mod n + b mod n) mod n)
2.It doesn't matter what numbers you are using, at the end, value should be 0<= V< n so modular arithmetic is (some long cumbersome arithmetic expressions) mod n
Explain where I am getting this wrong, this is bothering me a lot.
2 Answers
There is a simple definition of the $\pmod n$ operator, in that if we have $x\equiv a\pmod n$, then we may write $x=a+kn$ for some $k\in\mathbb{Z}$.
We reduce $a$ to a value in $[0,n)$ and fix $k$ accordingly.
So:
$$(a+b) \pmod n = (a+b) + kn$$
for some $k$.
And:
$$a \pmod n + b \pmod n = a+k_an + b+k_bn = (a+b) + (k_a+k_b)n = (a+b) + kn$$
So these two are the same.
With division, the two resulting formula are not the same:
$$\frac ab \pmod n = \frac ab + kn$$
$$\frac{a \pmod n}{b \pmod n} = \frac{a + k_an}{b + k_bn}$$
I'll try my best to answer concisely:
It is not a condition for $a,b$ to be in $[o,n)$ but since every integer is equivalent to one, it makes sense to use numbers in this range
When I studied this, I liked to think that rather than division of $a$ by $b$, we multiply by the inverse of $b$. If $a|n$ there is no inverse (it is 'like' dividing by zero in a naive sense)
To find the inverse of $b \mod{c}$ there is the extended Euclidean algorithm
