1

I've had quite easy time imagining why addition would be 'persistent'$\mod m$ but with multiplication it's not that obvious. I've seen proofs of it, but none have helped me internalise it. Any tips on how to think about it? Thanks.

nek28
  • 153
  • 2
    $(a+hm)(b+km)=ab+(hkm+ak+bh)m$ – almagest Mar 23 '16 at 15:03
  • 2
    Perhaps thinking about multiplication as repeated addition? It seems reasonable that repeatedly applying a 'persistent' operation would yield something 'persistent'. – pjs36 Mar 23 '16 at 15:05
  • The best "intuition" probably is understanding the proof - which is just the above formula, considered modulo $m$. – Dietrich Burde Mar 23 '16 at 15:16
  • You have to be very careful writing $a\bmod m$ as a binary function. Your statement, as one answer points out, is not true if you define $a\bmod m$ to be an integer. But if you mean it is the map that sends $a$ to its corresponding element of $\mathbb Z/m\mathbb Z$, then it is true. – Thomas Andrews Mar 23 '16 at 15:46

1 Answers1

2

Perhaps because you are missing part of the formula? (A * B) mod C = (A mod C * B mod C) mod C

CAGT
  • 831
  • 1
  • 7
  • 17
  • It would be useful to find an example where the OP's given formula fails. – Thomas Andrews Mar 23 '16 at 15:46
  • @ThomasAndrews A=2, B=2, C=4, (A * B) mod C gives 0, while (A mod C * B mod C) gives 4... that's where you need the last mod C so: (A mod C * B mod C)=0. – CAGT Mar 23 '16 at 15:54
  • I know, I meant, that should be in your answer, so you explain why you need the extra term. (As it is, it is possible that the OP means $a\bmod m$ to mean the corresponding element of $\mathbb Z/m\mathbb Z$, in which case, you don't need to change the formula.) – Thomas Andrews Mar 23 '16 at 15:56
  • @ThomasAndrews sometimes the question seems more a basic issue, like in this one. If I start adding math rigorousness in the answer like corresponding elements of a ring of integers, the OP might get lost. I prefer something more direct, like he understands the persistence of mod m in addition, multiplication should be explainable quite well with same persistence, I thought he had a bad formula. I could have written the proof by Quotient-Remainder Theorem and confuse him even more. Sometimes less is more. I feel is necessary to keep it as simple to help the OP. – CAGT Mar 23 '16 at 16:07