wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> putnam exam (pure math) >> Constant Modulo N
(Message started by: william wu on Aug 23rd, 2003, 9:55pm)

Title: Constant Modulo N
Post by william wu on Aug 23rd, 2003, 9:55pm
For any positive integer n, show that the sequence { 2 , 22 , 22[sup2] , ... } eventually becomes a constant modulo n.

Title: Re: Constant Modulo N
Post by Sir Col on Aug 24th, 2003, 7:18am
I don't think this works in general?!

Let uk represent the kth term of the sequence.

Let us assume that uk [equiv] b mod n for some k.
uk+1 = (uk)2 [equiv] b2 mod n.

Now consider n=7.
u1 = 2 [equiv] 2 mod 7.
u2 [equiv] 4 mod 7
u3 [equiv] 2 mod 7, and so on.

That is, it will alternate congruence with 2 and 4, never becoming constant.

The only way to guarantee this to work, is for b=0 or b=1 for some k. In other words, n=uk or n=uk1.

For example, the actual sequence (when evaluated) is: 2,4,16,256,65536.

2 [equiv] 2 mod 15
4 [equiv] 4 mod 15
16 [equiv] 1 mod 15
256 [equiv] 1 mod 15, and so on.

Have I missed something?

Title: Re: Constant Modulo N
Post by hv2004 on Aug 24th, 2003, 7:53am
This is USAMO 1991/3. The solution involves mathematics induction and Fermat-Euler theorem. An alternate and more difficult version of this problem is Putnam 1997/B5. This problem is also similar to Putnam 1985/A4.

Title: Re: Constant Modulo N
Post by Sir Col on Aug 24th, 2003, 8:10am
But doesn't uk mod 7, alternate?

Title: Re: Constant Modulo N
Post by wowbagger on Aug 24th, 2003, 8:42am

on 08/24/03 at 07:18:44, Sir Col wrote:
Let uk represent the kth term of the sequence.

Let us assume that uk [equiv] b mod n for some k.
uk+1 = (uk)2 [equiv] b2 mod n.

I don't think that's true, because uk+1 = 2uk.

So u4 = 65536, u4 = 2 (mod 7).

Don't know whether this helps much in finding the constant n.

Or am I the one who's wrong?

Title: Re: Constant Modulo N
Post by Sir Col on Aug 24th, 2003, 8:54am
Ah, it looked to me as if each new term was being squared. It is not clear from the question if uk+1=uk2 or uk+1=2uk and that would make a difference.

As it is taken from a genuine paper, it must have a solution. You must be right, wowbagger. Cheers!

Hmm. Back to pencil and paper... ;)

Title: Re: Constant Modulo N
Post by DH on Aug 29th, 2003, 12:21pm
Suppose this holds true for all numbers smaller than n.
The sequence 21 mod n , 22 mod n , 23 mod n ... either converges to 0 or it is periodic and the period is T < n.The period cannot be n because all numbers including 0 would have to be part of the sequence.

u(k) = 2u(k-1)
u(k) mod n = 2u(k-1) mod n = 2( u(k-1) mod T ) mod n

Because T<n we already know that u(k-1) mod T will eventually converge. So u(k) will eventually converge.

To complete the induction it's easy to verify that the property holds true for n=1.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board