3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 99 = 11*9, so just consider the reminder for 11 and 9. Use Fermat' little theorem. $\endgroup$
    – Yimin
    Mar 31 '13 at 0:36
7
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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))}$.

$\endgroup$
2
$\begingroup$

$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

Please use Calculator.

$\endgroup$
1
$\begingroup$

$\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$

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.