wu :: forums
wu :: forums - Constant Modulo N

Welcome, Guest. Please Login or Register.
Sep 29th, 2022, 7:13am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: towr, Eigenray, Grimbal, SMQ, william wu, Icarus)
   Constant Modulo N
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Constant Modulo N  (Read 1147 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Constant Modulo N  
« on: Aug 23rd, 2003, 9:55pm »
Quote Quote Modify 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

   
WWW

Gender: male
Posts: 1825
Re: Constant Modulo N  
« Reply #1 on: Aug 24th, 2003, 7:18am »
Quote Quote Modify 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=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?
IP Logged

mathschallenge.net / projecteuler.net
hv2004
Guest

Email

Re: Constant Modulo N  
« Reply #2 on: Aug 24th, 2003, 7:53am »
Quote Quote Modify Modify Remove Remove

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
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Constant Modulo N  
« Reply #3 on: Aug 24th, 2003, 8:10am »
Quote Quote Modify Modify

But doesn't uk mod 7, alternate?
IP Logged

mathschallenge.net / projecteuler.net
wowbagger
Uberpuzzler
*****





242002184 242002184    


Gender: male
Posts: 727
Re: Constant Modulo N  
« Reply #4 on: Aug 24th, 2003, 8:42am »
Quote Quote Modify 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

   
WWW

Gender: male
Posts: 1825
Re: Constant Modulo N  
« Reply #5 on: Aug 24th, 2003, 8:54am »
Quote Quote Modify 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... Wink
« Last Edit: Aug 24th, 2003, 9:01am by Sir Col » IP Logged

mathschallenge.net / projecteuler.net
DH
Guest

Email

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

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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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