A^B mod C = ( (A mod C)^B ) mod C
can any one please explain and provide the proof of this property of modulo arithmetic.
This follows directly from the multiplication property :
(A * B)\% m = ((A\%m)*(B\%m))\% m
Applying this property with B = A ,
(A^2)\%m = ((A\%m)*(A\%m))\%m = ((A\%m)^2)\%m
By induction for any general value of n,
(A^n)\%m = ((A\%m)^n)\%m
For Proving multiplication property, you can do induction on the addition property. (A+B)\%m = ((A\%m + B\%m))\%m