19^24 mod 21
Solution:
Fast Modular Exponentiation
`19^24" mod "21`
Comparing with `A^B" mod "C`
We get `A=19,B=24,C=21`
Step 1: Divide B into powers of 2 by writing it in binary
`24=11000` in binary
`24=2^3+2^4`
`24=8+16`
`19^24" mod "21=19^((8+16))" mod "21`
`19^24" mod "21=(19^8*19^16)" mod "21`
Step 2: Calculate mod C of the powers of two <= B
`19^1" mod "21=19" mod "21=19`
`19^2" mod "21=(19^1*19^1)" mod "21=(19^1" mod "21*19^1" mod "21)" mod "21=(19*19)" mod "21=361" mod "21=4`
`19^4" mod "21=(19^2*19^2)" mod "21=(19^2" mod "21*19^2" mod "21)" mod "21=(4*4)" mod "21=16" mod "21=16`
`19^8" mod "21=(19^4*19^4)" mod "21=(19^4" mod "21*19^4" mod "21)" mod "21=(16*16)" mod "21=256" mod "21=4`
`19^16" mod "21=(19^8*19^8)" mod "21=(19^8" mod "21*19^8" mod "21)" mod "21=(4*4)" mod "21=16" mod "21=16`
Step 3: Use modular multiplication properties to combine the calculated mod C values
`19^24" mod "21`
`=(19^8*19^16)" mod "21`
`=(19^8" mod "21*19^16" mod "21)" mod "21`
`=(4*16)" mod "21`
`=64" mod "21`
`=1`
`:.19^24" mod "21=1`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
