求救 有條mod數唔識計

203=29*7

Now, we can use Chinese Remainder Theorem to solve it,

y= 25^13 (mod 29) -----(i)
y=25^13(mod 7) ------- (ii)


Then let y = 7p+29q (mod203) ----------- (*)
Since 7=7(mod29) ,
we need 7p = 25^13 (mod29)
= (-4)^(4*3+1) (mod29) as 25=-4 mod(29)
= (((-4)^4)^3)*(-4) (mod 29)
as (-4)^12= ((-4)^4)^3
= ((-5)^3)*(-4) (mod 29) as (-4)^4 = -5 mod (29)
= (-9) * (-4) (mod29) as (-5)^3 = -9 (mod29)
= 7 (mod29)
then p = 1 (mod29 )
Since 29 = 1(mod 7)
we need q = 25^13 (mod 7)
= 4^13 (mod 7) as 25= 4 (mod7)
= ((4^3) ^4) *4 (mod 7) as 4^13 = ((4^3) ^4) *4
= (1^4) *4 (mod7) as 4^3 = 1(mod7)
= 4 mod7
Therefore, substitute p=1, q=4 into the equation (*)
then y= 7p+29q
=7*1+29*4
= 123(mod203)

你應該將
25^13 mod 203
=(25^2)^6 * 25 mod 203
= 625^6 * 25 mod 203
= 16^6 *25 mod 203 ( because 625 mod 203 = 16 )
= 4096^2 * 25 mod 203
= 36^2 *25 mod 203 ( because 4096 mod 203 = 36 )
= 1296 * 25 mod 203
= 78 * 25 mod 203 ( because 1296 mod 203 = 78 )
= 123

2007-06-02 01:47:30 補充：
閣下是大學生??你是想用The Rules of Exponentiation??25 mod 203 = 2525^2 mod 203 = 1625^4 mod 203 = (25^2 mod 203)^2 mod 203 = 16^2 mod 203 = 5325^8 mod 203 = (25^4 mod 203)^2 mod 203 = 53^2 mod 203 = 170(待續)

2007-06-02 01:47:37 補充：
25^(8 4 1) mod 203= 170 * 53 * 25 mod 203= (170*53 mod 203) * 25 mod 203= 78 * 25 mod 203= 123當中用了6次mod.