My Math Forum 1991 usa math olympiad question!

 Math Events Math Events, Competitions, Meetups - Local, Regional, State, National, International

 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 Euler-Fermat 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)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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Justme Geometry 3 November 19th, 2013 01:37 AM Niboon Math Events 3 April 3rd, 2013 10:57 AM betelgeuse91 Math Events 4 August 18th, 2011 09:20 PM yoyobarn Math Books 1 July 25th, 2009 04:40 PM alpah Number Theory 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top