SecondThread's blog

Algorithms Dead Episode 1: Divsion Under Mod!
By SecondThread, history, 4 years ago, In English

Algorithms Dead Episode 1: Division Under Mod

Do you blindly do operations under mod without knowing why they work? Does it scare you when a problem asks you do print something mod a big number? If so, you should watch Episode 1 of Algorithms Dead!

In it, I talk about why mod operations (addition/subtraction/multiplication) are allowed, why mod inverses work, and what things are safe to do when you store fractions as $$$p*q^{-1}$$$.

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

It was nice, your channel has many helpful videos,also loved the lecture on Game Theory.

→ Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

the answer for 8/7(mod 5) = 4 using prime modulo inverse , shouldn't it be 1 ?

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

    The denominator is 7 here, which is congruent to 2(mod 5).

    The multiplicative inverse of 2 under mod 5 is 3.

    So, the expression becomes

    = (8*3)(mod 5)
= 24(mod 5)
= 4
    → Reply