Determine 462 and hence determine 5603 mod 462SolutionConver

Determine (462) and hence determine 5^603 mod 462.

Solution

Converting 603 to bianry form

1001011011

so to determine the mod the problem can be written as

(5^1 * 5^2 * 5^8 * 5^16 * 5^64 * 5^512) mod 462

5^1 mod 462= 5

5^2 mod 462= (5^1 * 5^1) mod 462= (5^1 mod 462* 5^1 mod 462) mod 462
5^2 mod 462= (5 * 5) mod 462= 25 mod 462
5^2 mod 462= 25

5^4 mod 462= (5^2 * 5^2) mod 462= (5^2 mod 462* 5^2 mod 462) mod 462
5^4 mod 462= (25 * 25) mod 462= 625 mod 462
5^4 mod 462= 163

5^8 mod 462= (5^4 * 5^4) mod 462= (5^4 mod 462* 5^4 mod 462) mod 462
5^8 mod 462= (163* 163) mod 462
5^8 mod 462= 235

5^16 mod 462= (5^8 * 5^8) mod 462= (5^8 mod 462* 5^8 mod 462) mod 462
5^16 mod 462= (235 * 235) mod 462= 16 mod 19
5^16 mod 19 = 247

5^32 mod 462= (5^16 * 5^16) mod 462= (5^16 mod 462* 5^16 mod 462) mod 462
5^32 mod 462= (247* 247) mod 462
5^32 mod 462= 25

5^64 mod 462= (5^32 * 5^32) mod 462= (5^32 mod 462* 5^32 mod 462) mod 462
5^64 mod 462= (25 * 25) mod 462
5^64 mod 462= 163

Similarly, the mod for higher power of 2 can be written as

5^128 mod 462= 235

5^256 mod 462= 247

5^512 mod 462= 25

Step 3: Use modular multiplication properties to combine the calculated mod C values

5^603 mod 462 = (5^1 * 5^2 * 5^8 * 5^16 * 5^64 * 5^512) mod 462
5^603 mod 462 = ( 5^1 mod 462 * 5^2 mod 462 * 5^8 mod 462 * 5^16 mod 462 * 5^64 mod 462 * 5^512 mod 462) mod 462
5^603 mod 462 = ( 5 * 25 * 235 * 247 * 163 * 25 ) mod 462
5^603 mod 462 =  125
5^603 mod 462 = 125