1
$\begingroup$

What Modular arithmetic means from wikipedia

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value

so point of modular arithmetic is to do our normal arithmetic operations wrap around after reaching a certain value

From what i read https://www.doc.ic.ac.uk/~mrh/330tutor/ch03.html 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) this might sound dumb to many

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

$\endgroup$
1
$\begingroup$

I'll try my best to answer concisely:

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

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

$\endgroup$
  • $\begingroup$ I didn't actually get what you mean by 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 $\endgroup$ – viru Apr 22 '17 at 9:48
  • 1
    $\begingroup$ Ok, sorry it wasn't clear! Modular arithmetic splits up integers into classes. For example, $4 \equiv 1 (\mod 3)$ so $4$ and $1$ are in the same class mod $3$. If you wanted to add $4$ and $5$ them then you don't have to use $1+2 (\mod 3)$ - in fact you can use any integers in the same class as $1$ and $2$, but yes it does make sense to use the numbers in the range $[0,n)$ as they are the 'canonical' representation of the different equivalence classes $\endgroup$ – TheMathsGeek Apr 22 '17 at 10:41
  • $\begingroup$ so in any operation if a number is replaced by any number that is in it's corresponding equivalence class result should be same,is that it. lets just suppose modulo 3 then {0,3,6,9} all mean same in modular arithmetic when we are in modulo 3 system $\endgroup$ – viru Apr 22 '17 at 12:02
  • $\begingroup$ Yes, that's right! Apologies for the slow response $\endgroup$ – TheMathsGeek Apr 23 '17 at 13:22
2
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.