(a * b)$^{x}$ mod n = ((a$^{x}$ mod n) * (b$^{x}$ mod n)) mod n
Can anyone give me some tips to prove the above equation? Thanks.
(a * b)$^{x}$ mod n = ((a$^{x}$ mod n) * (b$^{x}$ mod n)) mod n
Can anyone give me some tips to prove the above equation? Thanks.
This follows from basic modular arithmetic: if $k\equiv r\pmod{n}$ and $\ell\equiv s\pmod{n}$, then $k\ell\equiv rs\pmod{n}$. Since $(ab)^x = a^xb^x$, then what you have is just this instance with $k=a^x$, $\ell=b^x$, $r=a^x\bmod n$ and $s=b^x\bmod n$. The final "$\bmod n$" just assures that you fall inside the main residue class representatives.