# Remainder when large numbers divided

• Jun 27th 2011, 01:13 PM
Zalren
Remainder when large numbers divided
What is the remainder when $\displaystyle 2001^{2001}$ is divided by $\displaystyle 26$?

I think I have to do something with $\displaystyle 26$, like break it up into $\displaystyle 13 * 2$. Try to use Fermat's Theorem somehow. I know that $\displaystyle (2001, 13) = 1$ and $\displaystyle (2001, 2) = 1$.

Any help to get rolling would be appreciated.
• Jun 27th 2011, 02:24 PM
VinceW
Re: Remainder when large numbers divided
$\displaystyle 2001 \equiv 25 \pmod {26}$
$\displaystyle 2001^2 \equiv 25^2 \equiv 1 \pmod {26}$
$\displaystyle 2001^4 \equiv 1^2 \equiv 1 \pmod {26}$
$\displaystyle 2001^8 \equiv 1 \pmod {26}$
$\displaystyle 2001^{16} \equiv 1 \pmod {26}$
$\displaystyle 2001^{64} \equiv 1 \pmod {26}$
$\displaystyle 2001^{256} \equiv 1 \pmod {26}$
$\displaystyle 2001^{512} \equiv 1 \pmod {26}$
$\displaystyle 2001^{1024} \equiv 1 \pmod {26}$

$\displaystyle 2001^{2001} = 2001^{1024} 2001^{512} 2001^{256} 2001^{128} 2001^{64} 2001^{16} 2001 \equiv 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 25 \equiv 25 \pmod {26}$
• Jun 27th 2011, 06:10 PM
Soroban
Re: Remainder when large numbers divided
Hello, Zalren!

Quote:

$\displaystyle \text{What is the remainder when }2001^{2001}\text{ is divided by }26\,?$
. . .$\displaystyle 2001 \;=\;77(26) -1$

$\displaystyle \begin{array}{ccccc} 2001 & \equiv & \text{-}1 & \text{(mod 26)} \\ \\[-3mm] 2001^{2001} & \equiv & (\text{-}1)^{2001} & \text{(mod 26)} \\ \\[-3mm] 2001^{2001} & \equiv & \text{-}1 & \text{(mod 26)} \\ \\[-3mm] 2001^{2001} & \equiv & 25 & \text{(mod 26)}\end{array}$

$\displaystyle \text{Therefore, }2001^{2001} \div 26\text{ has a remainder of }25.$

• Jun 27th 2011, 06:13 PM
Drexel28
Re: Remainder when large numbers divided
Quote:

Originally Posted by VinceW
$\displaystyle 2001 \equiv 25 \pmod {26}$
$\displaystyle 2001^2 \equiv 25^2 \equiv 1 \pmod {26}$
$\displaystyle 2001^4 \equiv 1^2 \equiv 1 \pmod {26}$
$\displaystyle 2001^8 \equiv 1 \pmod {26}$
$\displaystyle 2001^{16} \equiv 1 \pmod {26}$
$\displaystyle 2001^{64} \equiv 1 \pmod {26}$
$\displaystyle 2001^{256} \equiv 1 \pmod {26}$
$\displaystyle 2001^{512} \equiv 1 \pmod {26}$
$\displaystyle 2001^{1024} \equiv 1 \pmod {26}$

$\displaystyle 2001^{2001} = 2001^{1024} 2001^{512} 2001^{256} 2001^{128} 2001^{64} 2001^{16} 2001 \equiv 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 25 \equiv 25 \pmod {26}$

I think you made it harder than it has to be (both of you). Isn't it true that $\displaystyle \displaystyle 2001^{2001}\equiv 25^{2001}\equiv (-1)^{2001}\equiv -1\equiv 25\text{ mod }26$.