Author |
Topic: Constant Modulo N (Read 1173 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Constant Modulo N
« on: Aug 23rd, 2003, 9:55pm » |
 Quote  Modify
|
For any positive integer n, show that the sequence { 2 , 22 , 22[sup2] , ... } eventually becomes a constant modulo n.
|
| « Last Edit: Aug 23rd, 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 24th, 2003, 7:18am » |
Quote Modify
|
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=uk–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 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.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Constant Modulo N
« Reply #4 on: Aug 24th, 2003, 8:42am » |
Quote Modify
|
on Aug 24th, 2003, 7:18am, 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?
|
| « Last Edit: Aug 24th, 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 24th, 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 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... 
|
| « Last Edit: Aug 24th, 2003, 9:01am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
DH
Guest
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove