# Remainder when large numbers divided

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

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

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

$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}$
• June 27th 2011, 06:10 PM
Soroban
Re: Remainder when large numbers divided
Hello, Zalren!

Quote:

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

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

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

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

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

$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 2001^{2001}\equiv 25^{2001}\equiv (-1)^{2001}\equiv -1\equiv 25\text{ mod }26$.