andreyDagger's blog

Division over non prime modulo
By andreyDagger, 15 months ago, In English

Let $$$m$$$ be some positive integer (not necessary prime) . There is a way to calculate $$$\displaystyle{\frac{a}{b}}\%m$$$ when b is not very big and $$$a \% b = 0$$$ Firstly, let's notice, that $$$\displaystyle{\frac{a}{b}}=mk+(a/b)\%m$$$, for some integer value k. Now, let's do some mathematical stuff:

$$$\displaystyle{\frac{a}{b}}=mk+\displaystyle{\frac{a}{b}}\%m$$$
$$$a=mbk+b(\displaystyle{\frac{a}{b}}\%m)$$$
$$$(a\%mb)=b(\displaystyle{\frac{a}{b}}\%m)$$$
$$$(a\%mb)/b=\displaystyle{\frac{a}{b}}\%m$$$

So, the answer is $$$(a\%mb)/b$$$

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If a%b = 0, then won't I first calculate a/b and then find (a/b) modulo m, so is this formula useful practically?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Yes, $$$a$$$ can be very big. For example $$$\frac{10^n-1}{9} \% m$$$

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is "when $$$b$$$ is not very big" required?
This proof is correct even for large $$$b$$$ right?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For big $$$b$$$ you need to use BigInteger because you can't make something like this $$$b\%=m$$$

    → Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This can be generalized, when $$$a \%b$$$ can differ from $$$0$$$. Let $$$\gcd (b,m)=1$$$ for simplicity. We only want to calculate $$$b^{-1}$$$ (the inverse). We can find $$$p,q$$$ such that $$$pb + qm = 1$$$ with extended Euclidean algorithm. $$$q$$$ is not important, but $$$p$$$ will exactly be equal to the inverse. So, $$$\frac{a}{b} = ap\% m$$$.

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

If I wanted $$$\frac{1}{2} \pmod{11}$$$, is the answer $$$(1 \text{ mod } 22)/2$$$?

→ Reply