# What is the remainder when $25^{889}$ is divided by 99?

What is the remainder when $25^{889}$ is divided by 99 ?

$25^3$ divided by $99$ gives $26$ as a remainder.

$25*(25^3)$ divided by $99$ gives (remainder when $25*26$ is divided by $99$) as a remainder.

i.e. $25*(25^3)$ divided by $99$ gives $56$ as a remainder.

$(25^3)*(25^3)$ divided by $99$ gives (remainder when $26*26$ is divided by $99$) as a remainder.

i.e. $(25^3)*(25^3)$ divided by $99$ gives $82$ as a remainder.

• 99 = 11*9, so just consider the reminder for 11 and 9. Use Fermat' little theorem. Mar 31 '13 at 0:36

Note that $11\cdot 9 = 99$: so consider $25^{889} \;\text{mod}\; 11, \;\text{and mod}\;9$

Can you see how to apply Fermat's Little Theorem here? And perhaps it's generalization: Euler's Theorem?

Two tricks to use here:

1. By the Chinese Remainder Theorem, it suffices to find $25^{889} \bmod 9$ and $25^{889} \bmod{11}$, and combine the results.

2. For any modulus $m$ and numbers $a$ and $b$, we have $a^b \equiv (a \bmod m)^{(b \mod \phi(m))}$.

$25^{889}$

= $25^{7*127}$

= $(25^7)^{127}$

= $(25*625*625*625)^{127}$

= $(25*625^3)^{127}$

= $(25*(99A+31)^3)^{127}$

= $(99B + 25*(31)^3)^{127}$

Remainder when $(25*(31)^3)^{127}$ is divided by 99

= Remainder when $(25*31*961)^{127}$ is divided by 99

= Remainder when $(25*31*70)^{127}$ is divided by 99

= Remainder when $(25*2170)^{127}$ is divided by 99

= Remainder when $(25*91)^{127}$ is divided by 99

= Remainder when $(2275)^{127}$ is divided by 99

= Remainder when $(97)^{127}$ is divided by 99

= Remainder when $97*(97^2)^{63}$ is divided by 99

= Remainder when $97*(9409)^{63}$ is divided by 99

= Remainder when $97*(103)^{63}$ is divided by 99

= Remainder when $97*(4)^{63}$ is divided by 99

= Remainder when $97*(2^9)^{14}$ is divided by 99

= Remainder when $97*(512)^{14}$ is divided by 99

= Remainder when $97*((17)^2)^{7}$ is divided by 99

= Remainder when $97*(289)^{7}$ is divided by 99

= Remainder when $97*(91)^{7}$ is divided by 99

= Remainder when $97*91*((91)^2)^{3}$ is divided by 99

= Remainder when $97*91*(8281)^{3}$ is divided by 99

= Remainder when $97*91*(163)^{3}$ is divided by 99

= Remainder when $97*91*(64)^{3}$ is divided by 99

= Remainder when $97*91*(2^9)^{2}$ is divided by 99

= Remainder when $97*91*(512)^{2}$ is divided by 99

= Remainder when $97*91*(17)^{2}$ is divided by 99

= Remainder when $97*91*(289)$ is divided by 99

= Remainder when $97*91*(91)$ is divided by 99

= Remainder when $97*(8281)$ is divided by 99

= Remainder when $97*(163)$ is divided by 99

= Remainder when $97*64$ is divided by 99

= Remainder when $95*32$ is divided by 99

= Remainder when $67*4$ is divided by 99

= Remainder when $70$ is divided by 99

Remainder is 70

$\rm mod\ 9\!:\ 25^3\equiv (-2)^3\equiv -8\equiv 1\:\Rightarrow\:n = 25^{889}\equiv 25^{889\ mod \ 3}\equiv 25\equiv \color{#0A0}{-2}$

$\rm mod\ 11\!:\ 25^5\equiv 5^{10}\equiv 1\:\Rightarrow\:n = 25^{889}\equiv 25^{889\ mod\ 5}\equiv 25^4 \equiv 3^4\equiv (-2)^2\equiv \color{#C00}4$

$\rm mod\ 9\!:\ \color{#0A0}{{-}2} \equiv n\equiv \color{#C00}4\!+\!11k\equiv 4\!+\!2k\:\Rightarrow\:k\equiv -3\equiv\color{blue}{6}\:\Rightarrow\:n = 4\!+\!11(\color{blue}{6}\!+9\,j) = 70+99\,j$

Using Carmichael Function, $\lambda(99)=$lcm $(\lambda(9),\lambda(11))=$lcm$(3(3-1),10)=30$

So, $5^{30}\equiv1\pmod {99}$

Now, $25^{889}=(5^2)^{889}=5^{1788}$

Also, $1778\equiv 8\pmod {30}\implies 25^{889}=5^{1780}\equiv5^8\pmod {99}$

$5^2=25,5^3=125\equiv26\pmod{99},5^4\equiv26\cdot5\equiv31\pmod{99},$

$5^8=(5^4)^2\equiv(31)^2\pmod{99}\equiv961\equiv-29\pmod{99}$ as $990=99\cdot10$

So, $5^8\equiv-29\pmod{99}\equiv70$

Euler’s Number of $99$

= $99.\frac{2}{3}.\frac{10}{11}$

= $60$

From Fermat’s Theorem we know

$25^{60 × K} \mod {99} = 1$ (where K is any natural number)

Note that $25$ and $99$ are co-primes (∵ they don’t have any common factors other than $1$)

Putting $K =15$, we have, $25^{900} \mod {99} = 1$

Let’s assume $25^{899} \mod {99} = R$

∴ $25^{899} = 99N + R$ (where $N$ is a natural number)

$25^{900} \mod {99} = (25 × 25^{899}) \mod {99} = (25 × R) \mod {99} = 1$

we can conclude that $R=4$