PDA

View Full Version : Math problem: Easy way?

dauerbach
05-18-2003, 09:25 PM
The question is what is the last digit of 3^99. I found the pattern of 3,5,7,9 for powers of three and bute forced it to get the answer which I don't have in front of me, but I think is 9 if I recall correctly. Took me about 15 minutes. I am sure there is a 30 second method. Anyone know what it is?

aahala
05-18-2003, 09:56 PM
The pattern seems to be 3,9,7,1 then it repeats.

So 3^100 would have 25 of those and the last digit 1.
So 3^99 would be 7.

Is this correct?

ryoushi
05-18-2003, 09:56 PM
I get 7.

I looked at the last digit of different powers of 3:

3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243

From there it repeats in a cycle of 4. 3^100 would be at the end of a cycle, so it ends in 1. 3^99 is one before that, so it ends in 7.

Q.E.D.
05-18-2003, 10:03 PM
399 = 171792506910670443678820376588540424234035840667.

So, 7 is the last digit.

dauerbach
05-18-2003, 10:10 PM
That's what I get for posting a work from memory. Yes, the pattern was 1,3,9,7. Don't know where the five came from. The same pattern in reverse occurs with 3^x where x is divisible by 9 and that is how I figured it out, by doing that 11 times.

aahala
05-18-2003, 10:12 PM
OK, so ryoushi and I have been eliminated. Now for your grand prize question.

Name that number. 171 what.
:D

DrMatrix
05-18-2003, 10:17 PM
I got 7. Since you are only concerned with the last digit, once a digit repeats, you have a cycle. In this case the length is four. Just divide 99 by four; ignore the quotent and take the remainder 3. The last digit of 3^99 = the last digit of 3^3.

BTW, this is modular arithmetic base 10. I don't remember the formula when the base is composite. With a prime modulus p:
n = n^p mod p

Or you could use brute force like Q.E.D did, I suppose.

Q.E.D.
05-18-2003, 10:22 PM
Originally posted by aahala
OK, so ryoushi and I have been eliminated. Now for your grand prize question.

Name that number. 171 what.
:D 171 quattuordecillion.
Originally posted DrMatrix
Or you could use brute force like Q.E.D did, I suppose.
:D What brute force? I just plugged it into MathCad.

Jabba
05-19-2003, 05:50 AM
Dr Matrix wrote
BTW, this is modular arithmetic base 10. I don't remember the formula when the base is composite. With a prime modulus p:
n = n^p mod p
If a and m are coprime, then
af(m) = 1 ( mod m)
where f is the Euler function.
( G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Theorem 72)

Here m = 10 and f(10) = 4, with the possible a being 1, 3, 7 or 9. So, for each of these a
a4 = 1 ( mod 10)
and so, for every k,
a4k = 1 ( mod 10)