Math Help - 'simple' proofs

1. 'simple' proofs

What are the last two digits of 3^1234

2. Originally Posted by anncar
What are the last two digits of 3^1234
$3^{1234}=(3^2)^{617}=9^{617}$

if you perform the multiplication at least 6 or 10 powers of 9 (i.e up to $9^{10}$, you should notice that the last digit is 9 for odd powers and 1 for even powers; and the second to the last digit increases from 0, 2 ,4, 6, 8 then 0 again, from one odd power to the next odd power starting from 9^1, while it decreases from 8,6,4,2,0 then 8 again, from one even power to the next even power starting from 9^2..
hence, $3^{1234}=(3^2)^{617}=9^{617}$ has 69 as the last two digits..

3. Hello, anncar!

Another approach . . .

What are the last two digits of $3^{1234}$
We have: . $3^{1234} \:=\:3^{2\cdot617} \:=\:(3^2)^{617} \:=\:9^{617}\:=\:(10 - 1)^{617}$

Then we have:

. . $\underbrace{10^{617} - {617\choose1}10^{616} + {617\choose2}10^{615} + \cdots - {617\choose2}10^2}_{\text{These do not affect the last two digits}} + {617\choose616}10 - 1$

Therefore, the number ends with: . ${617\choose616}10 - 1 \;=\;6170 - 1 \;=\;61{\color{blue}69}$

4. Yet another approach is to use mod 100. This just depends on what course is asking you the question. If it's a number theory course, try this technique:

Determine $3^{1234} \mod 100$.

Note that $\phi(100) = \phi(2^2)\cdot\phi(5^2) = 2 \cdot 20 = 40$, so $3^{40} \equiv 1 \mod 100$.

Now let's determine $1234 \mod 40$. You can do this by straight pen and paper division to get $1234 = 30 \cdot 40 + 34$, so $1234 \equiv 34 \mod 40$.

So now we know that $3^{1234} \equiv 3^{34} \mod 100$, which is a much simpler problem to solve.

We know $3^5 = 243 \equiv 43 \mod 100$, so the problem again reduces to $43^6 \cdot 3^4 \mod 100$. Note $43^2 \equiv 49 \mod 100$, so we reduce further to $49^3 \cdot 81 \mod 100$, and since $49^2 \equiv 1 \mod 100$, then the problem simplifies to solving $49 \cdot 81 \mod 100$

Working out this calculation, you get $49 \cdot 81 = 3969 \equiv 69 \mod 100$.

So the final answer is 69.. again. --- this is a good problem showing how different areas of math can be used to solve a single problem.