Modulus transformation

Question

Can someone confirm whether this is true :

$((a^b \ mod\ n) * (a^c \ mod \ n)) \mod \ n = a^{b+c} \ mod \ n$

Im pretty sure it is, and every combination of numbers i try manually works, but when i try to write a program that tests this for combinations from 1 to 25 for a,b,c,n i get different results and im not sure whether this is to problems with the modulus operation, maybe overflows happening

I cant find any rules for this specifically since the equation is so long

Please typeset the mathematics in your question using mathjax, to make it readable. — Lee Mosher, Sep 13 '19 at 19:46
Didnt really think it was long enough to bother but sure, done — Cx Vercility, Sep 13 '19 at 19:54

John Omielan · Answer 1 · 2019-09-13T20:42:13.007

0

Let $a^b = dn + e$, where $0 \le e \lt n$ and $a^c = fn + g$, where $0 \le g \lt n$. Then your left side is

$$((a^b \ \text{mod} \ n) * (a^c \ \text{mod} \ n)) \ \text{mod} \ n = eg \ \text{mod} \ n \tag{1}\label{eq1}$$

Since $a^{b+c} = (a^b)(a^c) = (dn + e)(fn + g) = dfn^2 + (dg + ef)n + eg$, your right side is

$$a^{b+c} \ \text{mod} \ n = eg \ \text{mod} \ n \tag{2}\label{eq2}$$

Thus, your LHS and RHS match.

edited Sep 13 '19 at 20:42

answered Sep 13 '19 at 20:35

John Omielan

47,976

1

Exactly what i was looking for. Thanks a ton man! – Cx Vercility Sep 13 '19 at 20:40

Modulus transformation

1 Answers1