1

It's from a programming language. "%' here is a modulo operation.

(a * 2^32 + b) % c = (((a % c) * (2^32 % c)) + b) % c
accme
  • 111
  • So, what you want to prove is that $a\cdot b(\mod c)=(a(\mod c)\cdot b(\mod c))(\mod c)$ and the same holds for addition, correct? – Dennis Gulko Nov 13 '12 at 10:14
  • Mmm, probably right :) But I'm not a mathematician, so I would be glad to take a look at some basic articles on this theme. – accme Nov 13 '12 at 10:32

1 Answers1

1

In general, if you have two integers

a = j + kc
b = l + mc

Then

ab % c
= (j+kc)(l+mc) % c 
= (jl + jmc + lkc + kmc^2) % c
= jl
= (a % c)(b % c)
Norbert
  • 56,803
Zert
  • 123
  • 4
  • And the same for sums. – Fabian Nov 13 '12 at 10:20
  • "jl + jmc + lkc + kmc^2 % c" - does '%' relate only to the last term? Why? And why this equals to 'jl'? – accme Nov 13 '12 at 10:27
  • Just like (1+2+4+6)/2=(1/2)+1+2+3 (look at the parentheses), (jl + jmc + lkc + kmc^2) / c=(jl/c)+jm+lk+kmc. Think about what that means about (jl + jmc + lkc + kmc^2) % c. – Mark S. Nov 13 '12 at 12:32