wu :: forums - Print Page


    
      
        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 23^rd, 2003, 9:55pm)

Title: Constant Modulo N
Post by william wu on Aug 23^rd, 2003, 9:55pm

For any positive integer n, show that the sequence { 2 , 2² , 2^2[sup2] , ... } eventually becomes a constant modulo n.

Title: Re: Constant Modulo N
Post by Sir Col on Aug 24^th, 2003, 7:18am

I don't think this works in general?!

Let u_k represent the k^th term of the sequence.

Let us assume that u_k [equiv] b mod n for some k.
u_k+1 = (u_k)² [equiv] b² mod n.

Now consider n=7.
u₁ = 2 [equiv] 2 mod 7.
u₂ [equiv] 4 mod 7
u₃ [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=u_k or n=u_k–1.

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 24^th, 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 24^th, 2003, 8:10am

But doesn't u_k mod 7, alternate?

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

on 08/24/03 at 07:18:44, Sir Col wrote:

Let u_k represent the k^th term of the sequence.

Let us assume that u_k [equiv] b mod n for some k.
u_k+1 = (u_k)² [equiv] b² mod n.

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

So u₄ = 65536, u₄ = 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 24^th, 2003, 8:54am

Ah, it looked to me as if each new term was being squared. It is not clear from the question if u_k+1=u_k² or u_k+1=2^u_k 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 29^th, 2003, 12:21pm

Suppose this holds true for all numbers smaller than n.
The sequence 2¹ mod n , 2² mod n , 2³ 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) = 2^u(k-1)
u(k) mod n = 2^u(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.