So I am continuing work on the 1985 Putnam, I recently solved problem A4. Unfortunately, like A1, it was not very hard. I have not yet solved any problem of which I am particularly proud. Ah well, I should keep on working.
Define a sequence {ai} by a1 = 3 and ai+1 = 3^ai for i ≥ 1. Which integers
between 00 and 99 inclusive occur as the last two digits in the decimal expansion of
infinitely many ai?
Okay, starting this problem in a clever way is difficult, so I decided to just compute the first few terms of the sequence, and see what happens.
a1=3
a2=27
a3=3^27 (don't know last digits as yet)
I can perform my operations modulo 100 (looking at the remainder of everything when divided by 100), and just get the last digits. However, the other digits matter when taking 3^ai. It would be really nice for me if they didn't matter. (i.e. 3^100=1 mod 100). I know from Euler's theorem 3^40=1 (mod 100). It would be very nice for me if 3^20 was the same thing. I unfortunately just decided to compute it directly.
3^20=(3^4)^5=81^5=81*81*81^3=61*81^3=61*61*81=21*81=1701=1 (mod 100), so 3^20=1, and therefore 3^100=1^5=1)
So a3=3^27=3^7=81*27=2187=87 (mod 100)
a4=3^87 mod 100
=3^7 mod 100=87.
So after a3, all our ai have last digit 87. So our answer is just 87.
Irit-
ReplyDeleteI understand the posing of the problem, but I have some issues with your explanation. WISE journals are going to be read by your teacher and other evaluators who will have nowhere near the background in this area that you do. While your explanation will make perfect sense to somebody well-versed in modular arithmetic and who knows what Euler's Theorem is, those who do not will be unable to make heads or tails of what you're saying.
I'm glad that you have chosen a project that is more interesting to you, and I hope that you start to enjoy it more, but please remember your audience. It's a good exercise for you to work on explaining things at a more fundamental level. We want to understand what you're talking about, and we're willing to sort it out, but you need to help us. Hopefully, by doing so, you'll gain a deeper understanding of what you're talking about and maybe hit upon a solution you would not have thought of otherwise.