

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^{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})^{2} [equiv] b^{2} mod n. Now consider n=7. u_{1} = 2 [equiv] 2 mod 7. u_{2} [equiv] 4 mod 7 u_{3} [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 FermatEuler 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:
I don't think that's true, because u_{k+1} = 2^{uk}. So u_{4} = 65536, u_{4} = 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}^{2} or u_{k+1}=2^{uk} 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^{1} mod n , 2^{2} mod n , 2^{3} 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(k1)} u(k) mod n = 2^{u(k1)} mod n = 2^{( u(k1) mod T )} mod n Because T<n we already know that u(k1) 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 © 20002004 Yet another Bulletin Board 