Блог пользователя andreyDagger

Division over non prime modulo
Автор andreyDagger, 16 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
16 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить