7^106 mod 143
Solution:
Fast Modular Exponentiation
`7^106" mod "143`
Comparing with `A^B" mod "C`
We get `A=7,B=106,C=143`
Step 1: Divide B into powers of 2 by writing it in binary
`106=1101010` in binary
`106=2^1+2^3+2^5+2^6`
`106=2+8+32+64`
`7^106" mod "143=7^((2+8+32+64))" mod "143`
`7^106" mod "143=(7^2*7^8*7^32*7^64)" mod "143`
Step 2: Calculate mod C of the powers of two <= B
`7^1" mod "143=7" mod "143=7`
`7^2" mod "143=(7^1*7^1)" mod "143=(7^1" mod "143*7^1" mod "143)" mod "143=(7*7)" mod "143=49" mod "143=49`
`7^4" mod "143=(7^2*7^2)" mod "143=(7^2" mod "143*7^2" mod "143)" mod "143=(49*49)" mod "143=2401" mod "143=113`
`7^8" mod "143=(7^4*7^4)" mod "143=(7^4" mod "143*7^4" mod "143)" mod "143=(113*113)" mod "143=12769" mod "143=42`
`7^16" mod "143=(7^8*7^8)" mod "143=(7^8" mod "143*7^8" mod "143)" mod "143=(42*42)" mod "143=1764" mod "143=48`
`7^32" mod "143=(7^16*7^16)" mod "143=(7^16" mod "143*7^16" mod "143)" mod "143=(48*48)" mod "143=2304" mod "143=16`
`7^64" mod "143=(7^32*7^32)" mod "143=(7^32" mod "143*7^32" mod "143)" mod "143=(16*16)" mod "143=256" mod "143=113`
Step 3: Use modular multiplication properties to combine the calculated mod C values
`7^106" mod "143`
`=(7^2*7^8*7^32*7^64)" mod "143`
`=(7^2" mod "143*7^8" mod "143*7^32" mod "143*7^64" mod "143)" mod "143`
`=(49*42*16*113)" mod "143`
`=3720864" mod "143`
`=4`
`:.7^106" mod "143=4`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
