Author 
Topic: Constant Modulo N (Read 1144 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Constant Modulo N
« on: Aug 23^{rd}, 2003, 9:55pm » 
Quote Modify

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

« Last Edit: Aug 23^{rd}, 2003, 9:57pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825


Re: Constant Modulo N
« Reply #1 on: Aug 24^{th}, 2003, 7:18am » 
Quote Modify

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?


IP Logged 
mathschallenge.net / projecteuler.net



hv2004
Guest

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.


IP Logged 



wowbagger
Uberpuzzler
Gender:
Posts: 727


Re: Constant Modulo N
« Reply #4 on: Aug 24^{th}, 2003, 8:42am » 
Quote Modify

on Aug 24^{th}, 2003, 7:18am, 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})^{2} [equiv] b^{2} mod n. 
 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?

« Last Edit: Aug 24^{th}, 2003, 8:50am by wowbagger » 
IP Logged 
"You're a jerk, <your surname>!"



Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825


Re: Constant Modulo N
« Reply #5 on: Aug 24^{th}, 2003, 8:54am » 
Quote Modify

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...

« Last Edit: Aug 24^{th}, 2003, 9:01am by Sir Col » 
IP Logged 
mathschallenge.net / projecteuler.net



DH
Guest


Re: Constant Modulo N
« Reply #6 on: Aug 29^{th}, 2003, 12:21pm » 
Quote Modify
Remove

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.


IP Logged 



