
Math Events Math Events, Competitions, Meetups  Local, Regional, State, National, International 
 LinkBack  Thread Tools  Display Modes 
December 26th, 2006, 08:27 AM  #1 
Newbie Joined: Nov 2006 Posts: 20 Thanks: 0  1991 usa math olympiad question!
Show that for any fixed integer n >=1, the sequence: 2, 2^2, 2^(2^2), 2^(2^(2^2))... mod n $$ is eventually constant. [That is, the sequence is defined: a_1=2, ai+1 = 2a_i. and you need to show that, for any positive integer n, the sequence a_1 mod n, a_2 mod n, .... is eventually constant.] Hints: Certainly the EulerFermat Theorem is involved in some way, but be careful! Just because aï‚ºb mod n$ doesn't mean 2a ï‚º2b mod n. What must be true of a and b in order for 2a to be congruent to 2b mod n? It might be enough to prove the result when n is prime, but that might not be relevant. You might consider using induction or its cousin, infinite descent. I got stuck in this question. Can you help me! 
December 26th, 2006, 06:31 PM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
You got stuck  so what do you have so far?

December 27th, 2006, 03:33 PM  #3 
Newbie Joined: Dec 2006 From: Moscow, Russia Posts: 4 Thanks: 0 
Simple induction on n. n=1 is trivial. Let n>1. By induction sequence is essential constant modulo phi(n)<n (Euler's totient function).This gives desired result. Just use If 1)a,,b,c,n are integers,2) n>0, 3)b and c are the same (modulo phi(n)) and 4)b and c are greater than some constant which depends on a and n, then a^b =a^c (mod n) 
February 7th, 2007, 04:44 AM  #4 
Newbie Joined: Jan 2007 From: Hai duong _ vietnam Posts: 2 Thanks: 0 
Oh ; can you use latex ? 
February 7th, 2007, 09:59 AM  #5 
Senior Member Joined: Dec 2006 Posts: 1,111 Thanks: 0 
No, unfortunately not... 

Tags 
1991, math, olympiad, question, usa 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Geometry question math olympiad  Justme  Geometry  3  November 19th, 2013 01:37 AM 
Math Olympiad Thailand  Niboon  Math Events  3  April 3rd, 2013 10:57 AM 
any book recommendation for math olympiad please?  betelgeuse91  Math Events  4  August 18th, 2011 09:20 PM 
Math Olympiad book for Grade 2 to 8  yoyobarn  Math Books  1  July 25th, 2009 04:40 PM 
1991 usa math olympiad question!  alpah  Number Theory  0  December 31st, 1969 04:00 PM 