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.
 A: 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?
A: Two tricks to use here:


*

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

*For any modulus $m$ and numbers $a$ and $b$, we have $a^b \equiv (a \bmod m)^{(b \mod \phi(m))}$.
A: $\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$
A: 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$
A: 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$
