Find $9^A$ mod 100 Given $9^{40}$ mod 100 = 1

[Albert1]

given $9^{40}$ mod 100=1

if $A=9^9$

find $9^A $ mod $100=?$

 

[kaliprasad]

given $9^{40}$ mod 100=1

if $A=9^9$

find $9^A $ mod $100=?$

we can compute

Spoiler

A = 387420489
so A mod 40 = 9
so $9^A$ mod $100$ =$9^9$ mod 100 = 387420489 mod 100 = 89

but it is no fun

Spoiler

we have 40 = 8 * 5
9 mod 8 = 1
so $9^9$ mod 8 = 1
9 mod 5 = -1
so $9^9$ mod 5 = -1
we can now find $9^9$ mod 40 by chinese remainder theorem by by taking multiples of 8(only 5 multiples) and adding 1 we get checking as -1 mod 5
$9^9$ mod 40 = 9
hence A mod 40 = 9
now we need to find
$9^A$ mod 100 = $9^9$ mod 100
so let us find mod 4 and mod 25
$9$ mod 4 = 1
so $9^9$ mod 4 = 1

$9^3 = 729 = 4$ mod 25
so $9^9 = 4^3 = 64 =14 $ mod 25
we take 25 n+ 14 and divide by 4 to see remainder 1 the values are 14, 39, 64, 89 and see the result 89