# Unable to find Remainder when $2^{2009}$ is Divided by $100$

Calculate The Remainder when $2^{2009}$ is Divided by $100$

-
Dumb approach: do exponentiation by repeated squaring in $\Bbb Z/100\Bbb Z$. Did you try it? – Marc van Leeuwen Feb 19 '13 at 16:15
What theorems do you know that might be useful? – Thomas Andrews Feb 19 '13 at 16:16
actually i have tried using binomial theorem but could not get anything., Thanks – juantheron Feb 19 '13 at 16:17

Hint $\rm\ mod\ 25\!:\ \color{#C00}{2^{10}}\! = 1024\equiv \color{#C00}{-1}\:\Rightarrow\: 2^{2009}\!\! = 2^{2010-1}\!\!= (\color{#C00}{2^{10}})^{201} 2^{-1}\! \equiv \dfrac{(\color{#C00}{-1})^{201}}2 \equiv \dfrac{-1}2 \equiv \dfrac{24}2\equiv \color{#0A0}{12}\:$

Hence $\rm\,\ 4,25\mid 2^{2009}\!-\color{#0A0}{12}\:\Rightarrow\: lcm(4,25)=4\cdot 25\mid 2^{2009}\!-12,\$ i.e. $\rm\ 2^{2009}\!\equiv 12\:\ (mod\ 100)$

-
Will you explain the notation in the second line, please? (I'm referring to the comma and the bar.) – daniel.wright Feb 20 '13 at 0:33
@daniel $\rm\ b\mid c\$ means $\rm\,b\,$ divides $\rm\,c,\:$ and $\rm\ a,b\mid c\$ means both $\rm\,a,b\,$ divide $\rm\,c.\:$ This notation is in wide use in number theory. – Math Gems Feb 20 '13 at 1:00

The simplest approach is to call up a spreadsheet, put 1 in cell A1, put =mod(2*A1,100) in A2 and copy down.

$2^n \pmod {100}$ will go through a repeating pattern with cycle $20$, so $2^{2009} \equiv ?? \pmod {100}$

-