A random blog: March 2011

I found a nice Number Theory question, so for those people who want to attack it directly, here it is:

Prove that exp 2^2(x) is eventually constant mod n (as x increases), where n is an arbitrary positive integer.

But since I expect few to solve it from there (main because of notation), I guess I should explain the weird notation.

exp 2^2(x) actually came from my interpretation of the Wikipedia article (wanted to add Knuth's up arrows, but I'm a lazy person). So what it's supposed to mean is 2^2^2^2..., with x number of 2s. This might not be standard notation, but it's what I got from Wikipedia.

Next mod n, for those who don't know, is basically asking what the remainder when the number is divided by n, eg 42=19 (mod 23), and 31 = 5 (mod 26).

So before I go on hinting like a maniac, it's time to talk about number theory in general. Number theory, in general, talks about the properties of integers. For example, number theory attempts to describe the properties of primes. However, Wikipedia lists at least 5 fields of number theory, such as algebraic number theory. In general, fields such as analytic number theory are more for research problems, which are still relatively open problems, but elementary number theory has a large number of solved problems which have elegant solutions and are light to solve (well, not as bad as researching a problem for months).

Number theory is rather interesting; when you look at a problem, it's hard to tell whether it might be easy or hard, with some messes quickly reducing to workable expressions, but stuff like proving that x^n+y^n=z^n has no integer solutions for n>=3 looks simple, but involves elliptic curves (see Fermat's Last Theorem). However, in this case, it both looks easy and is pretty doable.

Now, for people who have done some kind of number theory before, for the original question in this post, it helps to define it as a recurrence relation, with a1=2 and a2=2^a1 = 2^2 = 4. Then it suffices to prove that 2^ai = 2^a(i+1) (mod n) for any sufficiently large i.

Next, it helps to know Euler's Theorem, but is completely unnecessary (really).

The next important thing to know is the idea of induction. The general format of induction can go something like this: Student 1 is a boy. If Student i is a boy, then Student i+1 must necessarily be a boy as well. Therefore, Student 2 is a boy, therefore Student 3 is a boy, et cetera. We thereby conclude that Students 1 to the last student are all boys.

There is a similar form of induction, which works backwards. This works by say, concluding that Student i is a boy if Student i-1 is a boy. Student i-1 is a boy if Student i-2 is a boy, and this traces all the way back to Student 1, who is a boy. We are done.

An important thing to know is that the sequence 2, 4, 8, 16, 32, 64, ... enters a cycle mod n. To prove this, the most primitive way I can think of is to think of the ith term and the (i+1)th term. Say the remainder when i/n is x. This means that 2^i=kn+x, for some integer k. Therefore, 2^(i+1) = 2kn+2x, which when divided by n, gives a remainder solely defined by x. Hence, one can think of walking the remainders like a path, and with finite number of destinations to visit, one must eventually go back to the same point. Since the direction from any starting point is uniquely defined (ie you're forced to walk the same way from any same point), once you get back to the same point, there is no way you're ever going to break out from the cycle.

The substep to prove is that the length of the cycle is less than n. (Hint: consider 0 mod n)

Bad Spoiler Alert: (highlight to see)
Following this, you may realise that if the length of the cycle mod n is x, then the value of 2^i mod n is dependent on the value of 2^i mod x, where x is smaller than n. This is the induction step.

Don't forget your base case when induction though.

P.S.: This post is shorter than I expected it to be, my essay spamming skills must have deteriorated. Ohnoes.

A random blog

Saturday, March 26, 2011

Number theory

Sunday, March 6, 2011

Yet another 26 move chess match

Just a chess match

Followers

Blog Archive

Contributors