Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite
1

I am trying to calculate the last two digits of $3^{400}$, but working $\bmod {100}$ is proving intractable. I did the last digit case pretty handily, and now I'm stuck at last two.

share|improve this question
If you just want to know the last two digits, you can use Wolfram|Alpha or Python: $3^{400} = 70550791086553325712464271575934796216507949612787315762871223209262085551582934‌​156579298529447134158154952334825355911866929793071824566694145084454535257027960‌​285323760313192443283334088001$. So 01 is indeed the correct answer. – moose Sep 12 '12 at 12:28
Actually, in Python the pow function has an optional third argument, the modulo of the power. With it you even can compute quite easily the last two digits of 3⁴⁰⁰⁰⁰⁰⁰⁰⁰⁰: pow(3, 4000000000, 100) → 1 – Alfe Sep 12 '12 at 15:08

4 Answers

up vote 10 down vote accepted

We have $3^{400}=(-1+10)^{200}$. The first term in the expansion via the Binomial Theorem is $1$. The other terms are divisible by $100$. Indeed by $1000$.

share|improve this answer
up vote 11 down vote

Are you familiar with the generalization of Fermat's little theorem?

From it you know that $3^{\phi(100)}\equiv 1\pmod{100}$, where $\phi$ is the Euler totient function. I get $\phi(100)=40$, and so $3^{400}\equiv 1\pmod{100}$ if I haven't made any errors.

share|improve this answer
I have seen it before, but it was not discussed in this class, which makes me think that we are supposed to do this simply using the basics of modular arithmetic? – JJR Sep 12 '12 at 3:19
4  
@jmi4 A way to force your way through it would be to compute lower powers of $3$ until you find something easy to work with. Investigating the first few powers shows $3^{20}=3486784401$, so $3^{20}\equiv 1\pmod{100}$ and the rest follows. – yunone Sep 12 '12 at 3:24
I think this is what we have to do. Thank you for your help. – JJR Sep 12 '12 at 3:27
Also the reason 20 works even though $\varphi{(100)} = 40$ is because $\lambda{(100)} = 20$ (ref. Carmichael function). – Thomas Sep 12 '12 at 10:02
up vote 10 down vote

$$3^{400}=3^{5\cdot 2\cdot 2\cdot 20}\equiv 43^{2\cdot 2\cdot 20}\equiv 49^{2\cdot 20} \equiv 1^{20} \equiv 1 \quad(\bmod 100) $$

share|improve this answer
up vote 2 down vote

Hmmm, just happened to see this after comign over from StackOverflow, so here's a more algorithmic approach, since that's what I'm good at...

Since you only need the last two digits, you can keep truncating the left side of any results you get along the way, since they will stop contributing the value of the last two digits with each multiplication.

So, you can times 3 by itself 400 times, and after each time, ignore the 100's column and greater. Since it's 3, the last number wil only ever be 1,3,9 or 7, so we can always safely do so.

Easy to code (coming from a programmer), but I've got no idea how to put that into a mathematical formula.

share|improve this answer
2  
+1, even better: The last digits establish a periodicity. As you said, the last digits will always be 1,3,9,7,1,3,9,7,... (corresponding to $3^0,3^1,3^2,...$) with a period of four, so the final digit of $3^{400}$ is again $1$. The second-to-last digits has a sequence 0,0,0,2,8,4,2,8,6,8,4,4,4,2,6,0,2,6,8,6,0,0,0,2,... with a period of 16, which also divides $400=25\cdot16$, so the second-to-last digit is zero. And since the third-to-last digits sequence will have a periodicity that is an even multiple of 16 (I'm not sure it is definitely $16^2=256$ though), that digit is less easy... – Tobias Kienzler Sep 12 '12 at 7:17
1  
This is called modulo 100 arithmetic, for what it's worth. – Thomas Sep 12 '12 at 11:03
1  
The OP has tried this though as he mentions. – picakhu Sep 12 '12 at 12:25
This is in VBA: Function x(Pow, Mult, Modulo)Dim q: x = 1: For q = 1 To Pow: x = x * Mult Mod Modulo: NextEnd Function - I can't put newlines in a comment, so split it at the ¶ symbol – Sean Cheshire Sep 12 '12 at 15:58

Your Answer

 
discard

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.