Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer
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}$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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