How to prove the modular multiplication property?

Question

In Number Theory, I have seen many a times the following property being used though I don't know what it's called formally (that makes it harder to Google):

(a * b) (mod n) = (a mod n) * (b mod n)

What is this called and how can it be formally proved?

It's the definition of multiplication modulo $n$, after it has been shown it does not depend on the choice of the representatives in each class. — Bernard, Feb 03 '17 at 22:43
This notation can be a little confusing if you're trying to do this on a computer.
Let a=15, b=42, and n=12.

(a * b) % n = 6

(a % n) * (b % n) = 18

However, ((a % n) * (b % n)) % n = 6.

From what I read at https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-multiplication, the "multiplication property of modular arithmetic" is

(a * b) % n = ((a % n) * (b % n)) % n — William John Holden, Feb 09 '22 at 18:31

score 9 · Accepted Answer · answered Feb 03 '17 at 22:38

9

If $a=xn+a'$ and $b=yn+b'$, where all are whole numbers, then $a'=a\text{ mod }n$ and $b'=b\text{ mod }n$. It's then easy enough to multiply them:

$$ab=(xn+a')(yn+b')=(xyn+xb'+ya')n+a'b'$$

Take mod $n$ of both sides, and it should then be clear that

$$ab\equiv a'b'\pmod n$$

answered Feb 03 '17 at 22:38

Simply Beautiful Art

74,685

sorry for the very stupid question, how do you deduce the final equation from the previous one? – Math and ML Jun 17 '19 at 23:54
By definition, $mn+c\equiv c\pmod n$. Can you see what $m$ and $c$ are? – Simply Beautiful Art Jun 18 '19 at 02:00
m and c be any integer? so how does this relate to what you wrote above? – Math and ML Jun 18 '19 at 10:19
ok so is the logic that xyn + xb' + ya' any integer hence it is m, then you get mn + a'b' = ab? – Math and ML Jun 18 '19 at 10:24
1

@mkheifetz yes. – Simply Beautiful Art Jun 18 '19 at 10:43

How to prove the modular multiplication property?

1 Answers1