8
$\begingroup$

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.

  • 3
    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) → 12012-09-12

5 Answers 5

1

Expanding 3^400 binominally as (1+2)^400 It comes out to be 1+800k where k is a positive rational integer. Therefore last two terms are 01 and last three equals 001. Hope you understood

  • 0
    Please utilize MathJax/LaTeX markup to improve readability, and perhaps explain what 'binomially' means, since others in the future or even the OP themself will benefit from full details.2016-11-30
19

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.

  • 0
    Also the reason 20 works even though $\varphi{(100)} = 40$ is because $\lambda{(100)} = 20$ (ref. Carmichael function).2012-09-12
19

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

13

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

2

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.

  • 0
    This is in VBA: `Function x(Pow, Mult, Modulo)` ¶ `Dim q: x = 1: For q =$1$To Pow: x = x * Mult Mod Modulo: Next` ¶ `End Function` - I can't put newlines in a comment, so split it at the ¶ symbol2012-09-12