Archive - Jun 2, 2008

Date
  • All
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

Towers of Powers

Posted June 2nd, 2008 by Mgccl
in

I ARML 2008ed! It was great, definitely doing it next year.
There was an ARML Lecture at 8pm on the day before the ARML. Sadly I was feeding at that time, with 3 other students from my school and a Intel Talent Search Finalist who also got admitted into MIT and Harvard(She chose Harvard over MIT...) and had the highest amount of individual question right on the ARML meet in our Suffolk County Allstar team.
Our team t-shirt was: "We have imaginary friends." and a face created with a unit circle, a segment of a hyperbola and imaginary numbers. Yeah, that's the best non-perverted math t-shirt we can think of...
I am god at math jokes... most math jokes are only funny when they are perverted... I actually collect math jokes as hobby... If you need any you can ask for some
For the first time, I slept inside a university, had Subway, had Arby's, had something that I believe it's omelet.
I gained a huge amount of confidence. 4 months with 14 hours per day on math training is about enough time to make to USAMO. Yeah!

The lecture was on two problems:

1. Given n, does the sequence n, n^n,n^{n^n}... become constant when consider in the system \mathbb{Z}/k\mathbb{Z} of integers modulo k?^?

2. Given k, does the sequence 1^1, 2^2,3^3... periodic mod k? If so, when does it repeat?

Since I'm not in the lecture, I can only try to figure it out myself.
I think solved the first one, haven't start the second one.
Please anyone... check if my solution is correct or not.

Proof:
For the number in the sequence mod k eventually become a constant, then there must be a number x so that x^n \equiv x\ (mod\ k).
so the next integer in the sequence mod k is.
\begin{eqnarray} x^n^n &=& \underbrace{(((x^n)^n)^n....)}_{n n's}\\ \underbrace{(((x^n)^n)^n....)}_{n n's} &\equiv& x\ (mod\ k) \end{eqnarray}
and so on.

After finding the property of the number, now I have to find if that number ever exist in the sequence.
Answer is yes.
For any a^i \equiv b\ (mod\ k), keep increasing i will eventually create a set of repeating numbers, and the size of the set is smaller than k.
With this information, x must exist
Suppose a_i = b^i mod\ k.
a_i have a period of d, all the possible numbers are in the ordered sequence S.
If d=n, trivial case, x will be accessed the at the first try, and it's 0.
If d\not{=}n
a_n, a_{n^n}... will go though all the number in S. Until eventually one land on the x.

I'm too sleepy, can't form a great argument.

Honey Pot that kill bots